如何对大字典进行排序

Question

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

我知道字典太大而无法加载到内存中然后进行排序，但是我怎么能做到这一点呢？

Answer 1

您可以使用有序键/值存储，例如wiredtiger、leveldb、bsddb。它们都支持使用自定义排序功能的有序键。leveldb 是最容易使用的，但如果您使用 python 2.7，bsddb则包含在 stdlib 中。如果您只需要字典排序，您可以使用 rawhashopen函数打开持久排序字典：

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或wiredtiger以提高速度。

要在 bsddb 中按值排序，您必须使用复合键模式或键组合。归根结底是创建一个字典键来保留您要查找的顺序。在此示例中，我们首先将原始 dict 值（以便首先出现小值）与原始 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