文字列メンバーの条件に一致するコレクションからオブジェクトを検索する最速の方法

StackOverflow https://stackoverflow.com/questions/97329

質問

コレクション (配列、汎用リスト、またはその他のもの) があるとします。 最速の この問題の解決策) 特定のクラス、それをそう呼びましょう ClassFoo:

class ClassFoo
{
    public string word;
    public float score;
    //... etc ...
}

コレクションには 50,000 個ほどのアイテムがあり、すべてメモリ内にあると仮定します。ここで、たとえば次のように、bar メンバーの条件に従うコレクション内のすべてのインスタンスをできるだけ早く取得したいと考えています。

List<ClassFoo> result = new List<ClassFoo>();
foreach (ClassFoo cf in collection)
{
    if (cf.word.StartsWith(query) || cf.word.EndsWith(query))
        result.Add(cf);
}

できるだけ早く結果を得るにはどうすればよいですか?高度なインデックス作成手法とデータ構造を考慮する必要がありますか?

この問題のアプリケーション ドメインは、クエリを取得し、結果として提案のコレクションを提供するオートコンプリーターです。条件がこれ以上複雑になることはないと仮定します。また、大量の検索が行われると想定します。

役に立ちましたか？

解決

条件句には「何でも」を指定できるという制約があるため、リスト全体をスキャンして条件を適用することに制限されます。

条件句に制限がある場合は、クエリをより効率的に処理するためにデータを整理することを検討できます。

たとえば、「byFirstLetter」辞書を使用したコード サンプルは、「endsWith」クエリにはまったく役に立ちません。

したがって、最終的には、そのデータに対してどのようなクエリを実行するかによって決まります。

データベースでは、この問題は「クエリ オプティマイザー」の負担となります。一般的なデータベースでは、インデックスのないデータベースの場合、明らかにすべてのクエリがテーブル スキャンになります。テーブルにインデックスを追加すると、オプティマイザはそのデータを使用して、より高度なクエリ プランを作成し、より適切にデータを取得できるようになります。それは本質的にあなたが説明している問題です。

クエリのタイプのより具体的なサブセットを取得したら、どの構造が最適であるかについてより適切な決定を下すことができます。また、データ量も考慮する必要があります。それぞれ 100 バイト未満の 10 個の要素のリストがある場合、データ量が非常に少ないため、すべてをスキャンするのが最も速い方法である可能性があります。明らかに、これは 100 万要素まで拡張できませんが、賢いアクセス技術であっても、セットアップ、メンテナンス (インデックスのメンテナンスなど)、およびメモリのコストがかかります。

編集, 、コメントに基づいて

オート コンプリーターの場合、データが静的な場合は、データを並べ替えて二分検索を使用します。実際にはそれ以上速くなることはありません。

データが動的である場合は、バランスのとれたツリーに保存し、それを検索します。これは事実上二分探索であり、データをランダムに追加し続けることができます。

それ以外のものは、これらの概念に特化したものです。

他のヒント

var Answers = myList.Where(item => item.bar.StartsWith(query) || item.bar.EndsWith(query));

私の意見ではこれが最も簡単で、かなり早く実行できるはずです。

わかりません...実際にできることはルールを最適化することだけであり、それは最速にする必要がある部分です。より多くのハードウェアを投入することなしにループを高速化することはできません。

複数のコアまたはマシンがある場合は、並列化できます。

今は Java を使いこなしていませんが、次のことを考えてみます。

リストはどのように作成していますか?おそらく、比較時間を短縮する方法で、すでに注文されたものを作成できるでしょう。

コレクションに対して直線ループを実行するだけの場合、コレクションを配列として保存する場合とリンク リストとして保存する場合に大きな違いは見られません。

