python - 避免循环并提高性能以更新字典

Question

我有一个形式的字典:

dict1[element1] : reference1

dict1[element2] : reference2

dict1[element3] : reference2

有些元素具有相同的引用(如 element2 和 element3 有)。 我需要将其转换为具有以下形式的字典:

dict2[reference1] : [element1]

dict2[reference2] : [element2,element3]

为了得到这个我写了:

dict2=dict()
for key in dict1:
    UpdateDict(dict2,dict1[key],key)

def UpdateDict(Dict,Key,Entry):
    Keys = list(Dict.keys())
    if Key in Keys:
        Dict[Key].append(Entry)
        return
    else:
        Item = list()
        Item.append(Entry)
        Dict[Key] = Item
    return

这在 dict1 不是很大之前工作正常，但如果 dict1 很大(大约 1000 个键)，则需要数小时才能获得结果。

有没有更快的方法？

Answer 1

这个:

Keys = list(Dict.keys())
if Key in Keys:
    ...

可能是罪魁祸首。它将 O(1) 查找(if Key in Dict:)转换为 O(n) 查找。这加上每个键的单函数调用的开销确实是次优的。

一个更简单的解决方案是使用 collections.defaultdict:

from collections import defaultdict

def revindex(dic):
    rev = defaultdict(list)
    # nb for py2.7 use `iteritems()` instead
    for k, v in dic.items():
        rev[v].append(k)
    return rev


dict2 = revindex(dict1)