Объединение словарей списков в Python

У меня есть очень большая коллекция (p, q) кортежей, которые я хотел бы преобразовать в словарь списков, где первый элемент в каждом кортеже является ключом, который индексирует список, содержащий q.

Пример:

Original List: (1, 2), (1, 3), (2, 3)  
Resultant Dictionary: {1:[2, 3], 2:[3]}

Кроме того, я хотел бы эффективно объединить эти словари.

Пример:

Original Dictionaries: {1:[2, 3], 2:[3]}, {1:[4], 3:[1]}  
Resultant Dictionary: {1:[2, 3, 4], 2:[3], 3:[1]}

Эти операции находятся внутри внутреннего цикла, поэтому я бы предпочел, чтобы они были как можно быстрее.

Заранее спасибо

Ответы

Ответ 1

Если список наборов отсортирован, itertools.groupby, как предложено @gnibbler, не является плохой альтернативой defaultdict, но его нужно использовать иначе, чем он предложил:

import itertools
import operator

def lot_to_dict(lot):
  key = operator.itemgetter(0)
  # if lot not sorted, you also need...:
  # lot = sorted(lot, key=key)
  # NOT in-place lot.sort to avoid changing it!
  grob = itertools.groupby(lot, key)
  return dict((k, [v[1] for v in itr]) for k, itr in grob)

Для "слияния" dicts списков в новый d.o.l...:

def merge_dols(dol1, dol2):
  keys = set(dol1).union(dol2)
  no = []
  return dict((k, dol1.get(k, no) + dol2.get(k, no)) for k in keys)

Я даю [] псевдоним no, чтобы избежать бесполезного построения большого количества пустых списков, учитывая, что производительность важна. Если наборы клавиш dols перекрываются только скромно, быстрее будет:

def merge_dols(dol1, dol2):
  result = dict(dol1, **dol2)
  result.update((k, dol1[k] + dol2[k])
                for k in set(dol1).intersection(dol2))
  return result

так как это использует список-catenation только для перекрывающихся ключей, поэтому, если их немного, это будет быстрее.

Ответ 2

defaltdict на помощь (как обычно)

from collections import defaultdict
my_dict = defaultdict(list)

for key,value in original_list:
    my_dict[key].append(value)

Сочетание двух dicts можно сделать так (обратите внимание, что дубликаты будут сохранены):

for key,value in orig_dict:
    new_dict[key].extend(value)

Ответ 3

collections.defaultdict работает следующим образом:

from collections import defaultdict
dic = defaultdict(list)
for i, j in tuples:
    dic[i].append(j)

похож на dicts:

a, b = {1:[2, 3], 2:[3]}, {1:[4], 3:[1]}
de = defaultdict(list, a)
for i, j in b.items():
    de[i].extend(j)

Ответ 4

Вот стиль итератора, выполняющий его

>>> mylist=[(1, 2), (1, 3), (2, 3)]
>>> from itertools import groupby
>>> from operator import itemgetter
>>> mylist=[(1, 2), (1, 3), (2, 3)]
>>> groupby(mylist,itemgetter(0))

>>> list(_)
[(1, <itertools._grouper object at 0xb7d402ec>), (2, <itertools._grouper object at 0xb7c716ec>)]

Ответ 5

Я хотел, чтобы это было сделано в одной строке только для удовольствия:

>>> from itertools import groupby
>>> t=(1, 2), (1, 3), (2, 3) 
>>> [(i,[x for _,x in list(f)]) for i,f in groupby(sorted(t),lambda t: t[0])] 
[(1, [2, 3]), (2, [3])]
>>> b={1:[2, 3], 2:[3]}, {1:[4], 3:[1]}
>>> dict([(key,sum([i[1::][0] for i in elements],[])) for key,elements in groupby(sorted(b[0].items()+b[1].items()),lambda t: t[0])])
{1: [2, 3, 4], 2: [3], 3: [1]}

Ответ 6

Вот как я это делаю в Python 2.7:

combined = {}
combined.update(d1)
combined.update(d2)

Для этого полезно определить функцию утилиты:

def merge(d1, d2):
    ''' Merge two dictionaries. '''
    merged = {}
    merged.update(d1)
    merged.update(d2)
    return merged