結果を保存する場合、結果を収集する方法に応じて、構造が違いを生む可能性があります (ただし、Java の汎用構造が賢明であると仮定すると、違いは生じません)。先ほども言いましたが、私は Java については十分ではありませんが、汎用のリンク リストにはテール ポインタが保持されると考えています。この場合、特に違いはありません。基礎となる配列とリンク リストの実装、およびそれがバイト コード内でどのように検索されるかについてより詳しい人なら、テール ポインタを使用してリンク リストに追加するのと、配列に挿入するのとどちらが速いかがわかるでしょう (私の推測では、配列だと思います) ）。一方、配列を使用する場合は、結果セットのサイズを把握するか、ストレージ領域を犠牲にして、反復処理中のコレクション全体と同じ大きさにする必要があります。

どの比較が真である可能性が最も高いかを判断し、それを最初に実行することで比較クエリを最適化することも役立ちます。つまり:一般に、コレクションのメンバーがクエリで開始される確率が 10%、メンバーがクエリで終了する確率が 30% である場合、最初に終了比較を実行する必要があります。

特定の例では、クエリで始まる最初の項目にバイナリチョップし、そうでない次の項目に到達したときに早期に終了できるため、コレクションを並べ替えると役立ちます。2 番目の句の各文字列の逆順に並べ替えたコレクション項目へのポインタのテーブルを作成することもできます。

一般に、クエリの構造が事前にわかっている場合は、コレクションを適切に並べ替えることができます (または、複数の句がある場合は、コレクションに対して並べ替えられたインデックスを複数作成できます)。そうしないと、線形検索以上に優れた検索を実行できなくなります。

リストに一度データを入力してから、多数の検索 (数千件以上) を実行するものであれば、値で始まる/終わる値を実際の値にマッピングする、ある種の検索辞書を作成できます。これは高速な検索になりますが、より多くのメモリを使用することになります。それほど多くの検索を行っていない場合、または少なくとも半頻度でリストを再作成することがわかっている場合は、CQ が提案した LINQ クエリを使用するでしょう。

何らかのインデックスを作成すると、速度が向上する可能性があります。

次のようなインデックスを構築できます。

Dictionary<char, List<ClassFoo>> indexByFirstLetter;
foreach (var cf in collection) {
  indexByFirstLetter[cf.bar[0]] = indexByFirstLetter[cf.bar[0]] ?? new List<ClassFoo>();
  indexByFirstLetter[cf.bar[0]].Add(cf);
  indexByFirstLetter[cf.bar[cf.bar.length - 1]] = indexByFirstLetter[cf.bar[cf.bar.Length - 1]] ?? new List<ClassFoo>();
  indexByFirstLetter[cf.bar[cf.bar.Length - 1]].Add(cf);
}

次に、それを次のように使用します。

foreach (ClasssFoo cf in indexByFirstLetter[query[0]]) {
  if (cf.bar.StartsWith(query) || cf.bar.EndsWith(query))
    result.Add(cf);
}

これで、例のように多くの ClassFoo をループする必要はなくなる可能性がありますが、やはりインデックスを最新の状態に保つ必要があります。より高速であるという保証はありませんが、より複雑であることは間違いありません。

場合によります。すべてのオブジェクトは常にメモリにロードされるのでしょうか?ロードできるオブジェクトには有限の制限がありますか?クエリではまだロードされていないオブジェクトを考慮する必要がありますか?

コレクションが大きくなる場合は、必ずインデックスを使用します。

実際、コレクションが任意のサイズにまで拡大する可能性があり、すべてをメモリに収めることができるかどうかわからない場合は、ORM、インメモリ データベース、または別の組み込みデータベースを検討します。ORM の場合は DevExpress の XPO、メモリ内データベースの場合は SQLite.Net が思い浮かびます。

ここまでやりたくない場合は、クラス参照にマッピングする「bar」メンバー参照で構成される単純なインデックスを作成します。

考えられる基準のセットが固定されており小さい場合は、リスト内の各要素にビットマスクを割り当てることができます。ビットマスクのサイズは、一連の基準のサイズです。要素を作成するかリストに追加するときは、その要素がどの基準を満たしているかを確認し、この要素のビットマスクに対応するビットを設定します。リストの要素を照合することは、そのビットマスクをターゲットのビットマスクと照合するのと同じくらい簡単です。より一般的な方法はブルーム フィルターです。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top