Encontrar todas las claves en un diccionario de una lista dada RÁPIDAMENTE

Tengo un diccionario (potencialmente bastante grande) y una lista de claves ‘posibles’. Quiero encontrar rápidamente cuál de las claves tiene valores coincidentes en el diccionario. He encontrado mucha discusión sobre los valores de un solo diccionario aquí y aquí , pero ninguna discusión sobre la velocidad o entradas múltiples.

He encontrado cuatro formas, y para las tres que funcionan mejor comparo su velocidad en diferentes tamaños de muestra a continuación: ¿existen mejores métodos? Si la gente puede sugerir candidatos razonables, también los someteré al análisis a continuación.

Las listas de muestra y los diccionarios se crean de la siguiente manera:

import cProfile from random import randint length = 100000 listOfRandomInts = [randint(0,length*length/10-1) for x in range(length)] dictionaryOfRandomInts = {randint(0,length*length/10-1): "It's here" for x in range(length)} 

Método 1: la palabra clave 'in' :

 def way1(theList,theDict): resultsList = [] for listItem in theList: if listItem in theDict: resultsList.append(theDict[listItem]) return resultsList cProfile.run('way1(listOfRandomInts,dictionaryOfRandomInts)') 

32 llamadas a funciones en 0.018 segundos

Método 2: manejo de errores:

 def way2(theList,theDict): resultsList = [] for listItem in theList: try: resultsList.append(theDict[listItem]) except: ; return resultsList cProfile.run('way2(listOfRandomInts,dictionaryOfRandomInts)') 

32 llamadas a funciones en 0.087 segundos

Método 3: establecer la intersección:

 def way3(theList,theDict): return list(set(theList).intersection(set(theDict.keys()))) cProfile.run('way3(listOfRandomInts,dictionaryOfRandomInts)') 

26 llamadas a funciones en 0.046 segundos

Método 4: Uso ingenuo de dict.keys() :

Este es un cuento de advertencia: ¡fue mi primer bash y, por lejos, el más lento!

 def way4(theList,theDict): resultsList = [] keys = theDict.keys() for listItem in theList: if listItem in keys: resultsList.append(theDict[listItem]) return resultsList cProfile.run('way4(listOfRandomInts,dictionaryOfRandomInts)') 

12 llamadas a funciones en 248.552 segundos

EDITAR: Llevar las sugerencias dadas en las respuestas en el mismo marco que he usado para mantener la coherencia. Muchos han notado que se pueden lograr más mejoras en el rendimiento en Python 3.x, particularmente en la lista de métodos basados ​​en la comprensión. Muchas gracias por toda la ayuda!

Método 5: Mejor manera de realizar la intersección (gracias jonrsharpe):

 def way5(theList, theDict): return = list(set(theList).intersection(theDict)) 

25 llamadas a funciones en 0.037 segundos

Método 6: comprensión de la lista (gracias jonrsharpe):

 def way6(theList, theDict): return [item for item in theList if item in theDict] 

24 llamadas a funciones en 0.020 segundos

Método 7: Usar la palabra clave & (gracias jonrsharpe):

 def way7(theList, theDict): return list(theDict.viewkeys() & theList) 

25 llamadas a funciones en 0.026 segundos

Para los métodos 1-3 y 5-7 los cronometré como antes con una lista / diccionarios de longitud 1000, 10000, 100000, 1000000, 10000000 y 100000000 y muestro un gráfico log-log del tiempo tomado. En todas las longitudes, la intersección y el método de enunciado funcionan mejor. Todos los gradientes son aproximadamente 1 (quizás un poco más alto), lo que indica O (n) o quizás una escala ligeramente superlineal.

Log-Log plot que compara la escala de tiempo de los 6 métodos sensibles con la longitud de lista / dict.

De un par de métodos adicionales que probé, el más rápido fue una simple lista de comprensión:

 def way6(theList, theDict): return [item for item in theList if item in theDict] 

Esto ejecuta el mismo proceso que su enfoque más rápido, way1 , pero más rápido. Para comparación, la forma más rápida basada en el set era

 def way5(theList, theDict): return list(set(theList).intersection(theDict)) 

resultados de timeit :

 >>> import timeit >>> setup = """from __main__ import way1, way5, way6 from random import randint length = 100000 listOfRandomInts = [randint(0,length*length/10-1) for x in range(length)] dictionaryOfRandomInts = {randint(0,length*length/10-1): "It's here" for x in range(length)} """ >>> timeit.timeit('way1(listOfRandomInts,dictionaryOfRandomInts)', setup=setup, number=1000) 14.550477756582723 >>> timeit.timeit('way5(listOfRandomInts,dictionaryOfRandomInts)', setup=setup, number=1000) 19.597916393388232 >>> timeit.timeit('way6(listOfRandomInts,dictionaryOfRandomInts)', setup=setup, number=1000) 13.652289059326904 

