15

最も効率的な方法を解決するためのガイダンスを探しているという問題があります。サイズが 3 文字から 70 文字までの 2 億文字列のデータがあります。文字列は、文字の数字と、ダッシュやアンダースコアなどのいくつかの特殊文字で構成されます。文字列全体または文字列内の任意の部分文字列をすばやく検索できる必要があります (部分文字列の最小サイズは 3 です)。ここでは、1 秒未満と定義されています。

これでの最初のカットとして、次のことを行いました。

  1. 38 個のインデックス ファイルを作成しました。インデックスには、特定の文字で始まるすべての部分文字列が含まれています。最初の 4MB には 100 万個のハッシュ バケットが含まれます (ハッシュ チェーンの開始)。インデックスの残りの部分には、ハッシュ バケットからのリンク リスト チェーンが含まれます。私のハッシュは非常に均等に分散されています。100 万個のハッシュ バケットが RAM に保持され、ディスクにミラーリングされます。

  2. 文字列がインデックスに追加されると、重複しない (それ自体の中で) 3-n 文字の部分文字列に分割されます (n が文字列-1 の長さの場合)。たとえば、"apples" は "A" インデックスに pples,pple,ppl,pp として格納されます (部分文字列は "L" および "P" インデックスにも格納されます)。

検索/追加サーバーは (C++ で) デーモンとして実行され、チャンピオンのように機能します。通常の検索時間は 1/2 秒未満です。

問題はプロセスのフロントエンドにあります。通常、一度に 30,000 個のキーを追加します。プロセスのこの部分には永遠に時間がかかります。ベンチマークとして、180,000 個の可変長キーの空のインデックスへの読み込み時間は約 3 時間半です。

このスキームは、ロード時間が非常に長いことを除いて機能します。

最適化に夢中になる (またはしようとする) 前に、この問題を解決するためのより良い方法があるかどうか疑問に思っています。前後のワイルドカード検索 (つまり、DBMS の '%ppl%' のような文字列) は、このような大規模なデータセットでは驚くほど遅くなります (たとえば、MySQL では数時間のオーダー)。したがって、DBMS ソリューションは問題外のようです。通常の単語ではなく、実際の単語で構成されているかどうかに関係なく文字列を扱っているため、全文検索は使用できません。

4

2 に答える 2

1

あなたの説明から、I/O を処理し、膨張した文字列をハードディスクにミラーリングしているため、データのロードにはずっと時間がかかります。これは、主にディスクへのデータの読み取りと書き込みの方法に応じて、間違いなくボトルネックになります。

mmapいくつかの LRU ポリシーを使用すると、実行時間が改善される可能性があります。データを複製するという考えは検索を高速化することだと確信していますが、使用しているように見えるマシンは 1 台だけであるため、ボトルネックはメモリ検索から I/O に飛び込むことになります。リクエスト。

あなたが興味を持っていないかもしれない別の解決策 - それはうんざりするほど面白くて不安でもあります (: --, データを複数のマシンに分割することです。データを構造化した方法を考慮すると、実装自体に少し時間がかかる場合がありますの時間ですが、それは非常に簡単です。

  • 各マシンは、に近いものを使用して選択されたセット バケットによって責任を負いhash_id(bucket) % num_machinesます。
  • 挿入は各マシンからローカルで実行されます。
  • アプリケーションがインタラクティブでない場合、検索は何らかのタイプのクエリアプリケーションによってインターフェース化されるか、単純に一連のクエリにクラスター化されます。
  • ノードから開始リクエストを送信し、別のノードにリクエストを転送する可能性があることを考慮して、検索ではインターフェースが分散されている場合もあります (過度の I/O オーバーヘッドを避けるために、クラスター化されたリクエストも同様です)。

もう1つの良い点は、あなたが言ったように、データが均等に分散されていることです-すでに\ o /; これは通常、分散実装の最も厄介な部分の 1 つです。さらに、データのサイズが大きくなるたびに別のマシンを追加できるため、これは非常にスケーラブルです。

于 2013-01-22T20:53:17.343 に答える
1

すべてを 1 回のパスで行うのではなく、38 回のパスで問題を解決します。

180,000 個の文字列をそれぞれ読み取ります。各文字列で "A" を見つけ、"A" ハッシュ テーブルにのみ書き込みます。完了したら、「A」ハッシュ テーブルの完成した結果全体をディスクに書き込みます。（「A」ハッシュテーブル全体をメモリに保存するのに十分なRAMを用意してください。そうでない場合は、より小さなハッシュテーブルを作成してください。つまり、開始文字のペアで38 ^ 2ハッシュテーブルを持ち、1444個の異なるテーブルを持ちます。プレフィックスがどれだけ一般的であるかに基づいて、ハッシュ テーブルがキーオフする文字数を動的に変更することさえできるため、それらはすべて適度なサイズです.そのようなプレフィックスの長さを追跡することは高価ではありません.

次に、「B」を探して、180,000 個の文字列をそれぞれ読み取ります。等。

私の理論では、大規模なテーブルのキャッシュがスラッシングされているため、速度が低下しているということです。

次に役立つ可能性があるのは、テーブルのサイズを縮小するために、ハッシュを実行する文字列の長さを制限することです。

長さ 70 の文字列の長さ 3 から 70 の 2278 個の部分文字列すべてを実行する代わりに、ハッシュの長さを 10 文字に制限した場合、長さ 3 から 10 の 508 個の部分文字列しかありません。長さは 10 よりも長くなります。繰り返しますが、ハッシュの長さを動的にすることもできます。長さ X ハッシュには、「文字列が X より長い場合は長さ X+Y ハッシュを試してください。これは一般的すぎます。それ以外の場合は、単にハッシュを終了します。これにより、場合によってはルックアップが遅くなるという犠牲を払って、テーブル内のデータ量を減らすことができます。

于 2013-01-22T21:25:39.080 に答える