Encontrar los 3 mejores productos en listas con sublistas.
Estoy tratando de encontrar una solución más rápida que la actual, que asume la iteración sobre todos los elementos y es muy ineficiente para listas más grandes.
Para ser más específico, tengo una lista de N elementos. Cada uno de estos elementos tiene otra lista con un número variable de elementos. El objetivo es encontrar los 3 mejores productos de todas las listas, dado que solo se puede utilizar un número de cualquier lista en cualquier momento.
Por ejemplo, si tuviéramos las siguientes listas (diccionarios):
LISTA PRINCIPAL: {‘a’:0.97,’b’:0.88,’c’:0.77}
SUB-LISTA A: {‘a1′:0.68,’a2′:0.13,’a3’:0.04}
SUB-LISTA B: {‘b1′:0.77,’b2′:0.66,’b3’:0.02}
SUB-LISTA C: {‘c1′:0.99,’c2′:0.92,’c3’:0.13}
RESULTADO: 1.cc1 2.cc2 3.b*b1
Quiero obtener el número superior de todos los posibles productos. Ordenar las listas, iterar sobre todos los elementos y agregarlos a una lista temporal con los 3 mejores elementos es la solución actual, pero se vuelve problemático cuando se trata de listas con más de 1,000 elementos.
¿Alguien conoce algún tipo de algoritmo que se pueda usar aquí, dado que la longitud de cada lista puede superar los 1000 elementos?
Alternativamente, si no es posible encontrar los 3 mejores productos con una buena complejidad temporal, ¿conoce algún algoritmo que se pueda usar para encontrar, por ejemplo, el producto superior entre todas las listas?
davy.ai
Hay algunas enfoques diferentes que podrían mejorar potencialmente la complejidad temporal de este problema. Una opción potencial es utilizar estructuras de datos de montículo (heap) para mantener eficientemente los 3 (o 1) productos principales vistos hasta ahora mientras se itera sobre las listas.
Aquí hay una posible implementación:
a. Iterar sobre cada sublista en orden decreciente de valor.
b. Para cada elemento en la sublista actual:
i. Calcular el producto del elemento actual de la lista principal y el elemento actual de la sublista actual.
ii. Si el montículo tiene actualmente menos de 3 elementos, agregar el producto actual al montículo.
iii. De lo contrario, si el producto actual es mayor que el producto más bajo en el montículo, reemplazar el producto más bajo con el producto actual.
Esto debería tener una complejidad temporal de O(N log k), donde N es el número total de elementos y k es el tamaño del montículo (es decir, 3 en este caso). Si bien esto todavía es técnicamente un tiempo polinómico, debería ser significativamente más rápido que la fuerza bruta para listas grandes.
Si el objetivo es encontrar solo el producto principal, el enfoque del montículo se puede simplificar para mantener solo un único elemento máximo en lugar de un montículo. La complejidad temporal sería entonces O(N), lo que lo haría significativamente más rápido que la fuerza bruta.
Por supuesto, siempre es posible que haya restricciones o detalles adicionales que hagan que otro enfoque sea más apropiado. Pero en general, los algoritmos basados en montículos son una buena elección para encontrar los K elementos principales en un conjunto de datos grande.