Habiendo añadido la sugerencia de @abarnert:

 def way7(theList, theDict): return list(theDict.viewkeys() & theList) 

y vuelva a ejecutar el tiempo que ahora tengo:

 >>> timeit.timeit('way1(listOfRandomInts,dictionaryOfRandomInts)', setup=setup, number=1000) 13.110055883138497 >>> timeit.timeit('way5(listOfRandomInts,dictionaryOfRandomInts)', setup=setup, number=1000) 17.292466681101036 >>> timeit.timeit('way6(listOfRandomInts,dictionaryOfRandomInts)', setup=setup, number=1000) 14.351759544463917 >>> timeit.timeit('way7(listOfRandomInts,dictionaryOfRandomInts)', setup=setup, number=1000) 17.206370930653392 

way1 y way1 han cambiado de lugar, así que volví a ejecutar:

 >>> timeit.timeit('way1(listOfRandomInts,dictionaryOfRandomInts)', setup=setup, number=1000) 13.648176054011941 >>> timeit.timeit('way6(listOfRandomInts,dictionaryOfRandomInts)', setup=setup, number=1000) 13.847062579316628 

Así que parece que el enfoque de conjunto es más lento que la lista, pero la diferencia entre la lista y la comprensión de la lista es (sorprendentemente, para mí al menos) es una variable de bits. Yo diría que simplemente elija uno, y no se preocupe por eso a menos que se convierta en un verdadero cuello de botella más adelante.

Primero, creo que estás en 2.7, así que haré la mayor parte de esto con 2.7. Pero vale la pena señalar que si está realmente interesado en optimizar su código, la twig 3.x continúa obteniendo mejoras en el rendimiento, y la twig 2.x nunca lo hará. ¿Y por qué estás usando CPython en lugar de PyPy?


