0

すべてのデータがメモリに格納された場合、つまりメディアの速度がはるかに高速になる場合、"SELECT .. WHERE .." クエリ (データのフィルター処理) を実行する最速の方法は何ですか? これまでのところ、私の頭にあるオプションは次のとおりです。

1) b ツリーのようなアルゴリズムですが、それでもインデックスとより大きなスペースが必要になる場合があります

2) 固定長の配列。サイズは小さいですが、遅くなる可能性があります。

速度とサイズの両方が問題である場合、他のより良い方法はありますか

4

1 に答える 1

1

それは、あなたが持っている特定のケースに依存します-どの操作が速く必要か、正確なサイズはどれくらいかなど。いくつかの例：

  1. クエリの場合AND、通常、並べ替えられたリストのセットが維持されます (各機能のリスト)。このデータ構造は転置インデックスと呼ばれ、特定のクエリから関連ドキュメントを取得するために検索エンジンでよく使用されます。(たとえば、Apache Lucene はこのデータ構造を使用します)。
  2. 配列を使用でき、データの繰り返しが必要な場合、配列は基本的に最もキャッシュ効率の高いデータ構造であるため、非常に効率的なアプローチです。配列からの順次読み取りは、ほとんどの場合、他のどの DS よりもはるかに高速です。これは、データを反復する際のボトルネックとなることが多い「ヒット ミス」が最も少ないためです。
  3. たとえば、データが文字列であり、トライや基数ツリーなどの文字列用に設計されたデータ構造を使用して、いくつかの文字列属性 (たとえば、プレフィックス) に従ってフィルター処理する場合、最高のパフォーマンスが得られる可能性があります。

結論: デフォルト ライブラリのパフォーマンスを向上させるためにカスタムメイドの何かを行う場合は、選択したデータ構造を設計する前に、特定の問題の詳細を考慮する必要があります。

于 2012-10-08T10:44:31.247 に答える