Python: somma i valori dei dizionari a tre livelli

Question

Dato un dizionario con tre livelli di chiavi, qual è il modo più veloce per sommare i valori? Ecco il mio approccio attuale:

from collections import defaultdict 

dicts = [ {'a':{'b':{'c':1}}}, {'a':{'b':{'c':4, 'e':3}}} ] 

def sum_three_deep_dict_values(dicts): 
    '''Read in two dicts and return a dictionary that contains their outer-joined keys and value sums''' 
    combined = defaultdict(lambda: defaultdict(lambda: defaultdict(int))) 
    for d in dicts: 
     for w1, val_dict in d.iteritems():   
      for w2 in val_dict.iterkeys():    
       for w3 in val_dict[w2].iterkeys(): 
        combined[w1][w2][w3] += d[w1][w2][w3] 
    return combined 

print sum_three_deep_dict_values(dicts) 

Qui il risultato atteso è {'a': {'b': {'c': 5, 'e': 3}}} L'obiettivo è quello di sommare i valori per i quali entrambi i dizionari hanno gli stessi tasti (come ad esempio d[a][b][c] qui) e comprendono le restanti coppie chiave valore dal dizionario sia in il dizionario di output.

Ci sono un certo numero di domande su SO che sembrano rispondere alla domanda: "Come si dovrebbero sommare i valori dei dizionari annidati"? Leggendole la notte scorsa, comunque, ognuna delle quali ho trovato coinvolto qualche strano caso speciale o parametro, tipo "combina/ignora l'n-esimo livello di chiavi", o "applica una condizione if nel posto speciale". Volevo quindi sollevare la semplice domanda: qual è il modo migliore per sommare i valori dei dizionari double-nested in Python?

Answer 1

Penso che il tuo approccio attuale sia, in generale, buono. Il mio suggerimento sarebbe quello di eliminare il maggior numero possibile di ricerche nel dizionario. L'iterazione su chiavi e valori insieme dovrebbe essere veloce come scorrere semplicemente sui tasti, quindi potresti anche combinarli. E la chiamata finale a d[w1][w2][w3] non è necessaria se lo fai, né la ricerca della chiave provvisoria. Quindi qualcosa del genere:

def sum_three_deep_dict_values(dicts): 
    '''Read in two dicts and return a dictionary that contains 
     their outer-joined keys and value sums''' 
    combined = defaultdict(lambda: defaultdict(lambda: defaultdict(int))) 
    for layer0 in dicts: 
     for k1, layer1 in layer0.iteritems(): 
      for k2, layer2 in layer1.iteritems(): 
       for k3, count in layer2.iteritems(): 
        combined[k1][k2][k3] += count 
    return combined 

Mi sono preso la libertà di cambiare leggermente lo schema del nome.

Se si è ancora preoccupati della velocità dopo aver provato quanto sopra, potrebbe essere necessario esaminare altre strutture dati o librerie di terze parti. Ma prima di farlo, prova a PyPy - Trovo che dia spesso almeno un acceleratore 4x su loop vanilla for.

Inoltre, testare questo contro il codice originale. Penso che il mio ragionamento sopra sia valido, ma è ancora un po 'congetturale. Sono curioso anche dei suggerimenti degli altri. Alla scala su cui stai lavorando, questa potrebbe essere una sfida! (Per curiosità, per quanto tempo è questo che vi porta con il codice corrente?)

UPDATE: Ho provato questo ed è davvero più veloce, anche se solo per un pelo:

>>> %timeit sum_three_deep_original(dicts) 
1000 loops, best of 3: 1.38 ms per loop 
>>> %timeit sum_three_deep_edited(dicts) 
1000 loops, best of 3: 1.26 ms per loop 

ti sto indovinando serve più velocità per la tua applicazione. L'ho provato con PyPy, e l'ho anche compilato usando cython (ma senza modifiche o annotazioni di tipo). PyPy vince con un aumento del 66%. Plain pitone di nuovo (con un po 'diversi parametri di questa volta):

:~ $ python -c 'from tdsum import test; test()' 
1.63905096054 

compilato con Cython:

:~ $ python -c 'from tdsum import test; test()' 
1.224848032 

E l'utilizzo di PyPy:

:~ $ pypy -c 'from tdsum import test; test()' 
0.427165031433 

mi si aspetterebbe una versione reale Cython utilizzando un struttura dati personalizzata per sovraperformare PyPy in modo significativo. Il problema è che non puoi usare dict s e comunque ottenere l'accelerazione di iterazione che desideri, perché cython deve perdere tempo con l'overhead degli oggetti Python. Quindi dovresti implementare la tua tabella hash!

Mi sono chiesto spesso perché cython non fornisce una soluzione a questo problema; forse c'è un tipo numpy là fuori che sarebbe utilizzabile. Continuerò a cercare!

Answer 2

Ecco una soluzione che utilizza una funzione di appiattimento e una funzione di gonfiaggio, per problemi arbitrariamente profondamente annidati. Funziona per te input, ma non lo testò molto di più:

from collections import Counter 

def flatten(d, parent=None): 
    for k, v in d.items(): 
     keys = (k,) if parent is None else parent + (k,) 
     if isinstance(v, dict): 
      yield from flatten(v, keys) 
     else: 
      yield keys, v 

def puffup(c): 
    top = {} 
    for k, v in c.items(): 
     current = top # reset walk 
     for ki in k[:-1]: 
      if ki not in current: 
       current[ki] = {} 
     current[k[-1]] = v 
    return top 

dicts = [ {'a':{'b':{'c':1}}}, {'a':{'b':{'c':4, 'e':3}}} ] 
c = Counter() 
for d in dicts: 
    c += dict(flatten(d)) 
print(puffup(c)) 
# {'a': {'b': {'c': 5, 'e': 3}}} 

Ho appena visto che stai cercando il più veloce. Anche se molto più flessibile, questo è ~ 2.5 volte più lento della risposta sopra, senza fare jigging con gli input molto del tutto.