问python基于键匹配合并字典的最快方法
EN

Stack Overflow用户

提问于 2011-09-06 23:34:05

回答 3查看 3.1K关注 0票数 3

我有两个字典清单。列表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)

python

dictionary

回答 3

Stack Overflow用户

回答已采纳

发布于 2011-09-07 00:00:39

这里有一种可能会有帮助的方法。我会让你来填写细节的。

您的代码很慢，因为它是一个O(n^2)算法，将每个A与每个B进行比较。

如果您首先按id对listA和listB中的每一个进行排序(这些操作都是O(nlogn))，那么您可以轻松地迭代A和B的排序版本(这将是线性时间)。

当您必须对非常大的数据集进行外部合并时，这种方法很常见。Mihai的答案更适合于内部合并，在内部合并中，您只需通过id (在内存中)对所有内容进行索引。如果您有足够的内存来保存这些额外的结构，并且字典查找的时间不变，那么这种方法可能会更快，更不用说更简单了。:)

举个例子，假设A在排序后有以下ids

acfgjp

B有这些ids，同样是在排序之后

aaaabbbbcccddeeeefffggiikknnnnppppqqqrrr

奇怪的是，这个想法是为了将索引保存到A和B中(我知道这听起来不是很Pythonic式的)。首先，您在A中查看a，在B中查看a。因此，您遍历B，将所有的a添加到a的"things“数组中。一旦你用完了B中的A，你就会在A中上移一个，变成c。但是B中的下一项是b，它比c小，所以你必须跳过b。然后你得到了B中的c，所以你可以开始添加c的"things“。继续这样，直到两个列表都用完了。就一次传球。:)

票数 1

Stack Overflow用户

发布于 2011-09-06 23:53:58

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)

基本上，它通过“预测”listB中的哪些字典与每个“ID”匹配，从而避免为listA中的每个字典遍历listB中的每个字典。

票数 4

Stack Overflow用户

发布于 2011-09-07 01:00:33

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