tuplas de Python como teclas lentas?

Question

Estoy tratando de implementar una búsqueda rápida de tuplas ordenadas en un diccionario; algo que responde a la pregunta "¿Tiene la tupla (3,8) un valor asociado, y si es así, qué es?". Deje que los enteros en las tuplas se vinculen desde abajo por 0 y desde arriba por max_int.

Me adelanté y usé el dict de Python, pero encontré que era bastante lento. Otro enfoque para este problema sería crear una lista T con max_int (en su mayoría vacíos) dicts, y para cada tupla (3,8) poner T [3] [8] = valor. Creo que este es exactamente el enfoque de cubo y pico que Python toma con los dicts, pero este último es aproximadamente 30 veces (¡!) Más rápido aquí.

También, sin embargo, es feo (especialmente porque ahora estoy por implementar 3-tuplas), así que agradecería algunas sugerencias aquí.

Como referencia, aquí está el código que utiliza para obtener los tiempos:

import numpy as np 
import time 

# create a bunch of sorted tuples 
num_tuples = 10 
max_int = 100 
a = np.random.rand(num_tuples,2) * max_int 
a = a.astype(int) 
for k in xrange(len(a)): 
    a[k] = np.sort(a[k]) 

# create dictionary with tuples as keys 
d = {} 
for t in a: 
    d[tuple(t)] = 42 

print d 

# do some lookups 
m = 100000 
start_time = time.time() 
for k in xrange(m): 
    (3,8) in d.keys() 
elapsed = time.time() - start_time 
print elapsed 

# now create the bucket-list structure mentioned above 
t = [{} for k in xrange(max_int)] 
for k in xrange(len(a)): 
    t[a[k][0]][a[k][1]] = 42 

print t 

# do some lookups 
m = 10000 
start_time = time.time() 
for k in xrange(m): 
    8 in t[3].keys() 
elapsed = time.time() - start_time 
print elapsed 

Answer 1

Aquí están los resultados de temporización precisas con Python 2.7:

>>> %timeit (3, 8) in d.keys() # Slow, indeed 
100000 loops, best of 3: 9.58 us per loop 

>>> %timeit 8 in t[3].keys() # Faster 
1000000 loops, best of 3: 246 ns per loop 

>>> %timeit (3, 8) in d # Even faster! 
10000000 loops, best of 3: 117 ns per loop 

>>> %timeit 8 in t[3] # Slightly slower 
10000000 loops, best of 3: 127 ns per loop 

Muestran que la norma (3, 8) in d (sin edificio .keys() lista) es en realidad un poco más rápido que el (menos general) 8 in t[3] enfoque, y doble rápido como el relativamente rápido 8 in t[3].keys() de la pregunta. Esta diferencia .keys/no .keys proviene del hecho de que (3, 8) in d.keys() construye una lista (en Python 2) de las claves y luego busca (3, 8) en esta lista, que es mucho más lenta que buscar (3, 8) en la tabla hash del diccionario d.

Como se señaló en los comentarios, los resultados de los tiempos son diferentes con Python 3: Python 3 de keys() tiene una prueba rápida in porque keys() rendimientos en lugar de una visión sobre las teclas, por lo que el operador in puede utilizar la tabla de dispersión de los correspondientes diccionario.

La diferencia de velocidad en la pregunta original proviene del hecho de que d.keys() construye una lista relativamente larga, en comparación con t[3].keys().

PD: la función %timeit es proporcionada por la excelente carcasa IPython. El programa original se puede ejecutar a través de IPython con %run prog.py.

Answer 2

que está probando para diferentes valores. En la versión de diccionario, hay una búsqueda de 100.000 claves, mientras que en la estructura de listas de elementos, la búsqueda es de solo 10.000 teclas.

Aparte de eso, este fragmento de código está ralentizando las cosas: (3,8) in d.keys() si acaba de escribir (3,8) in d, entonces el tiempo de búsqueda en ambas versiones sería bastante similar, y la diferencia insignificante. Haga esta prueba modificada y ver por sí mismo:

import numpy as np 
import time 

# create a bunch of sorted tuples 
num_tuples = 10 
max_int = 100 
a = np.random.rand(num_tuples,2) * max_int 
a = a.astype(int) 
for k in xrange(len(a)): 
    a[k] = np.sort(a[k]) 

# create dictionary with tuples as keys 
d = {} 
for t in a: 
    d[tuple(t)] = 42 

# do some lookups 
m = 100000 
start_time = time.time() 
for k in xrange(m): 
    if (3,8) in d: 
     pass 

elapsed = time.time() - start_time 
print elapsed 

# now create the bucket-list structure mentioned above 
t = [{} for k in xrange(max_int)] 
for k in xrange(len(a)): 
    t[a[k][0]][a[k][1]] = 42 

# do some lookups 
m = 100000 
start_time = time.time() 
for k in xrange(m): 
    if 8 in t[3]: 
     pass 

elapsed = time.time() - start_time 
print elapsed 

La razón para el comportamiento observado es que tanto (3,8) in d.keys() y 8 in t[3].keys() están creando una nueva lista temporal de claves cada vez, pero la segunda versión crea listas más cortas. Si simplemente usó la expresión idiomática key in dictionary, las listas temporales ya no se crean y el rendimiento comienza a parecer similar para ambos enfoques.

Me gustaría ir con la primera versión, es mucho más simple, más fácil de leer y entender y idiomático - y cuando se usa correctamente, funciona igual de bien que la segunda versión.

Answer 3

Es un poco extraño comparar la velocidad de (a, b) in d a b in t[a] porque esta última asume que a debe estar presente.

En cualquier caso, la primera manera siempre debe ser más rápida. Ambas versiones tienen a y b. El primero tiene la sobrecarga adicional de asignar una tupla y mezclarla. Sin embargo, la segunda forma hace dos búsquedas separadas de diccionario.