De todos modos, algunas micro-optimizaciones más para probar (además de las de la respuesta de jonrsharpe :


Caché de atributos y / o búsquedas globales en variables locales (se llama LOAD_FAST por una razón). Por ejemplo:

 def way1a(theList, theDict): resultsList = [] rlappend = resultsList.append for listItem in theList: if listItem in theDict: rlappend(theDict[listItem]) return resultsList In [10]: %timeit way1(listOfRandomInts, dictionaryOfRandomInts) 100 loops, best of 3: 13.2 ms per loop In [11]: %timeit way1a(listOfRandomInts, dictionaryOfRandomInts) 100 loops, best of 3: 12.4 ms per loop 

Pero para algunos operadores, los métodos especiales, como __contains__ y __getitem__ , pueden no valer la pena. Por supuesto que no sabrás hasta que lo intentes:

 def way1b(theList, theDict): resultsList = [] rlappend = resultsList.append tdin = theDict.__contains__ tdgi = theDict.__getitem__ for listItem in theList: if tdin(listItem): rlappend(tdgi(listItem)) return resultsList In [14]: %timeit way1b(listOfRandomInts, dictionaryOfRandomInts) 100 loops, best of 3: 12.8 ms per loop 

Mientras tanto, la respuesta de Jon en way6 ya optimiza el resultList.append totalidad mediante el uso de una lista comp, y acabamos de ver que la optimización de las búsquedas que probablemente no ayude. Especialmente en 3.x, donde la comprensión se comstackrá en una función propia, pero incluso en 2.7 no esperaría ningún beneficio, por las mismas razones que en el ciclo explícito. Pero tratemos de estar seguros:

 def way6(theList, theDict): return [theDict[item] for item in theList if item in theDict] def way6a(theList, theDict): tdin = theDict.__contains__ tdgi = theDict.__getitem__ return [tdgi(item) for item in theList if tdin(item)] In [31]: %timeit way6(listOfRandomInts, dictionaryOfRandomInts) 100 loops, best of 3: 14.7 ms per loop In [32]: %timeit way6a(listOfRandomInts, dictionaryOfRandomInts) 100 loops, best of 3: 13.9 ms per loop 

Sorprendentemente (al menos para mí), esta vez realmente ayudó. No estoy seguro de por qué.

Pero lo que realmente estaba configurando era esto: otra ventaja de convertir tanto la expresión de filtro como la expresión de valor en llamadas de función es que podemos usar filter y map :

 def way6b(theList, theDict): tdin = theDict.__contains__ tdgi = theDict.__getitem__ return map(tdgi, filter(tdin, theList)) def way6c(theList, theDict): tdin = theDict.__contains__ tdgi = theDict.__getitem__ return map(tdgi, ifilter(tdin, theList)) In [34]: %timeit way6b(listOfRandomInts, dictionaryOfRandomInts) 100 loops, best of 3: 10.7 ms per loop In [35]: %timeit way6c(listOfRandomInts, dictionaryOfRandomInts) 100 loops, best of 3: 13 ms per loop 

Pero esa ganancia es en gran parte específica de 2.x; 3.x tiene una comprensión más rápida, mientras que su list(map(filter(…))) es más lenta que el map(filter(…)) 2.x map(filter(…)) o map(ifilter(…)) .


No es necesario convertir ambos lados de una intersección de conjunto en un conjunto, solo el lado izquierdo; el lado derecho puede ser cualquier iterable, y un dict ya es un iterable de sus claves.

Pero, aún mejor, la vista clave de un dict ( dict.keys en 3.x, dict.keyview en 2.7) ya es un objeto similar a un conjunto y está respaldada por la tabla hash del dict, por lo que no necesita transformar nada. . (No tiene la misma interfaz; no tiene un método de intersection , pero su operador & toma iterables, a diferencia de set , que tiene un método de intersection que toma iterables pero su & solo toma sets. Eso es molesto, pero solo nos importa el rendimiento aquí, ¿verdad?)

 def way3(theList,theDict): return list(set(theList).intersection(set(theDict.keys()))) def way3a(theList,theDict): return list(set(theList).intersection(theDict)) def way3b(theList,theDict): return list(theDict.viewkeys() & theList) In [20]: %timeit way3(listOfRandomInts, dictionaryOfRandomInts) 100 loops, best of 3: 23.7 ms per loop In [20]: %timeit way3a(listOfRandomInts, dictionaryOfRandomInts) 100 loops, best of 3: 15.5 ms per loop In [20]: %timeit way3b(listOfRandomInts, dictionaryOfRandomInts) 100 loops, best of 3: 15.7 ms per loop 

El último no ayudó (aunque usó Python 3.4 en lugar de 2.7, fue 10% más rápido …), pero el primero definitivamente lo hizo.

En la vida real, es posible que también desee comparar los tamaños de las dos colecciones para decidir cuál se configura, pero aquí la información es estática, por lo que no tiene sentido escribir el código para probarlo.


De todos modos, mi resultado más rápido fue el map(filter(…)) en 2.7, por un margen bastante bueno. En la versión 3.4 (que no mostré aquí), la lista de componentes de Jon fue más rápida (incluso se reparó para devolver los valores en lugar de las claves), y más rápida que cualquiera de los métodos 2.7. Además, la operación de configuración más rápida de 3.4 (usando la vista clave como conjunto y la lista como iterable) estuvo mucho más cerca de los métodos iterativos que en 2.7.

 $ ipython2 # Apple CPython 2.7.6 [snip] In [3]: %timeit way1(listOfRandomInts, dictionaryOfRandomInts) 100 loops, best of 3: 13.8 ms per loop $ python27x -m ipython # custom-built 2.7.9 [snip] In [3]: %timeit way1(listOfRandomInts, dictionaryOfRandomInts) 100 loops, best of 3: 13.7 ms per loop $ ipython3 # python.org CPython 3.4.1 [snip] In [3]: %timeit way1(listOfRandomInts, dictionaryOfRandomInts) 100 loops, best of 3: 12.8 ms per loop 

Entonces, eso es una aceleración del 8% usando un Python posterior. (Y la aceleración fue más cercana al 20% en las versiones listcomp y dict-key-view). Y no es porque la versión 2.7 de Apple sea mala o algo así, es solo que la versión 3.x ha seguido obteniendo optimizaciones durante los últimos 5 años o más. mientras que 2.7 no lo ha hecho (y nunca lo hará de nuevo).

Y mientras tanto:

 $ ipython_pypy # PyPy 2.5.0 Python 2.7.8 [snip] In [3]: %timeit way1(listOfRandomInts, dictionaryOfRandomInts) 1000000000 loops, best of 3: 1.97 ns per loop 

Eso es una aceleración de 7000000x simplemente escribiendo 5 caracteres adicionales. 🙂

Estoy seguro de que está haciendo trampa aquí. O bien el JIT memorizó implícitamente el resultado, o se dio cuenta de que ni siquiera lo miré, lo subí por la cadena y me di cuenta de que no tenía que hacer ninguno de los pasos, o algo así. Pero esto realmente sucede en la vida real a veces; He tenido una gran cantidad de códigos que pasaron 3 días depurando e intentando optimizar antes de darme cuenta de que todo lo que hacía era innecesario …

En cualquier caso, las aceleraciones del orden de 10x son bastante típicas de PyPy, incluso cuando no se puede hacer trampa. Y es mucho más fácil que ajustar las búsquedas de atributos o revertir el orden de quién se convierte en un conjunto para el 5%.

Jython es más impredecible, a veces casi tan rápido como PyPy, a veces mucho más lento que CPython. Desafortunadamente, el timeit se rompe en Jython 2.5.3, y acabo de romper mi Jython 2.7 completamente al actualizar de rc2 a rc3, así que … no hay pruebas hoy. De manera similar, IronPython es básicamente Jython rehecho en una máquina virtual diferente; Por lo general es más rápido, pero de nuevo impredecible. Pero mi versión actual de Mono y mi versión actual de IronPython no están jugando bien juntas, así que tampoco hay pruebas allí.