python - 大きなリストを計算する方法

Question

ハッシュのさまざまなスキームの衝突をカウントする必要があるとします。入力シーケンスの要素数は 1e10^8 以上です。これを分析的にカウントする方法がわからないので、総当たりを使用します。

このハッシュのリストを RAM に保持しないことは明らかです。それは私のニーズに合わせてコードを書くための最良の方法ですか? データベースなどにダンプする必要がありますか？どのライブラリを使用することをお勧めしますか?

ありがとうございました！

Answer 1

ファイルのセットを保持することをお勧めします。各ファイルには、それに含まれるハッシュのプレフィックスを付けて名前を付けます (たとえば、プレフィックスの長さを 6 にすると、名前の付いたファイルにffa23b.txtは、ハッシュ、、などが含まれる可能性がありますffa23b11d4334) ffa23b712f3。ハッシュを読み取るたびに、ハッシュの最初の N 文字に対応する名前でファイルに追加します。

ブルーム フィルターを使用して、すべてのハッシュをメモリに格納することなく、ハッシュの大部分を一意としてすばやく除外することもできます。そうすれば、ブルーム フィルターに対するチェックで、以前に実際に見たことがある可能性があることが示されている場合にのみ、特定のプレフィックス ファイルの検索にフォール バックする必要があります。これはめったに発生しません。

Answer 2

簡単な答え: 数ギガバイトの RAM がある場合は、Python 辞書を使用します。これが実装する最も簡単な方法です (そしておそらく実行が高速です)。次のようなことができます。

>>> mydict = {}
>>> for i in some_iterator:
        mydict[i] = ''

次に、キーがマッピングに存在するかどうかを確認します。

>>> 0 in mydict
True

>>> 123456789 in mydict
False

長い答え: GDBM (Berkeley DB のように見えます) や別の種類のデータベースなどの永続的なキー値ストアを使用できますが、このアプローチはPython 辞書だけを使用するよりもはるかに遅くなります。一方、このアプローチでは、持続性があります (必要な場合)。

GDBM は、単一のファイルに保持されるディクショナリ (キーと値のストア) として理解できます。次のように使用できます。

>>> import gdbm
>>> kv = gdbm.open('my.db', 'cf')

次に、ファイルmy.dbが作成されます (意味を理解するには、 Python GDBM のドキュメントcfを参照してください)。

ただし、キーと値として文字列のみをサポートするため、いくつかの制限があります。

>>> kv[0] = 0
Traceback (most recent call last)
[...]
TypeError: gdbm mappings have string indices only

>>> kv['0'] = 0
Traceback (most recent call last)
[...]
TypeError: gdbm mappings have string elements only

>>> kv['0'] = '0'

ダミーの値を持つすべてのキーを gdbm データベースに入力できます。

>>> for i in some_iterator:
        kv[str(i)] = ''

次に、キーがマッピングに存在するかどうかを確認します。

>>> '0' in kv
True

>>> '123456789' in kv
False