Объедините два больших словаря по ключу - самый быстрый подход

Question

У меня есть два больших словаря: это пример для демонстрации, но вы можете представить каждый словарь, имеющий около 100 тыс. Записей.

d1 = {'0001': [('skiing',0.789),('snow',0.65),('winter',0.56)],'0002': [('drama', 0.89),('comedy', 0.678),('action',-0.42), ('winter',-0.12),('kids',0.12)]}

d2 = {'0001': [('action', 0.89),('funny', 0.58),('sports',0.12)],'0002': [('dark', 0.89),('Mystery', 0.678),('crime',0.12), ('adult',-0.423)]}

В качестве конечной цели я хочу иметь словарь, который объединяет значения по ключу из каждого словаря:

{'0001': [('skiing', 0.789), ('snow', 0.65), ('winter', 0.56), [('action', 0.89), ('funny', 0.58), ('sports', 0.12)]], '0002': [('drama', 0.89), ('comedy', 0.678), ('action', -0.42), ('winter', -0.12), ('kids', 0.12), [('dark', 0.89), ('Mystery', 0.678), ('crime', 0.12), ('adult', -0.423)]]}

Способ, которым я достиг бы этого:

for key,value in d1.iteritems():
     if key in d2:
             d1[key].append(d2[key])

Но после прочтения во многих местах я узнал, что iteritems() действительно медленный и на самом деле не использует структуры данных C, чтобы сделать это, но использует функции Python. Как я могу сделать это объединить / объединить процесс быстро и эффективно.

Answer 1

Если ваш вклад должен быть диктом, я не думаю, что вы найдете что-то быстрее, чем iteritems, Если у одного dict заметно меньше ключей, чем у другого, вам следует перебрать меньший ключ, чтобы сократить количество итераций.

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

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

timeit дает следующие скорости для различных предложенных подходов, учитывая два дикта из 200 ключей (одинаковые клавиши для обоих диктов):

• iteritem (как дано n вопрос): 23.0725131035
• итерация по заданному пересечению: 31.7572350502
• объединение объектов Counter: 125.085702181
• перебрать списки: 16.3535020351

Чтобы дать перекрестку еще один шанс, пусть только половина ключей d2 на самом деле совпадают с d1:

• Итерит: 15.5433290005
• установить пересечение: 22.1796240807

Как мы видим, стоимость создания двух наборов все еще перевешивает любую потенциальную выгоду (по крайней мере, в Python 2, где dict.keys() дает список, а не совместимое с множеством операций представление).

Примечание: добавление против расширения

В вашем текущем примере кода

for key,value in d1.iteritems():
    if key in d2:
        d1[key].append(d2[key])

вы добавляете весь список d2 как один новый элемент списка в d1вместо слияния списков ([1,2].append([3,4]) == [1,2,[3,4]]не [1,2,3,4]). Вы можете перебрать список из d2 и вызывать добавить несколько раз, но extend() будет быстрее

Answer 2

for k, v in d2.items():
    if k in d1:
        d1[k].extend(v)
    else:
        d1[k] = v  

Answer 3

Я думаю, вам нужно объединить dicts

from collections import Counter
res = Counter(d1) + Counter(d2)
>>>res
Counter({'0001': [('skiing', 0.789), ('snow', 0.65), ('winter', 0.56 **...**

Например

from collections import Counter

d1 = {"a":[1,2], "b":[]}
d2 = {"a":[1,3], "b":[5,6]}

res = Counter(d1)+Counter(d2)

>>>res
Counter({'b': [5, 6], 'a': [1, 2, 1, 3]})

Даже такой подход поддерживает неодинаковое количество ключей в dicts, лайк

d1 = {"a":[1,2], "b":[]}
d2 = {"a":[1,3], "b":[5,6], "c":["ff"]}

>>>res
Counter({'c': ['ff'], 'b': [5, 6], 'a': [1, 2, 1, 3]})

Answer 4

Вы можете сделать это путем -

>>> d1 = {'0001': [('skiing',0.789),('snow',0.65),('winter',0.56)],'0002': [('drama', 0.89),('comedy', 0.678),('action',-0.42), ('winter',-0.12),('kids',0.12)]}
>>> d2 = {'0001': [('action', 0.89),('funny', 0.58),('sports',0.12)],'0002': [('dark', 0.89),('Mystery', 0.678),('crime',0.12), ('adult',-0.423)]}
>>> dict( (n, d1.get(n, []) + d2.get(n, [])) for n in set(d1)|set(d2) )
{'0001': [('skiing', 0.789), ('snow', 0.65), ('winter', 0.56), ('action', 0.89), ('funny', 0.58), ('sports', 0.12)], '0002': [('drama', 0.89), ('comedy', 0.678), ('action', -0.42), ('winter', -0.12), ('kids', 0.12), ('dark', 0.89), ('Mystery', 0.678), ('crime', 0.12), ('adult', -0.423)]}

Answer 5

d1 = {'0001': [('skiing',0.789),('snow',0.65),('winter',0.56)],'0002': [('drama', 0.89),('comedy', 0.678),('action',-0.42), ('winter',-0.12),('kids',0.12)]}
d2 = {'0001': [('action', 0.89),('funny', 0.58),('sports',0.12)],'0002': [('dark', 0.89),('Mystery', 0.678),('crime',0.12), ('adult',-0.423)]}

for x in set(d1).intersection(set(d2)):
    d1[x].extend(d2[x])

Может быть, вы можете попробовать эту программу. Сначала я получаю пересечение между d1 и d2, поэтому я мог бы выполнить наименьшее количество итераций для этой задачи.