Python中的原地字典反转

Question

Python中的原地字典反转

4

我需要反转一个列表字典，不知道用英语怎么解释，这里有一些代码可以实现我想要的功能。但是它占用了太多的内存。

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]}

我需要知道是否可以就地完成此操作，因为我目前的策略使用的字典已超出了我的机器可用的物理内存。您能否考虑使用生成器来完成此操作？

- Nathan

1

你尝试过使用 shelve 吗？ - S.Lott

我不知道shelve，谢谢。我猜既然操作它们，新旧字典都不需要完全加载？ - Nathan

shelve 只能使用字符串作为键。不过你可以绕过这个限制。 - John La Rooy

4个回答

2

如果算法正确，现代机器上运行数百万个条目可能需要很长时间才会耗尽RAM。假设这一点，您必须使用一些持久存储器仅逐块处理数据。为什么不使用只有2列的简单数据库表来存储字典？

然后您可以使用任何一列作为关键字，通过在所需列上选择 order by 并使用简单的python代码对其他列的值进行分组。

- Alexander Lebedev

我想将来会使用 shelve，但现在 gnibbler 的技巧实际上很有效。 - Nathan

1

我实际上并没有看到任何可以显著改善您当前算法的内存使用的方法。您确实使用了迭代器而不是直接创建新的列表/字典，因此唯一显著的内存使用来自原始字典和新的反转字典。

如果您没有足够的RAM来运行实际使用的字典的算法，我所能想到的就是以某种方式避免同时在内存中保留原始字典和反转字典。一种方法是在将它们添加到反转字典中时从原始字典中删除项目，可以像这样完成：

def invert(old_dict):
    inverted = collections.defaultdict(list)
    while old_dict:
        k,v = old_dict.popitem()
        for vi in v:
            inverted[vi].append(k)
    return inverted

（请注意，我还使用了defaultdict来简化代码，但如果您真的需要一个纯粹的dict而不是子类，您可以像最初使用try/except一样做些什么）

如果您想在算法完成后保留原始和反转字典，我所能想到的就是将它们存储在磁盘文件中，并找到一些方法只加载一部分。我不知道有哪个标准的Python模块能够将dict存储到磁盘并一次只加载一部分，因此您可能需要编写自己的代码。

- David Z

0

我没有直接的答案。这是我的一些想法。

我认为你想做的可以称为倒排索引
我不相信它可以原地完成，也不认为这是正确的策略。你应该考虑基于磁盘的解决方案。也许对原始数据结构进行排序或组织，将其写入一个或多个文件，然后读取它们并将它们合并到最终的数据结构中。

- Wai Yip Tung

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- John La Rooy · Accepted Answer

这并不是在原地进行操作，而是通过使用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

我有一种感觉，字典在大小不增加的情况下永远不会被重新调整大小，因此您可能需要定期添加和删除虚拟项。请参阅“缩小率”（Shrinkage rate）：http://svn.python.org/projects/python/trunk/Objects/dictnotes.txt

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