comprensión del diccionario de Python muy lento

Question

Tengo un diccionario d1 y una lista l1.

Las claves del diccionario son cadenas, y los valores son Objetos que yo mismo he definido. Si ayuda, puedo describir el Objeto con más detalle, pero por ahora, los objetos tienen un atributo de lista names, y algunos de los elementos de name pueden aparecer o no en l1.

Lo que quería hacer era tirar a la basura cualquier elemento del diccionario d1, en el que el atributo name del objeto en dicho elemento no contiene ninguno de los elementos que aparecen en l1.

Como un ejemplo trivial:

l1 = ['cat', 'dog', 'mouse', 'horse', 'elephant', 
     'zebra', 'lion', 'snake', 'fly'] 

d1 = {'1':['dog', 'mouse', 'horse','orange', 'lemon'], 
     '2':['apple', 'pear','cat', 'mouse', 'horse'], 
     '3':['kiwi', 'lime','cat', 'dog', 'mouse'], 
     '4':['carrot','potato','cat', 'dog', 'horse'], 
     '5':['chair', 'table', 'knife']} 

por lo que el diccionario resultante será más o menos la misma, pero los elementos de cada lista serán los pares de valores clave de 1-4 excluyendo las frutas y hortalizas, y no contendrá una 5ª par clave-valor, ya que ninguno de los valores de mobiliario aparece en l1.

Para ello he utilizado una lista anidada/comprensión de diccionario que se veía así:

d2 = {k: [a for a in l1 if a in d1[k]] for k in d1.keys()} 
print(d2) 

>>>>{'1': ['dog', 'mouse', 'horse'], 
    '3': ['cat', 'dog', 'mouse'], 
    '2': ['cat', 'mouse', 'horse'], 
    '5': [], 
    '4': ['cat', 'dog', 'horse']} 

d2 = {k: v for k,v in d2.iteritems() if len(v)>0} 
print(d2) 

>>>>{'1': ['dog', 'mouse', 'horse'], 
    '3': ['cat', 'dog', 'mouse'], 
    '2': ['cat', 'mouse', 'horse'], 
    '4': ['cat', 'dog', 'horse'],} 

Esto parece funcionar, pero para grandes diccionarios, artículos de 7000, se tarda unos 20 segundos para trabajar a través. En sí mismo, no es horrible, pero necesito hacer esto dentro de un bucle que iterará 10.000 veces, por lo que actualmente no es factible. ¿Alguna sugerencia sobre cómo hacer esto rápidamente?

Answer 1

Está calculando eficazmente la intersección del conjunto de cada lista que aparece en los valores del diccionario con la lista l1. Usar listas para establecer intersecciones es bastante ineficiente debido a las búsquedas lineales involucradas. Debe convertir l1 en un conjunto y usar set.intersection() o establecer pruebas de membresía en su lugar (dependiendo de si es aceptable que el resultado sea un conjunto nuevo).

El código completo podría tener este aspecto:

l1 = set(l1) 
d2 = {k: [s for s in v if s in l1] for k, v in d1.iteritems()} 
d2 = {k: v for k, v in d2.iteritems() if v} 

En lugar de las dos comprensiones del diccionario, sino que también podría ser preferible utilizar un solo for bucle aquí:

l1 = set(l1) 
d2 = {} 
for k, v in d1.iteritems(): 
    v = [s for s in v if s in l1] 
    if v: 
     d2[k] = v 

Answer 2

La cuestión no es la comprensión dict, pero la lista anidada comprende dentro de eso. Estás iterando sobre las mismas teclas todo el tiempo. Este tipo de cosas se hace mejor con sets.

s1 = set(l1) 
d2 = {k: list(s1.intersection(v)) for k, v in d1.items()} 

Answer 3

Uso set:

>>> l1 = ['cat', 'dog', 'mouse', 'horse', 'elephant', 
     'zebra', 'lion', 'snake', 'fly'] 
