structures - tuple() python
Python: List vs Dict para la tabla de búsqueda (8)
Velocidad
Las búsquedas en las listas son O (n), las búsquedas en los diccionarios se amortizan O (1), con respecto al número de elementos en la estructura de datos. Si no necesita asociar valores, use conjuntos.
Memoria
Tanto los diccionarios como los conjuntos usan el hash y usan mucha más memoria que solo para el almacenamiento de objetos. Según AM Kuchling en Beautiful Code , la implementación intenta mantener lleno el hash 2/3, por lo que puede desperdiciar algo de memoria.
Si no agrega nuevas entradas sobre la marcha (lo que hace, en función de su pregunta actualizada), podría valer la pena ordenar la lista y usar la búsqueda binaria. Esto es O (log n), y es probable que sea más lento para las cadenas, imposible para los objetos que no tienen un orden natural.
Tengo alrededor de 10 millones de valores que necesito poner en algún tipo de tabla de búsqueda, así que me preguntaba ¿cuál sería una lista o dict más eficiente?
Sé que puedes hacer algo como esto para ambos:
if something in dict_of_stuff:
pass
y
if something in list_of_stuff:
pass
Mi pensamiento es que el dict será más rápido y más eficiente.
Gracias por tu ayuda.
EDIT 1
Poco más información sobre lo que intento hacer. Problema de Euler 92 . Estoy haciendo una tabla de consulta para ver si un valor calculado ya ha sido calculado.
EDIT 2
Eficiencia para buscar
EDIT 3
No hay valores asignados con el valor ... ¿un conjunto sería mejor?
En realidad, no es necesario almacenar 10 millones de valores en la tabla, por lo que no es gran cosa.
Sugerencia: piense en qué tan grande puede ser su resultado después de la primera suma de operación de cuadrados. El mayor resultado posible será mucho menor que 10 millones ...
Hice algunos benchmarking y resulta que dict es más rápido que la lista y configurado para grandes conjuntos de datos, ejecutando python 2.7.3 en una CPU i7 en Linux:
python -mtimeit -s ''d=range(10**7)'' ''5*10**6 in d''10 bucles, lo mejor de 3: 64.2 mseg por ciclo
python -mtimeit -s ''d=dict.fromkeys(range(10**7))'' ''5*10**6 in d''10000000 bucles, lo mejor de 3: 0.0759 usec por ciclo
python -mtimeit -s ''from sets import Set; d=Set(range(10**7))'' ''5*10**6 in d''1000000 bucles, lo mejor de 3: 0.262 usec por ciclo
Como puede ver, dict es considerablemente más rápido que la lista y aproximadamente 3 veces más rápido que el conjunto. Sin embargo, en algunas aplicaciones es posible que desee elegir establecer por su belleza. Y si los conjuntos de datos son realmente pequeños (<1000 elementos), las listas funcionan bastante bien.
Quieres un dict.
Para las listas (sin clasificar) en Python, la operación "in" requiere O (n) tiempo --- no es bueno cuando tiene una gran cantidad de datos. Un dict, por otro lado, es una tabla hash, por lo que puede esperar O (1) tiempo de búsqueda.
Como otros han notado, puede elegir un conjunto (un tipo especial de dict) en su lugar, si solo tiene claves en lugar de pares clave / valor.
Relacionado:
- wiki.python.org/moin/TimeComplexity : información sobre la complejidad del tiempo de las operaciones de contenedor de Python.
- SO : el tiempo de operación del contenedor de Python y las complejidades de la memoria
Una dict es una tabla hash, por lo que es muy rápido encontrar las claves. Entonces entre dict y list, dict sería más rápido. Pero si no tiene un valor para asociar, es incluso mejor usar un conjunto. Es una tabla hash, sin la parte "tabla".
EDITAR: para su nueva pregunta, SÍ, un conjunto sería mejor. Solo crea 2 juegos, uno para las secuencias que terminaron en 1 y otro para las secuencias que terminaron en 89. He resuelto este problema exitosamente usando sets.
si los datos son únicos, set () será el más eficiente, pero de dos dígitos (que también requiere exclusividad, oops :)
set() es exactamente lo que quieres. O (1) búsquedas, y más pequeño que un dict.
Respuesta contundente : los dictos son más rápidos que las listas :)