大数据集的Python defaultdict

Question

我正在使用 defaultdict 来存储数百万个短语，所以我的数据结构看起来像 mydict['string'] = set(['other', 'strings'])。它似乎适用于较小的集合，但当我按下任何超过 1000 万个键时，我的程序就会崩溃，并显示有用的消息 Process killed。我知道 defaultdict 占用大量内存，但是否有使用 defaultdict 进行存储的优化方法，或者我是否必须查看其他数据结构，如 numpy 数组？

谢谢

Answer 1

如果您打算将单个 Python 进程留在内存中，那么您将不得不放弃 dict 数据类型——正如您所指出的，它具有出色的运行时性能特征，但它需要大量内存才能让您到达那里。

真的，我认为@msw 的评论和@Udi 的回答是正确的——要扩展，您应该查看磁盘上或至少某种进程外存储，可能 RDBMS 是最简单的开始吧。

但是，如果您确定需要保留在内存中和进程中，我建议您使用排序列表来存储您的数据集。您可以在 O(log n) 时间内进行查找，在常数时间内进行插入和删除，您可以自己包装代码，这样使用起来就很像 defaultdict。这样的事情可能会有所帮助(除了底部的测试之外没有调试):

import bisect

class mystore:
    def __init__(self, constructor):
        self.store = []
        self.constructor = constructor
        self.empty = constructor()

    def __getitem__(self, key):
        i, k = self.lookup(key)
        if k == key:
            return v
        # key not present, create a new item for this key.
        value = self.constructor()
        self.store.insert(i, (key, value))
        return value

    def __setitem__(self, key, value):
        i, k = self.lookup(key)
        if k == key:
            self.store[i] = (key, value)
        else:
            self.store.insert(i, (key, value))

    def lookup(self, key):
        i = bisect.bisect(self.store, (key, self.empty))
        if 0 <= i < len(self.store):
            return i, self.store[i][0]
        return i, None

if __name__ == '__main__':
    s = mystore(set)
    s['a'] = set(['1'])
    print(s.store)
    s['b']
    print(s.store)
    s['a'] = set(['2'])
    print(s.store)