如何对大型字典进行排序

Question

我有一个使用大型（〜14GB）文本文件的python脚本。我最终得到了一个键和值的字典，但是当我尝试按值排序字典时，出现内存错误。

我知道字典太大，无法载入内存然后排序，但我怎么能去完成这个？

Answer 1

您可以使用像wiredtiger，leveldb，bsddb这样的有序键/值存储。它们都支持使用自定义排序功能的有序键。 leveldb是最容易使用的，但如果你使用python 2.7,bsddb is included in the stdlib。如果你只需要字典排序，你可以使用原始hashopen函数打开一个持久分类词典：

from bsddb import hashopen 


db = hashopen('dict.db') 
db['020'] = 'twenty' 
db['002'] = 'two' 
db['value'] = 'value' 
db['key'] = 'key' 

print(db.keys()) 

此输出

>>> ['002', '020', 'key', 'value'] 

不要忘了你的工作后关闭数据库：

db.close() 

请注意，hashopen配置可能不适合您的需要。在这种情况下，我建议您使用leveldb，它具有简单的API或有线速度。

为了通过值bsddb订购，则必须使用复合键图案或键组合物。归结起来就是创建一个字典密钥，它可以保持您寻找的顺序。在这个例子中，我们首先包的原始字典值（使得小的值首先出现）与原来的dict键（使得bsddb密钥都是唯一的）：

import struct 
from bsddb import hashopen 

my_dict = {'a': 500, 'abc': 100, 'foobar': 1} 

# insert 
db = hashopen('dict.db') 
for key, value in my_dict.iteritems(): 
    composite_key = struct.pack('>Q', value) + key 
    db[composite_key] = '' # value is not useful in this case but required 
db.close() 


# read 
db = hashopen('dict.db') 
for key, _ in db.iteritems(): # iterate over database 
    size = struct.calcsize('>Q') 
    # unpack 
    value, key = key[:size], key[size:] 
    value = struct.unpack('>Q', value)[0] 
    print key, value 
db.close() 

此输出以下：

foobar 1 
abc 100 
a 500