0

非常に大きなレインボー テーブル ファイル (13GB ファイル) を検索する最良の方法を探しています。これは、次のような CSV スタイルのファイルです。

1f129c42de5e4f043cbd88ff6360486f; somestring
78f640ec8bf82c0f9264c277eb714bcf; anotherstring
4ed312643e945ec4a5a1a18a7ccd6a70; yetanotherstring

... アイデアがわかります - 約 9 億行あり、常にハッシュ、セミコロン、クリア テキスト文字列が含まれています。

したがって、基本的に、プログラムはこのファイルに特定のハッシュが含まれているかどうかを確認する必要があります。

これを行う最速の方法は何ですか？明らかに、ファイル全体をメモリに読み込んで、その上に置くことはできませんstrstr()。

では、これを行う最も効率的な方法は何ですか?

  1. ファイルを 1 行ずつ読み込みますstrstr()。
  2. ファイルのより大きなチャンク (たとえば 10.000 行) を読み取り、strstr()

それとも、このすべてのデータを MySQL データベースにインポートしてから、SQL クエリを介してハッシュを検索する方が効率的でしょうか?

どんな助けでも大歓迎です

4

3 に答える 3

2

それを行う最善の方法は、それを並べ替えてから、二分探索のようなアルゴリズムを使用することです。並べ替えた後、特定のエントリを見つけるのに O(log n) 時間かかります。ここで、n はエントリの数です。アルゴリズムは次のようになります。

  1. 開始オフセットと終了オフセットを保持します。開始オフセットをゼロに、終了オフセットをファイル サイズに初期化します。
  2. start = end の場合、一致はありません。
  3. オフセット (開始 + 終了) / 2 からデータを読み取ります。
  4. 改行が表示されるまで前方にスキップします。(さらに読む必要があるかもしれませんが、ステップ 3 で読むのに適切なサイズ (ほとんどのレコードよりも大きい) を選択すれば、おそらくそれ以上読む必要はありません。)
    • 対象のハッシュが探しているハッシュである場合は、手順 6 に進みます。
    • それ以外の場合、現在のハッシュが探しているハッシュよりも小さい場合は、start を現在の位置に設定し、ステップ 2 に進みます。
    • 現在のハッシュが探しているハッシュよりも大きい場合は、 end を現在の位置に設定し、ステップ 2 に進みます。
  6. セミコロンと末尾のスペースにスキップします。ハッシュされていないデータは、現在の位置から次の改行までになります。

これは、ブレーク付きの while ループに簡単に変換できます。

適切なインデックスなどを使用してMySQLにインポートすると、同様に（またはそれ以上、おそらく適切にパックされているため）効率的なアルゴリズムが使用されます。

于 2013-01-26T07:32:01.130 に答える
0

まず、単一の大きなファイルを65536の小さなファイルに分割します。これにより、ハッシュが0000ファイル内00/00data.txtにある場合、ハッシュがファイル内にある場合など0001になります。ファイル00/01data.txt全体が12 GiBの場合、各ファイルは小さいファイルは（平均で）208KiBになります。

次に、文字列からハッシュを分離します。65536の「ハッシュファイル」と65536の「文字列ファイル」があります。各ハッシュファイルには、残りのハッシュ（最初の4桁は不要になったため、最後の12桁のみ）と、対応する文字列ファイル内の文字列のオフセットが含まれます。これは、（それぞれ平均208 KiBの65536ファイルではなく）それぞれ120KiBの65536ハッシュファイルと100KiBの65536文字列ファイルがあることを意味します。

次に、ハッシュファイルはバイナリ形式である必要があります。12桁の16進数は48ビットです（12 * 8 = 96ビットではありません）。これだけで、ハッシュファイルのサイズが半分になります。文字列が文字列ファイルの4バイト境界に配置されている場合、16ビットの「文字列のオフセット/ 4」で問題ありません（文字列ファイルが256 KiB未満である場合）。ハッシュファイルのエントリは順番に並べ替える必要があり、対応する文字列ファイルは同じ順序にする必要があります。

これらすべての変更の後。ハッシュの上位16ビットを使用して、適切なハッシュファイルを見つけ、ハッシュファイルをロードして、バイナリ検索を実行します。次に（見つかった場合）、ハッシュファイルのエントリから（文字列ファイル内の）文字列の開始のオフセットを取得し、さらにハッシュファイルの次のエントリから次の文字列のオフセットを取得します。次に、文字列ファイルからデータをロードします。正しい文字列の先頭から始まり、次の文字列の先頭で終わります。

最後に、メモリに「ハッシュファイルキャッシュ」を実装します。アプリケーションが1.5GiBのRAMを割り当てることができる場合、ハッシュファイルの半分をキャッシュするにはそれで十分です。この場合（キャッシュされたハッシュファイルの半分）、ディスクからロードする必要があるのは文字列自体（おそらく20バイト未満）だけで、残りの半分は最初にハッシュファイルをキャッシュにロードする必要があります（例：60KiB）。したがって、ルックアップごとに平均して、ディスクから約30KiBをロードすることになります。もちろん、メモリが多いほど良いです（そして少ないほど悪いです）。また、約3 GiBを超えるRAMを割り当てることができる場合は、すべてのハッシュファイルをキャッシュして、一部の文字列のキャッシュについて考え始めることができます。

より高速な方法は、可逆エンコーディングを使用することです。これにより、文字列を整数に変換してから、ルックアップをまったく行わずに整数を元の文字列に戻すことができます。例として; すべての文字列が小文字のASCII文字を使用し、最大である場合。13文字の長さの場合、それらはすべて64ビット整数に変換して戻すことができます（26 ^ 13 <2 ^ 63として）。これにより、別のアプローチが可能になる可能性があります。たとえば、可能な場合はリバーシブルエンコーディング（整数/ハッシュクリアのビット64）を使用します。可逆的な方法でエンコードできない文字列には、ある種のルックアップ（整数/ハッシュのビット64が設定されている）のみを使用します。少しの知識があれば（たとえば、文字列に最適なリバーシブルエンコーディングを慎重に選択するなど）、13GiBファイルのサイズを「RAMに簡単に収まるほど小さい」サイズに縮小できます。

于 2013-01-26T10:17:06.420 に答える
0

最後のソリューションは、パフォーマンスの最適化全体をデータベースに移行するときに実装するのが最も簡単なソリューションかもしれません (通常、それらはそのために最適化されています)。

strstr文字列を検索するため、ここでは役に立ちませんが、特定の形式を知っているので、ジャンプしてより目的に合わせて比較できます。strncmp、およびに関することstrchr。

1 行を読み取るためのオーバーヘッドは非常に高くなります (ファイル IO の場合によくあることです)。したがって、より大きなチャンクを読み取り、そのチャンクで検索を実行することをお勧めします。別のスレッドで次のチャンクを読み取り、そこでも比較を行うことで、検索を並列化することも考えます。

標準の C ファイル API の代わりにメモリ マップド IO を使用することも考えられます。これを使用すると、コンテンツ全体をオペレーティング システムにロードしたままにしておくことができ、自分でキャッシュを気にする必要がなくなります。

もちろん、アクセスを高速化するためにデータを再構築することも役立ちます。たとえば、パディング バイトを挿入して、すべてのデータセットが同じ長さになるようにします。これにより、n 番目のエントリの位置を簡単に計算できるため、データ ストリームへの「ランダムな」アクセスが提供されます。

于 2013-01-26T07:34:52.983 に答える