Tengo alrededor de 10 millones de valores que necesito poner en algún tipo de tabla de consulta, por lo que me preguntaba cuál sería más eficiente una lista o dict .

Sé que puedes hacer algo así 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.

EDITAR 1 Un
poco más de información sobre lo que estoy tratando de hacer. Problema de Euler 92 . Estoy haciendo una tabla de búsqueda para ver si un valor calculado ya está listo.

EDIT 2
Eficiencia para buscar.

EDITAR 3
No hay valores asociados con el valor ... entonces, ¿ sería mejor un conjunto ?

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 hashing 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 el hash 2/3 lleno, por lo que puede desperdiciar bastante memoria.

Si no agrega nuevas entradas sobre la marcha (lo que hace, según 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.

Un 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 aún mejor usar un conjunto. Es una tabla hash, sin la parte de "tabla".

EDITAR: para su nueva pregunta, SÍ, un conjunto sería mejor. Simplemente cree 2 conjuntos, uno para las secuencias terminadas en 1 y otro para las secuencias terminadas en 89. He resuelto con éxito este problema usando conjuntos.

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

Hice algunas evaluaciones comparativas y resultó que dict es más rápido que la lista y el conjunto para conjuntos de datos grandes, 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 ms por bucle

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

  10000000 bucles, lo mejor de 3: 0.0759 usec por bucle

• 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 bucle

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 aún desee elegir el conjunto 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 un tiempo O (n) --- no es bueno cuando tiene una gran cantidad de datos. Un dict, por otro lado, es una tabla hash, por lo que puede esperar el tiempo de búsqueda O (1).

Como otros han señalado, puede elegir un conjunto (un tipo especial de dict) en su lugar, si solo tiene claves en lugar de pares clave / valor.

Relacionado:

• Wiki de Python : información sobre la complejidad temporal de las operaciones de contenedor de Python.
• SO : tiempo de operación del contenedor Python y complejidades de memoria

si los datos son únicos, set () será el más eficiente, pero de dos dict (que también requiere unicidad, oops :)

Como un nuevo conjunto de pruebas para mostrar @ EriF89 todavía tiene razón después de todos estos años:

$ python -m timeit -s "l={k:k for k in xrange(5000)}"    "[i for i in xrange(10000) if i in l]"
1000 loops, best of 3: 1.84 msec per loop
$ python -m timeit -s "l=[k for k in xrange(5000)]"    "[i for i in xrange(10000) if i in l]"
10 loops, best of 3: 573 msec per loop
$ python -m timeit -s "l=tuple([k for k in xrange(5000)])"    "[i for i in xrange(10000) if i in l]"
10 loops, best of 3: 587 msec per loop
$ python -m timeit -s "l=set([k for k in xrange(5000)])"    "[i for i in xrange(10000) if i in l]"
1000 loops, best of 3: 1.88 msec per loop

Aquí también comparamos a tuple, que se sabe que son más rápidos que lists(y usan menos memoria) en algunos casos de uso. En el caso de la tabla de búsqueda, el tuplecarenado no mejoró.

Tanto el dicty setfuncionó muy bien. Esto trae un punto interesante relacionado con la respuesta de @SilentGhost sobre la unicidad: si el OP tiene valores de 10M en un conjunto de datos, y se desconoce si hay duplicados en ellos, entonces valdría la pena mantener un conjunto / dict de sus elementos en paralelo con el conjunto de datos real y las pruebas de existencia en ese conjunto / dict. ¡Es posible que los 10M puntos de datos solo tengan 10 valores únicos, que es un espacio mucho más pequeño para buscar!

El error de SilentGhost sobre los dictos es realmente esclarecedor porque uno podría usar un dict para correlacionar datos duplicados (en valores) en un conjunto no duplicado (claves) y, por lo tanto, mantener un objeto de datos para contener todos los datos, pero aún así ser rápido como una tabla de búsqueda. Por ejemplo, una clave dict podría ser el valor que se busca, y el valor podría ser una lista de índices en una lista imaginaria donde ocurrió ese valor.

Por ejemplo, si la lista de datos de origen a buscar fuera l=[1,2,3,1,2,1,4], podría optimizarse tanto para la búsqueda como para la memoria reemplazándola con este dict:

>>> from collections import defaultdict
>>> d = defaultdict(list)
>>> l=[1,2,3,1,2,1,4]
>>> for i, e in enumerate(l):
...     d[e].append(i)
>>> d
defaultdict(<class 'list'>, {1: [0, 3, 5], 2: [1, 4], 3: [2], 4: [6]})

Con este dict, uno puede saber:

1. Si un valor estaba en el conjunto de datos original (es decir, 2 in ddevuelve True)
2. Cuando el valor era en el conjunto de datos original (es decir, d[2]devuelve la lista de índices, donde se encontró datos en la lista de datos original: [1, 4])

En realidad, no necesita almacenar 10 millones de valores en la tabla, por lo que no es un gran problema de ninguna manera.

Sugerencia: piense en cuán grande puede ser su resultado después de la primera operación de suma de cuadrados. El mayor resultado posible será mucho menor que 10 millones ...