Python: List vs Dict para tabla de consulta

Tengo alrededor de 10 millones de valores que necesito poner en algún tipo de tabla de consulta, así que me preguntaba cuál sería una lista o dictado 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 dictado será más rápido y más eficiente.

Gracias por tu ayuda.

EDITAR 1
Poco más información sobre lo que estoy tratando de hacer. Problema de Euler 92 . Estoy haciendo una tabla de consulta para ver si un valor calculado ya se ha calculado.

Editar 2
Eficiencia para buscar.

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

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 necesitas asociar valores, usa conjuntos.

Memoria

Tanto los diccionarios como los conjuntos utilizan hash y usan mucha más memoria que solo para el almacenamiento de objetos. De acuerdo con AM Kuchling en Beautiful Code , la implementación intenta mantener el hash 2/3 completo, por lo que podría perder 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 utilizar 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. Así que entre dict y lista, 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”.


EDIT: para su nueva pregunta, SI, un conjunto sería mejor. Simplemente cree 2 conjuntos, uno para las secuencias finalizadas en 1 y otro para las secuencias finalizadas en 89. He resuelto este problema con éxito utilizando conjuntos.

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

Hice algunas evaluaciones comparativas y resulta que el dict es más rápido que la lista y el conjunto 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 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, el dictado es considerablemente más rápido que la lista y aproximadamente 3 veces más rápido que el establecido. Sin embargo, en algunas aplicaciones es posible que aún desee elegir un conjunto por su belleza. Y si los conjuntos de datos son realmente pequeños (<1000 elementos) las listas funcionan bastante bien.

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

Quieres un dict

Para las listas (sin clasificar) en Python, la operación “en” requiere O (n) tiempo — no es bueno cuando tiene una gran cantidad de datos. Por otro lado, un dict es una tabla hash, por lo que puede esperar un tiempo de búsqueda O (1).

Como han señalado otros, puede elegir un conjunto (un tipo especial de dictado) 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 del contenedor de Python.
  • SO : Tiempo de operación del contenedor Python y complejidades de memoria

Como un nuevo conjunto de pruebas para mostrar @ EriF89 sigue siendo correcto 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 una tuple , que se sabe que es más rápida que las lists (y usa menos memoria) en algunos casos de uso. En el caso de la tabla de búsqueda, la tuple no fue mejor.

Tanto el dict como el set funcionaron muy bien. Esto muestra un punto interesante relacionado con la respuesta de @SilentGhost sobre la singularidad: 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 pruebas de existencia en ese conjunto / dict. Es posible que los puntos de datos 10M solo tengan 10 valores únicos, ¡lo cual es un espacio mucho más pequeño para buscar!

El error de SilentGhost sobre los dictados en realidad es esclarecedor porque uno podría usar un dictado para correlacionar datos duplicados (en valores) en un conjunto no duplicado (claves), y así mantener un objeto de datos para almacenar todos los datos, y 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 era 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(, {1: [0, 3, 5], 2: [1, 4], 3: [2], 4: [6]}) 

Con este dictado, uno puede saber:

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

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

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