1

特定のクラスのコレクション (配列、一般的なリスト、またはこの問題に対する最速ClassFooの解決策であるもの) があるとします。それを呼び出しましょう。

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

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

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

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

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

4

9 に答える 9

2

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

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

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

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

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

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

EDIT、コメントに基づいて

オートコンプリートの場合、データが静的な場合は、並べ替えてバイナリ検索を使用します。あなたは本当にそれより速くなるつもりはありません。

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

それ以外は、これらの概念の専門化です。

于 2008-09-18T22:13:14.887 に答える
1

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

私の意見ではそれが最も簡単で、かなり迅速に実行されるはずです。

于 2008-09-18T21:48:11.920 に答える
0

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

于 2008-09-19T22:06:41.157 に答える
0

私は今Javaに取り組んでいませんが、次のことについて考えます。

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

コレクションを単純にループするだけの場合は、それを配列として保存するか、連結リストとして保存するかに大きな違いは見られません。

結果を保存する方法は、結果を収集する方法によって異なります (ただし、Java の一般的な構造がスマートであると仮定すると、そうはなりません)。私が言ったように、私は自分の Java に慣れていませんが、一般的なリンクされたリストはテール ポインターを保持していると思います。この場合、実際には違いはありません。基になる配列とリンクされたリストの実装、およびそれがバイトコードでどのように検索されるかについてより多くの知識を持っている人は、テールポインターを使用してリンクされたリストに追加するか、配列に挿入する方が速いかをおそらく教えてくれるでしょう(私の推測では配列です）。一方、配列を使用する場合は、結果セットのサイズを知るか、ストレージ スペースを犠牲にして、反復するコレクション全体と同じ大きさにする必要があります。

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

于 2008-09-18T21:56:30.353 に答える
0

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

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

于 2008-09-18T21:56:43.443 に答える
0

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

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

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

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

于 2008-09-18T22:21:16.473 に答える
0

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

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

于 2008-09-18T21:49:03.057 に答える
0

リストを一度入力してから多くのルックアップ (数千以上) を実行する場合は、開始値/終了値を実際の値にマップするある種のルックアップ ディクショナリを作成できます。これは高速なルックアップになりますが、より多くのメモリを使用します。それほど多くのルックアップを行っていない場合、または少なくとも半頻度でリストを再作成することがわかっている場合は、CQ が提案した LINQ クエリを使用します。

于 2008-09-18T21:59:35.603 に答える
0

ある種のインデックスを作成すると、より高速になる可能性があります。

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

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 をループする必要はないかもしれませんが、インデックスを最新の状態に保つ必要があります。高速であるという保証はありませんが、間違いなくより複雑です。

于 2008-09-18T22:01:36.490 に答える