Python 合并字典的最快方法（基于键匹配）

Question

我有两个字典列表。列表A有34,000个元素，列表B有650,000个元素。我基本上是根据一个键的匹配，把列表B中的所有字典插入到列表A中的字典里。目前我在用最简单的方法，但这花了我很长时间（真的，像一天那么久）。肯定有更快的方法！

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

Answer 1

我会把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}

Answer 2

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 是 listA 的长度，m 是 listB 的长度。

简单来说，这样做可以避免在 listA 的每个字典上都去遍历 listB 的每个字典，而是通过“预先计算”哪些 listB 的字典和每个“ID”匹配，从而提高效率。

Answer 3

这里有一个可能对你有帮助的方法。我就不详细说明了，留给你自己去填补细节。

你的代码运行得慢是因为它使用了O(n^2)的算法，也就是把每个A都和每个B进行比较。

如果你先把listA和listB按id排序（这个操作是O(nlogn)），那么你就可以很轻松地遍历这两个排序后的列表（这个过程是线性的时间复杂度）。

这种方法在处理非常大的数据集时很常见，特别是需要进行外部合并的时候。Mihai的回答更适合内部合并，也就是在内存中通过id对所有东西进行索引。如果你的内存足够大来存放这些额外的结构，并且字典查找是常量时间，那么这种方法可能会更快，而且更简单。:)

举个例子，假设A在排序后有以下的id：

acfgjp

而B在排序后有这些id：

aaaabbbbcccddeeeefffggiikknnnnppppqqqrrr

这个方法有点奇怪，但其实是要保持对A和B的索引（我知道这听起来不太像Python风格）。一开始你会同时查看A中的和B中的。所以你会遍历B，把所有的a都加到你的“things”数组里。等你把B中的a都用完后，就把A中的指针移动到下一个元素c。但是B中的下一个元素是b，它比c小，所以你得跳过这些b。接着你会在B中找到一个c，这样你就可以开始把c的内容加到“things”里。继续这样做，直到两个列表都遍历完。只需要一次遍历。:)