Python: Gruppenlistenelemente in einem dict

Question

einen Wörterbuch aus einer Liste von Worten generieren möchte, Liste Gruppierung Gegenstände durch den Wert eines Schlüssels, wie zum Beispiel:

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

Bisher habe ich zwei gefunden Wege, dies zu tun. Das erste einfach iteriert über die Liste erstellen Sublisten im dict für jeden Schlüsselwert und fügen Sie Elemente, die diese Schlüssel zum sublist passend:

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) 

und gleichzeitig einen anderen 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'))) 

Ich frage mich, welche alternative ist das effizienteste?

Gibt es einen pythisch/prägnanten oder besseren Weg, dies zu erreichen?

Answer 1

Ist es richtig, dass Sie Ihre Eingabeliste mit dem Wert des 'a' Schlüssels der Listenelemente gruppieren möchten? Wenn ja, ist Ihr erster Ansatz ist die beste, eine kleine Verbesserung, verwenden dict.setdefault:

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

Answer 2

Ein Motto -

>>> 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

Der beste Ansatz ist die erste, die Sie erwähnt, und Sie können sogar machen es ist eleganter, indem setdefault wie von bernhard oben erwähnt verwendet wird. Die Komplexität dieses Ansatzes ist O (n), da wir einfach einmal über die Eingabe iterieren und für jedes Element eine Suche in das Ausgabediktat durchführen, das wir erstellen, um die passende Liste zu finden, die eine konstante Zeit benötigt (Lookup +) anhängen) für jeden Artikel. Die überlagerte Komplexität ist also O (n), was optimal ist.

Wenn Sie itertools.groupby verwenden, müssen Sie die Eingabe vorher sortieren (das ist O (n log n)).

Answer 4

Wenn durch effiziente Sie „Zeit effizient“ meinen, es ist möglich, sie zu messen, die timeit in Modul eingebaut werden.

Zum Beispiel:

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 

Bitte beachten Sie die timeit official docs für weitere Informationen.