Python самый быстрый способ объединить словари на основе соответствия ключей

Question

У меня есть 2 списка словарей.Список А длиной 34 000, список В длиной 650 000.Я, по сути, вставляю все диктанты списка B в списки диктов списка на основе совпадения ключей.В настоящее время я делаю очевидное, но это происходит навсегда (серьезно, как день).Должен быть более быстрый путь!

for a in listA:
    a['things'] = []
    for b in listB:
        if a['ID'] == b['ID']:
            a['things'].append(b)

Answer 1

from collections import defaultdict
dictB = defaultdict(list)
for b in listB:
    dictB[b['ID']].append(b)

for a in listA:
    a['things'] = []
    for b in dictB[a['ID']]:
        a['things'].append(b)

это изменит ваш алгоритм с O (n * m) на O (m) + O (n), где n = len (listA), m = len (listB)

он избегает циклического прохождения каждого dict в listB для каждого dict в listA путем «предварительного вычисления» того, что dict из listB соответствует каждому «ID»

Answer 2

Вот подход, который может помочь.Я оставлю это вам, чтобы заполнить детали.

Ваш код работает медленно, потому что это алгоритм O (n ^ 2), сравнивающий каждое A с каждым B.

Если высначала отсортируйте каждую из операций listA и listB по идентификатору (это O (nlogn)), затем вы можете легко перебирать отсортированные версии A и B (это будет за линейное время).

Этот подходобычно, когда вам приходится выполнять внешние слияния с очень большими наборами данных.Ответ Михая лучше для внутреннего слияния, когда вы просто индексируете все по id (в памяти).Если у вас есть память для хранения этих дополнительных структур, а поиск по словарю является постоянным временем, такой подход, скорее всего, будет быстрее, не говоря уже о более простом.:)

В качестве примера, скажем, у A были следующие идентификаторы после сортировки

acfgjp

, а у B были эти идентификаторы, снова после сортировки

aaaabbbbcccddeeeefffggiikknnnnppppqqqrrr

Идея, как ни странно, состоит в том, чтобы сохранить индексы для A и B (я знаю, что это звучит не очень Pythonic).Сначала вы смотрите на a в A и a в B. Таким образом, вы проходите через B, добавляя все a к вашему массиву вещей для a.Как только вы исчерпали a в B, вы переместитесь на один вверх в A, до c.Но следующий элемент в B - b, который меньше c, поэтому вам нужно пропустить b.Затем вы получите c в B, так что вы можете начать добавлять в «вещи» для c.Продолжайте в том же духе, пока оба списка не будут исчерпаны.Всего один проход.:)

Answer 3

Вместо этого я бы преобразовал ListA и ListB в словари, словари с ID в качестве ключа.Тогда просто добавить данные с помощью быстрого поиска в словаре Python:

from collections import defaultdict

class thingdict(dict):
    def __init__(self, *args, **kwargs):
        things = []
        super(thingdict,self).__init__(*args, things=things, **kwargs)

A = defaultdict(thingdict)
A[1] = defaultdict(list)
A[2] = defaultdict(list, things=[6])  # with some dummy data
A[3] = defaultdict(list, things=[7])

B = {1: 5, 2: 6, 3: 7, 4: 8, 5: 9}

for k, v in B.items():
    # print k,v
    A[k]['things'].append(v)

print A
print B

Это возвращает:

defaultdict(<class '__main__.thingdict'>, {
    1: defaultdict(<type 'list'>, {'things': [5]}),
    2: defaultdict(<type 'list'>, {'things': [6, 6]}),
    3: defaultdict(<type 'list'>, {'things': [7, 7]}),
    4: {'things': [8]},
    5: {'things': [9]}
})
{1: 5, 2: 6, 3: 7, 4: 8, 5: 9}