Python: voci di elenco di gruppo in un dict

Question

voglio generare un dizionario da un elenco di dizionari, raggruppando elementi della lista per il valore di qualche chiave, come ad esempio:

input_list = [ 
     {'a':'tata', 'b': 'foo'}, 
     {'a':'pipo', 'b': 'titi'}, 
     {'a':'pipo', 'b': 'toto'}, 
     {'a':'tata', 'b': 'bar'} 
] 
output_dict = { 
     'pipo': [ 
      {'a': 'pipo', 'b': 'titi'}, 
      {'a': 'pipo', 'b': 'toto'} 
     ], 
     'tata': [ 
      {'a': 'tata', 'b': 'foo'}, 
      {'a': 'tata', 'b': 'bar'} 
     ] 
} 

Finora ho trovato due modi per farlo. I primi semplicemente itera sulla lista, creare sottoliste in dict per ogni valore chiave e aggiungere elementi corrispondenti a questi tasti per la sottolista:

l = [ 
    {'a':'tata', 'b': 'foo'}, 
    {'a':'pipo', 'b': 'titi'}, 
    {'a':'pipo', 'b': 'toto'}, 
    {'a':'tata', 'b': 'bar'} 
    ] 

res = {} 

for e in l: 
    res[e['a']] = res.get(e['a'], []) 
    res[e['a']].append(e) 

E un altro utilizzando itertools.groupby:

import itertools 
from operator import itemgetter 

l = [ 
     {'a':'tata', 'b': 'foo'}, 
     {'a':'pipo', 'b': 'titi'}, 
     {'a':'pipo', 'b': 'toto'}, 
     {'a':'tata', 'b': 'bar'} 
] 

l = sorted(l, key=itemgetter('a')) 
res = dict((k, list(g)) for k, g in itertools.groupby(l, key=itemgetter('a'))) 

Mi chiedo quale alternativa è il più efficiente?

Esiste un modo più pitonico/conciso o migliore per ottenere questo risultato?

Answer 1

È corretto raggruppare l'elenco di input in base al valore del tasto "a" degli elementi dell'elenco? Se è così, il tuo primo approccio è il migliore, un miglioramento minore, utilizzare dict.setdefault:

res = {} 
for item in l: 
    res.setdefault(item['a'], []).append(item) 

Answer 2

A uno di linea -

>>> import itertools 
>>> input_list = [ 
...   {'a':'tata', 'b': 'foo'}, 
...   {'a':'pipo', 'b': 'titi'}, 
...   {'a':'pipo', 'b': 'toto'}, 
...   {'a':'tata', 'b': 'bar'} 
... ] 
>>> {k:[v for v in input_list if v['a'] == k] for k, val in itertools.groupby(input_list,lambda x: x['a'])} 
{'tata': [{'a': 'tata', 'b': 'foo'}, {'a': 'tata', 'b': 'bar'}], 'pipo': [{'a': 'pipo', 'b': 'titi'}, {'a': 'pipo', 'b': 'toto'}]} 

Answer 3

L'approccio migliore è la prima che lei ha citato, e si può anche fare è più elegante usando setdefault come menzionato da Bernhard sopra. La complessità di questo approccio è O (n) dal momento che semplicemente ripetiamo l'input una volta e per ogni elemento che eseguiamo una ricerca nell'output dict che stiamo costruendo per trovare l'elenco appropriato a cui aggiungerlo, che richiede un tempo costante (ricerca + append) per ogni articolo. Quindi la complessità overlal è O (n) che è ottimale.

Quando si utilizza itertools.groupby, è necessario ordinare prima l'input (che è O (n log n)).

Answer 4

Se per efficiente intendi "tempo efficiente", è possibile misurare utilizzando il timeit costruito nel modulo.

Ad esempio:

import timeit 
import itertools 
from operator import itemgetter 

input = [{'a': 'tata', 'b': 'foo'}, 
     {'a': 'pipo', 'b': 'titi'}, 
     {'a': 'pipo', 'b': 'toto'}, 
     {'a': 'tata', 'b': 'bar'}] 

def solution1(): 
    res = {} 
    for e in input: 
     res[e['a']] = res.get(e['a'], []) 
     res[e['a']].append(e) 
    return res 

def solution2(): 
    l = sorted(input, key=itemgetter('a')) 
    res = dict(
     (k, list(g)) for k, g in itertools.groupby(l, key=itemgetter('a')) 
    ) 
    return res 

t = timeit.Timer(solution1) 
print(t.timeit(10000)) 
# 0.0122511386871 

t = timeit.Timer(solution2) 
print(t.timeit(10000)) 
# 0.0366218090057 

Si prega di fare riferimento alla timeit official docs per ulteriori informazioni.