代码之家 › 专栏 › 技术社区 › Nathan

python中的就地字典反转

generator hashtable list python

4

Nathan · 技术社区 · 15 年前

我需要颠倒一个列表字典,我不知道如何用英语准确地解释它,所以这里有一些代码可以满足我的需要。只是需要太多的记忆。

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

原件是列表的dict,结果是列表的dict。这“颠倒”了它。

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

我需要知道这是否可以在适当的地方完成,因为我目前的策略是用我正在使用的字典来超过我机器上的物理内存量。你能想出一个办法用发电机来做吗?

4 回复 | 直到 9 年前

1

5

John La Rooy 15 年前

这并不是就地完成的,而是使用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

2

Alexander Lebedev 15 年前

如果算法正确的话,在现代机器上,可能需要数百万个条目来耗尽RAM。假设这样,您必须使用一些持久性存储,以便数据一次只处理块。为什么不使用带有2列的简单数据库表来存储dict?

然后,您可以使用任一列作为键,方法是选择 order by 使用简单的python代码对其他列中所需的列和值进行分组。

3

1

David Z 15 年前

实际上,我看不出你当前算法的内存使用有任何改进。您确实使用迭代器,而不是直接创建新的列表/字典,因此唯一重要的内存使用来自原始字典和新的反向字典。

如果您没有足够的RAM来使用实际使用的字典来运行这个算法,那么我所能想到的就是避免将原来的dict和颠倒的dict同时保存在内存中。一种方法是在将项目添加到倒置的dict时从原始dict中删除项目,可以这样做:

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存储到磁盘上,一次只加载其中的一部分,所以您可能需要为此编写自己的代码。

4

0

Wai Yip Tung 15 年前

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

我想你想做的事情可以称之为 Inverted index
我不相信这能在适当的地方完成,我也不认为这是正确的策略。您应该看看基于磁盘的解决方案。可能对原始数据结构进行排序或组织,将其写出一个或多个文件,然后将其读回并合并到最终的数据结构中。