Python: Lista vs Dict para la tabla de búsqueda de

Question

Tengo cerca de 10 millones de valores que tengo que poner en algún tipo de tabla de búsqueda, así que me preguntaba lo que sería más eficiente una lista o dict?

Sé que usted puede hacer algo como esto para ambos:

if something in dict_of_stuff: 
    pass 

y

if something in list_of_stuff: 
    pass 

Mi pensamiento es el dict será más rápido y más eficiente.

Gracias por su ayuda.

EDIT 1
poco más de información sobre lo que estoy tratando de hacer. Euler Problem 92. Estoy haciendo una tabla de consulta para ver si un valor calculado ya ha sido calculado.

EDIT 2
Eficiencia para buscar.

EDITAR 3
No existen valores assosiated con el valor ... así que sería un conjunto ser mejor?

Answer 1

velocidad

búsquedas en las listas son O (n), las búsquedas en los diccionarios se amortizan O (1), en relación con el número de elementos en la estructura de datos. Si no necesita asociar valores, use conjuntos.

memoria

Ambos diccionarios y conjuntos utilizan hash y utilizan mucha más memoria que sólo para el almacenamiento de objetos. De acuerdo con A.M. Kuchling en Beautiful Code, la implementación intenta mantener el hash 2/3 lleno, por lo que puede perder bastante 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.

Answer 2

si los datos son conjunto único() será el más eficiente, sino de dos - dict (que también requiere singularidad, oops :)

Answer 3

un diccionario es una tabla hash, por lo que es muy rápido para encontrar la llaves. 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.

Answer 4

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 han notado otros, puede elegir un conjunto (un tipo especial de dict) en su lugar, si solo tiene claves en lugar de pares clave/valor.

relacionadas:

• Python wiki: información sobre la complejidad del tiempo de las operaciones de contenedores de Python.
• SO: Operación contenedor de tiempo y memoria complejidades Python

Answer 5

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 cuadrados de operación. El mayor resultado posible será mucho menor que 10 millones ...

Answer 6

set() es exactamente lo que desea. O (1) búsquedas, y más pequeño que un dict.

Answer 7

hice un poco de evaluación comparativa y resulta que dict es más rápido que ambos lista y establecer para grandes conjuntos de datos, ejecutar Python 2.7.3 en una CPU i7 en Linux:

• python -mtimeit -s 'd=range(10**7)' '5*10**6 in d'

  10 bucles, mejor de 3: 64,2 mseg por bucle

• python -mtimeit -s 'd=dict.fromkeys(range(10**7))' '5*10**6 in d'

  10000000 bucles, mejor de 3: 0.075 9 USEC por lazo

• python -mtimeit -s 'from sets import Set; d=Set(range(10**7))' '5*10**6 in d'

  1000000 bucles, mejor de 3: 0,262 USEC por lazo

Como se puede ver, dict es considerablemente más rápido que 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.