私は100文字以上の文字列を持っています。文字列はそれぞれ63文字までです。私は多くのディスクスペースと非常に少ないメモリ(512 MB)を持っています。私は単独で存在を照会し、追加のメタデータを保管する必要はありません。大きな文字列の中に存在を確認する効率的な方法
私の事実上の解決策はBDB btreeです。何か良い選択肢はありますか?私はleveldbとKyoto Cabinetを知っていますが、利点を特定するのに十分に精通していません。
私は100文字以上の文字列を持っています。文字列はそれぞれ63文字までです。私は多くのディスクスペースと非常に少ないメモリ(512 MB)を持っています。私は単独で存在を照会し、追加のメタデータを保管する必要はありません。大きな文字列の中に存在を確認する効率的な方法
私の事実上の解決策はBDB btreeです。何か良い選択肢はありますか?私はleveldbとKyoto Cabinetを知っていますが、利点を特定するのに十分に精通していません。
偽陽性が許容される場合、解決策の1つはbloom filterです。ブルームフィルタはハッシュテーブルと似ていますが、ハッシュ値を使用してバケットのテーブルを索引付けする代わりに、複数のハッシュを使用してビット配列を索引付けします。それらのインデックスに対応するビットがセットされる。次に、文字列がフィルタ内にあるかどうかをテストするために、文字列が再びハッシュされ、対応するインデックスが設定されている場合、文字列はフィルタの "in"になります。
文字列に関する情報は保存されないため、メモリはほとんど使用されませんが、2つの文字列の間に衝突がある場合は、衝突の解決はできません。これは、偽陽性である可能性があることを意味します(フィルタにない文字列が、フィルタ内の文字列と同じインデックスにハッシュする可能性があるため)。しかしながら、偽陰性は存在し得ない。本当にセットに入っている文字列は、ブルームフィルタで検出されます。
fewPythonimplementationsがあります。あなた自身をロールバックすることも難しくありません。 を使って、素早く汚いブルームフィルタを自分でコーディングしたことを思い出しました。
ディスクがたくさんあるとおっしゃいましたか? 1つのオプションは、文字列をネストされたサブディレクトリにファイル名として格納することです。あなたは、直接文字列を使用することができ、次のいずれか
をd/r/e/w/ sears
または文字列のハッシュを取り、同様のプロセスに従うことによってで "シアーズを描いた":
f0/10/fe/6e/20d12ed895c10b93b2f81c6e
という名前の空のファイルを作成します。OSに最適化されたハッシュテーブルベースのインデックス付きNoSQLデータベースと考えることができます。
サイドのメリット:
+1は創造性のためですが、OSを使用して深くネストされたファイルの存在を確認するのは遅くてもかまいません。 – martineau
実際、私はそれについてもっと考えているのですが、なぜネストされたサブディレクトリがたくさんあるのですか?代わりに、各文字列に空のファイルを作成し、それらをすべて単一のディレクトリに格納します。もちろん、ファイルシステムの問題があるかもしれません... – martineau
テストがなければ、遅いかどうかはわかりません。実際には、ファイルシステムに依存してきわめて慎重になる可能性があります。 ディレクトリのサイズが小さいほど、ファイルシステムのほうがはるかに高速です。ほとんどの(すべての)現代のFSは、ディレクトリの参照をうまくキャッシュします。それが入れ子にされたサブディレクトリのモチベーションでした。 –
偽陽性を許容できますか? – senderle
偽陰性は受け入れられません。時々誤検知が起こる可能性があります。 –
これらをすべて 'set'に格納し、必要に応じてOSの仮想メモリマネージャーをディスクにページさせます。 'pickle'を使ってディスクに明示的に保存することもできます。データベースを構築する必要はありません。 – martineau