>>> d1 = {'1':['dog', 'mouse', 'horse','orange', 'lemon'], 
     '2':['apple', 'pear','cat', 'mouse', 'horse'], 
     '3':['kiwi', 'lime','cat', 'dog', 'mouse'], 
     '4':['carrot','potato','cat', 'dog', 'horse'], 
     '5':['chair', 'table', 'knife']} 
>>> l1_set = set(l1) 
>>> d2 = dict((k, set(d1[k]) & l1_set) for k in d1.keys()) 
>>> d2 
{'1': set(['horse', 'mouse', 'dog']), '3': set(['mouse', 'dog', 'cat']), '2': set(['horse', 'mouse', 'cat']), '5': set([]), '4': set(['horse', 'dog', 'cat'])} 
>>> d2 = dict((k, v) for k,v in d2.iteritems() if v) 
>>> d2 
{'1': set(['horse', 'mouse', 'dog']), '3': set(['mouse', 'dog', 'cat']), '2': set(['horse', 'mouse', 'cat']), '4': set(['horse', 'dog', 'cat'])} 

Answer 4

Si convierte l1 a un set y modificar ligeramente la comprensión dict, se puede conseguir este trabajo aproximadamente tres veces más rápido:

l1 = set(['cat', 'dog', 'mouse', 'horse', 'elephant', 
     'zebra', 'lion', 'snake', 'fly']) 

d1 = {'1':['dog', 'mouse', 'horse','orange', 'lemon'], 
     '2':['apple', 'pear','cat', 'mouse', 'horse'], 
     '3':['kiwi', 'lime','cat', 'dog', 'mouse'], 
     '4':['carrot','potato','cat', 'dog', 'horse'], 
     '5':['chair', 'table', 'knife']} 

d2 = {k: [a for a in d1[k] if a in l1] for k in d1.keys()} 
print(d2) 

Así es como puede comparar el rendimiento:

import timeit 

t = timeit.Timer(
    "d2 = {k: [a for a in l1 if a in d1[k]] for k in d1.keys()}", 
    "from __main__ import (d1, l1)", 
    ) 
print "%.2f usec/pass" % (1000000 * t.timeit(number=100000)/100000) 

t = timeit.Timer(
    'd2 = {k: [a for a in d1[k] if a in l1] for k in d1.keys()}', 
    "from __main__ import (d1, l1)", 
    ) 
print "%.2f usec/pass" % (1000000 * t.timeit(number=100000)/100000) 

Supongo que no tiene control sobre d1, y que la conversión de todos los valores de d1 a conjuntos antes del filtrado es demasiado lenta.

Answer 5

l1 = ['cat', 'dog', 'mouse', 'horse', 'elephant', 
     'zebra', 'lion', 'snake', 'fly'] 

d1 = {'1':['dog', 'mouse', 'horse','orange', 'lemon'], 
     '2':['apple', 'pear','cat', 'mouse', 'horse'], 
     '3':['kiwi', 'lime','cat', 'dog', 'mouse'], 
     '4':['carrot','potato','cat', 'dog', 'horse'], 
     '5':['chair', 'table', 'knife']} 

def gen_items(valid_name_set, d): 
    for k, v in d.iteritems(): 
     intersection = valid_name_set.intersection(v) 
     if intersection: # not empty 
      yield (k, intersection) 

print dict(gen_items(set(l1), d1)) 

Salida:

{'1': set(['dog', 'horse', 'mouse']), 
'2': set(['cat', 'horse', 'mouse']), 
'3': set(['cat', 'dog', 'mouse']), 
'4': set(['cat', 'dog', 'horse'])} 

alternativa:

from itertools import ifilter 
from operator import itemgetter 
set_l1 = set(l1) 
d2 = dict(ifilter(itemgetter(1), 
        ((k, set_l1.intersection(v)) for k, v in d1.iteritems())))