Confrontare due grandi dizionari e creare elenchi di valori per le chiavi che hanno in comune

Question

Ho un due dizionari come:

dict1 = { (1,2) : 2, (2,3): 3, (1,3): 3} 
dict2 = { (1,2) : 1, (1,3): 2} 

Quello che voglio come output è di due elenco di valori per gli elementi che esistono in entrambi i dizionari :

[2,3] 
[1,2] 

Quello che sto facendo in questo momento è qualcosa di simile:

list1 = [] 
list2 = [] 

for key in dict1.keys(): 
    if key in dict2.keys(): 
     list1.append(dict1.get(key)) 
     list2.append(dict2.get(key)) 

questo codice sta prendendo troppo tempo che non è qualcosa che non vedo l'ora di fare. Mi stavo chiedendo se ci potrebbe essere un modo più efficiente di farlo?

Answer 1

commons = set(dict1).intersection(set(dict2)) 
list1 = [dict1[k] for k in commons] 
list2 = [dict2[k] for k in commons] 

Answer 2

Non utilizzare dict.keys. Su python2.x, crea una nuova lista ogni volta che viene chiamata (che è un'operazione O(N) - E list.__contains__ è un'altra operazione O(N) in media). Basta fare affidamento sul fatto che i dizionari sono contenitori iterabili direttamente (con O(1) lookup):

list1 = [] 
list2 = [] 

for key in dict1: 
    if key in dict2: 
     list1.append(dict1.get(key)) 
     list2.append(dict2.get(key)) 

---

Si noti che il python2.7, è possibile utilizzare viewkeys per ottenere l'intersezione direttamente:

>>> a = {'foo': 'bar', 'baz': 'qux'} 
>>> b = {'foo': 'bar'} 
>>> a.viewkeys() & b 
set(['foo']) 

(su python3.x, si possibile utilizzarekeys qui invece di viewkeys)

for key in dict1.viewkeys() & dict2: 
    list1.append(dict1[key])) 
    list2.append(dict2[key])) 

Answer 3

È possibile utilizzare un elenco di comprensione all'interno zip() funzione:

>>> vals1, vals2 = zip(*[(dict1[k], v) for k, v in dict2.items() if k in dict1]) 
>>> 
>>> vals1 
(2, 3) 
>>> vals2 
(1, 2) 

O come un approccio più funzionale utilizzando vista degli oggetti e operator.itemgetter() si può fare:

>>> from operator import itemgetter 
>>> intersect = dict1.viewkeys() & dict2.viewkeys() 
>>> itemgetter(*intersect)(dict1) 
(2, 3) 
>>> itemgetter(*intersect)(dict2) 
(1, 2) 

Benchmark con risposta accettata:

from timeit import timeit 


inp1 = """ 
commons = set(dict1).intersection(set(dict2)) 
list1 = [dict1[k] for k in commons] 
list2 = [dict2[k] for k in commons] 
    """ 

inp2 = """ 
zip(*[(dict1[k], v) for k, v in dict2.items() if k in dict1]) 
    """ 
inp3 = """ 
intersect = dict1.viewkeys() & dict2.viewkeys() 
itemgetter(*intersect)(dict1) 
itemgetter(*intersect)(dict2) 
""" 
dict1 = {(1, 2): 2, (2, 3): 3, (1, 3): 3} 
dict2 = {(1, 2): 1, (1, 3): 2} 
print 'inp1 ->', timeit(stmt=inp1, 
         number=1000000, 
         setup="dict1 = {}; dict2 = {}".format(dict1, dict2)) 
print 'inp2 ->', timeit(stmt=inp2, 
         number=1000000, 
         setup="dict1 = {}; dict2 = {}".format(dict1, dict2)) 
print 'inp3 ->', timeit(stmt=inp3, 
         number=1000000, 
         setup="dict1 = {}; dict2 = {};from operator import itemgetter".format(dict1, dict2)) 

Uscita:

inp1 -> 0.000132083892822 
inp2 -> 0.000128984451294 
inp3 -> 0.000160932540894 

Per dizionari di lunghezza 10000 e gli elementi generati a caso, in 100 ciclo con:

inp1 -> 1.18336105347 
inp2 -> 1.00519990921 
inp3 -> 1.52266311646 

Edit:

Come @Davidmh menzionato nel commento per aver rifiutato di sollevare un'eccezione per secondo approccio è possibile includere il codice in un'espressione try-except:

try: 
    intersect = dict1.viewkeys() & dict2.viewkeys() 
    vals1 = itemgetter(*intersect)(dict1) 
    vals2 = itemgetter(*intersect)(dict2) 
except TypeError: 
    vals1 = vals2 = [] 

Answer 4

Questo dovrebbe essere fatto con keys in python3 e viewkeys in python2. Questi sono oggetti vista che si comportano come insiemi e non costano sforzi extra per costruirli ... sono solo "viste" delle chiavi del dizionario sottostanti. In questo modo si salva la costruzione degli oggetti set.

common = dict1.viewkeys() & dict2.viewkeys() 
list1 = [dict1[k] for k in common] 
list2 = [dict2[k] for k in common] 

dict_views oggetti possono essere intersecati direttamente con dizionari, quindi il seguente codice funziona pure. Preferirei il campione precedente però.

common = dict1.viewkeys() & dict2