LARGE辞書をソートする方法

Question

大きな（〜14GB）テキストファイルで動作しているpythonスクリプトがあります。私はキーと値の辞書で終わるが、値で辞書をソートしようとするとメモリエラーが発生する。

私は辞書が大きすぎてメモリに読み込んで並べ替えることができないと知っていますが、これを達成するにはどうすればいいですか？

Answer 1

wiredtiger、leveldb、bsddbのような順序付けられたキー/値ストアを使用できます。それらのすべてはカスタムソート機能を使用して順序キーをサポートしています。 leveldbは最も使いやすいですが、Python 2.7を使用している場合は、bsddb is included in the stdlibです。あなたの仕事の後デシベルを閉じることを忘れないでください

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

を出力します：

あなただけが永続的なソートされた辞書を開くために、生 hashopen機能を使用することができますソート辞書式が必要な場合

db.close() 

hashopenの設定があなたのニーズに合わない可能性があることに注意してください。この場合は、速度を上げるために単純なAPIまたはワイヤータイガーを持つleveldbを使用することをお勧めします。 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 

（小さい値が最初に表示されるように）この例では、元のdictのキー（はbsddbキーが一意になるように）して初のオリジナル辞書値をパック