python - Python 中的就地字典反转

Question

我需要反转列表字典，我不知道如何用英语准确解释它，所以这里有一些代码可以完成我想要的。它只是占用太多内存。

def invert(oldDict):
    invertedDict = {}
    for key,valuelist in oldDict.iteritems():
        for value in valuelist:
            try:
                entry = invertedDict[value]
                if key not in entry:
                    entry.append(key)
            except KeyError:
                invertedDict[value] = [key]
    return invertedDict

原始是列表字典，结果是列表字典。这会“反转”它。

test = {}
test[1] = [1999,2000,2001]
test[2] = [440,441]
test[3] = [440,2000]

print invert(test)

这给出:

{2000: [1, 3], 2001: [1], 440: [2, 3], 441: [2], 1999: [1]}

我需要知道这是否可以就地完成，因为我目前的策略是超过我正在使用的字典在我机器上的物理内存量。你能想出一种方法来使用生成器吗？

Answer 1

这不是原地做，而是使用 popitem() 消耗 oldDict

from collections import defaultdict
def invert(oldDict):
    invertedDict = defaultdict(list)
    while oldDict:
        key, valuelist = oldDict.popitem()
        for value in valuelist:
            invertedDict[value].append(key)
    return invertedDict

我有一种感觉，除非大小增加，否则 dict 永远不会调整大小，因此您可能需要定期添加和删除虚拟项。参见 Shrinkage rate

from collections import defaultdict
def invert(oldDict):
    invertedDict = defaultdict(list)
    i=0
    while oldDict:
        key, valuelist = oldDict.popitem()
        for value in valuelist:
            invertedDict[value].append(key)
        i+=1
        if i%1000==0: # allow the dict to release memory from time to time
            oldDict[None]=None
            del oldDict[None]
    return invertedDict