2

+5Mの静的レコードが配置されたデータベーステーブルがあります。単純な構造:(intの開始、intの終了、intの結果)。だから私は特定のINTを持っていて、それに対応するresult(int)を見つける必要があります。現在、ルックアップテーブルはDBにありますが、メモリ内に存在する必要があります。ほとんどの場合、データベースにアクセスできない環境に存在します。

私のソリューションでは、1秒あたり数千のトランザクションを処理する必要があるため、データベースにアクセスせずに、メモリ内で超高速にこのロジックを実行する必要があります。セットのサイズは50MBを少し超えるので、この投稿に従って、すべてをメモリに投入し、範囲ルックアップを実行できます。C#で範囲ルックアップを実行する-実装方法。しかし、私はそれがそのような規模でどのように機能するかわかりません。

  • 「起動時に」そのテーブルをプリロードしますか?しばらく時間がかかる場合があります。
  • テーブルをいくつかの.datファイルにロードし、実行時に非常に効率的なルックアップを行う方法はありますか?

ところで、私はAzureを使用していますが、ストレージテーブルを使用するとルックアップに役立つかどうかわかりません...

4

3 に答える 3

4

二分探索は超高速です。5,000万レコードの二分探索では、27回の比較で答えを見つけることができます。それをメモリにロードし、リンクした範囲ルックアップを使用するだけです。

遅い場合は、最適化を開始してください。

  • Rangeオブジェクトをクラスではなくstructに変更します
  • 独自のバイナリ検索アルゴリズムを手動でコーディングします。このアルゴリズムは、(a)を呼び出す代わりに、等式比較器を直接実装し、IEqualityComparer(b)ポインターやその他の安全でないトリックを使用して、検索中に配列境界チェックを無効にします。
于 2013-03-07T03:33:23.753 に答える
2

リンク先の範囲ルックアップコードはバイナリ検索を実行するため、パフォーマンスはになりますO(log n)。範囲ルックアップの場合よりもうまくいくとは思いません。のHashSet<T>ルックアップはO(1)ですが、範囲ルックアップにその構造を使用することはできません。

500万レコードは実際には膨大な量ではありません。リンク先のコードを使用して概念実証を本番環境で使用するハードウェアに実装し、パフォーマンスを測定することをお勧めします。

于 2013-03-07T03:32:50.770 に答える
0

確かにそれをシーケンシャルファイルに入れて、起動時にロードすることができます。50MBは1秒以内にディスクから外れます。また、テキストファイルとして解析する必要がある場合でも、もう1秒でテーブルを作成できるはずです。2 GHz(またはそれ以上)のプロセッサで処理している場合、500万レコードはそれほど大きくありません。

リストの二分探索はO(log n)であるため、検索ごとに実行するプローブの最大数は24です。

このような負荷テストを行うのは簡単なはずです。スピンアップして、たとえば1,000,000回のルックアップにかかる時間を確認します。何かのようなもの:

var clock = Stopwatch.StartNew();
for (int i = 0; i < NumIterations; ++i)
{
    int val = GetRandomValueToSearchFor(); // however you do that
    Ranges.BinarySearch(val, RangeComparer);
}
clock.Stop();
// time per iteration is clock.TotalMilliseconds/NumIterations

それはあなたが物事を照会することができる絶対的な最速を理解することを可能にします。1秒あたり数千のトランザクションで問題ないと思います。

于 2013-03-07T03:34:48.490 に答える