用于大型数据集的Python defaultdict

Question

我使用defaultdict来存储数百万个短语，所以我的数据结构看起来像mydict['string'] = set(['other', 'strings'])。对于较小的集合，它似乎可以正常工作，但是当我碰到任何超过1000万个键时，我的程序就会崩溃，并显示一个有用的消息Process killed。我知道defaultdict是内存密集型的，但是有没有一种使用defaultdicts进行存储的优化方法，还是需要查看其他数据结构，如numpy array？在

谢谢你

Answer 1

也许可以试试redis的set数据类型：

Redis Sets are unordered collections of strings. The SADD command adds new elements to a set. It's also possible to do a number of other operations against sets like testing if a given element already exists...

从这里：http://redis.io/topics/data-types-intro

redis-py支持这些命令。在

Answer 2

如果你打算用一个Python进程留在内存中，那么你将不得不放弃dict数据类型，正如你所说的，它有很好的运行时性能特性，但它使用大量内存来实现这一点。在

真的，我认为@msw的评论和@Udi的回答都恰到好处，你应该看看磁盘上的或者至少是某种进程外存储，也许RDBMS是最容易实现的。在

但是，如果您确定需要保留在内存中并处于进程中，我建议使用已排序的列表来存储数据集。您可以在O（logn）时间内进行查找，在恒定时间内执行插入和删除，并且您可以自己打包代码，这样使用情况看起来非常像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)