Comprensione del dizionario Python molto lenta

Question

Ho un dizionario d1 e un elenco l1.

Le chiavi del dizionario sono stringhe e i valori sono Oggetti che ho definito io. Se è utile, posso descrivere l'oggetto in maggiore dettaglio ma per ora gli oggetti hanno un attributo di lista names e alcuni degli elementi di name possono o non possono apparire in l1.

Quello che volevo fare era di buttare via qualsiasi elemento del dizionario d1, in cui l'attributo name dell'oggetto in detto elemento non contiene nessuno degli elementi che appaiono in l1.

Come esempio banale:

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']} 

così dizionario risultante sarà più o meno lo stesso ma gli elementi di ciascuna lista saranno le coppie di valori-chiave da 1 a 4 esclusione degli ortofrutticoli, e non conterrà un quinto valore chiave-valore in quanto nessuno dei valori del mobilio appare in l1.

Per fare questo ho usato un elenco nidificato/comprensione dizionario che si presentava così:

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'],} 

Questo sembra funzionare, ma per i dizionari, le grandi 7000+ articoli, ci vogliono circa 20 secondi per lavorare attraverso. In sé e per sé, non è orribile, ma ho bisogno di farlo all'interno di un ciclo che eseguirà una iterazione di 10.000 volte, quindi al momento non è fattibile. Qualche suggerimento su come farlo rapidamente?

Answer 1

Si sta effettivamente calcolando l'intersezione di ciascuna lista presente nei valori del dizionario con l'elenco l1. L'utilizzo di elenchi per le intersezioni di set è piuttosto inefficiente a causa delle ricerche lineari coinvolte. Dovresti trasformare l1 in un set e usare set.intersection() o impostare i test di appartenenza (a seconda che sia accettabile che il risultato sia di nuovo un set).

Il codice completo potrebbe essere la seguente:

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} 

Al posto dei due comprensioni del dizionario, ma potrebbe anche essere preferibile utilizzare un unico for ciclo qui:

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 questione non è la comprensione del ditt, ma la comprensione dell'elenco annidato in quello. Stai ripetendo le stesse chiavi ogni volta. Questo genere di cose è meglio fare con i set.

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

Se si converte l1 ad un set e un po 'di modificare la comprensione dict, è possibile ottenere questo lavoro circa tre volte più veloce:

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) 

Ecco come puoi confrontare le prestazioni:

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) 

Suppongo qui che non si abbia il controllo su d1 e che la conversione di tutti i valori di d1 in set prima del filtro sia troppo 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)) 

uscita:

{'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())))