por qué el operador 'in' con tupla como clave en python es tan lento?

Question

que tienen un diccionario como:

d=dict() 
d[('1','2')] = 'value' 

Entonces consultar la clave:

if (k1,k2) in d.keys(): 

Cuando hay millones de registros, la velocidad es un sufrimiento, cualquier problema con el operador 'in'?

¿Es una búsqueda secuencial?

Tengo que concat str como clave para eludir este problema.

Answer 1

Debe utilizar

(k1,k2) in d 

en lugar de llamar d.keys().

Haciéndolo a su manera, en Python 2 dará como resultado una búsqueda lineal y más bien anula los beneficios de dict. En Python 3 su código es eficiente (ver comentarios más abajo) pero mi versión es más clara.

Answer 2

Teniendo en cuenta la incorporación de Nolen Royalty, pensé en tomar nota de que realmente puedes hacer las pruebas timeit de una manera un poco mejor. Al mover la construcción del dict a una función de configuración, podemos sincronizar solo las operaciones en el dict, lo que nos proporciona un resultado que podemos comparar fácilmente.

En 3.2:

python -m timeit -s 'd = {(str(i), str(j)):"a" for i in range(100) for j in range(1000)}' '_ = ("1", "2") in d.keys()' '_ = (1, 2) in d.keys()' 
1000000 loops, best of 3: 0.404 usec per loop 

python -m timeit -s 'd = {(str(i), str(j)):"a" for i in range(100) for j in range(1000)}' '_ = ("1", "2") in d' '_ = (1, 2) in d' 
1000000 loops, best of 3: 0.247 usec per loop 

Se puede ver la diferencia. En 3.x, trabajar directamente en el dict nos da un aumento de velocidad de casi 2x, lo cual no está nada mal.

En 2.7.3:

python2 -m timeit -s 'd = {(str(i), str(j)):"a" for i in range(100) for j in range(1000)}' '_ = ("1", "2") in d.keys(); _ = (1, 2) in d.keys()' 
10 loops, best of 3: 36.3 msec per loop 

python2 -m timeit -s 'd = {(str(i), str(j)):"a" for i in range(100) for j in range(1000)}' '_ = ("1", "2") in d' '_ = (1, 2) in d' 
10000000 loops, best of 3: 0.197 usec per loop 

En 2.x, la diferencia es verdaderamente asombroso . Usar dict.keys() toma 36,300 microsegundos, mientras que solo el dict tarda menos de 0,2 microsegundos. Eso se acerca a doscientos mil veces más rápido.

Sólo pensé que valía la pena una nota.

Editar:

Tim hizo un comentario interesante, así que decidimos hacer anteras prueba. He intentado la mera construcción de la lista, y luego simplemente hacer la búsqueda de hash, se traduce de la siguiente manera:

python2 -m timeit -s 'd = {(str(i), str(j)):"a" for i in range(100) for j in range(1000)}' 'd.keys()' 'd.keys()' 
100 loops, best of 3: 5.84 msec per loop 

python2 -m timeit -s 'd = {(str(i), str(j)):"a" for i in range(100) for j in range(1000)}' -s 'l=d.keys()' '_ = ("1", "2") in l' '_ = ("1", "2") in l' 
10 loops, best of 3: 25.3 msec per loop 

se puede ver que en un gran dict como este, la construcción de la lista toma alrededor de 1/6 de la hora, haciendo la búsqueda a través de la lista 5/6ths del tiempo.