81

問題：

約120,000ユーザー (文字列)のテキスト ファイルをコレクションに保存し、後でそのコレクションで検索を実行したいと考えています。

search メソッドは、ユーザーが のテキストを変更するたびに発生TextBoxし、結果はのテキストを含むTextBox文字列になります。

リストを変更する必要はありません。結果を取得してListBox.

私がこれまでに試したこと：

外部テキスト ファイルから文字列エントリをダンプしている 2 つの異なるコレクション/コンテナーを試しました (もちろん 1 回):

  1. List<string> allUsers;
  2. HashSet<string> allUsers;

次のLINQクエリを使用します。

allUsers.Where(item => item.Contains(textBox_search.Text)).ToList();

私の検索イベント（ユーザーが検索テキストを変更すると発生します）：

private void textBox_search_TextChanged(object sender, EventArgs e)
{
    if (textBox_search.Text.Length > 2)
    {
        listBox_choices.DataSource = allUsers.Where(item => item.Contains(textBox_search.Text)).ToList();
    }
    else
    {
        listBox_choices.DataSource = null;
    }
}

結果：

どちらも応答時間が短かった (キーを押すたびに約 1 ～ 3 秒)。

質問：

私のボトルネックはどこにあると思いますか? 私が使ったコレクション？検索方法は？両方？

より良いパフォーマンスとより流暢な機能を得るにはどうすればよいですか?

4

17 に答える 17

36

いくつかのテストを行ったところ、120,000 項目のリストを検索し、エントリを新しいリストに入力するのにかかる時間はごくわずかです (すべての文字列が一致した場合でも、約 1/50 秒)。

したがって、表示されている問題は、次のデータ ソースの入力に起因するものである必要があります。

listBox_choices.DataSource = ...

リストボックスにあまりにも多くのアイテムを入れているだけだと思います。

次のように、最初の 20 エントリに制限してみてください。

listBox_choices.DataSource = allUsers.Where(item => item.Contains(textBox_search.Text))
    .Take(20).ToList();

また、(他の人が指摘したように)TextBox.Textの各アイテムのプロパティにアクセスしていることにも注意してくださいallUsers。これは、次のように簡単に修正できます。

string target = textBox_search.Text;
listBox_choices.DataSource = allUsers.Where(item => item.Contains(target))
    .Take(20).ToList();

ただし、500,000 回アクセスするのにかかる時間を計ったTextBox.Textところ、0.7 秒しかかからず、OP で述べた 1 ～ 3 秒よりもはるかに短かった. それでも、これは価値のある最適化です。

于 2014-01-27T11:28:17.113 に答える
15

テキスト検索エンジン ( Lucene.Net など) またはデータベース ( SQL CE、SQLiteなどの組み込みエンジンを検討してもよい) のいずれかが必要です。つまり、インデックス検索が必要です。部分文字列を検索するため、ハッシュベースの検索はここでは適用できませんが、ハッシュベースの検索は正確な値の検索に適しています。

それ以外の場合は、コレクションをループする反復検索になります。

于 2014-01-27T11:25:54.897 に答える
12

「デバウンス」タイプのイベントがあると便利な場合もあります。これは、変更が完了するまで一定時間 (たとえば、200 ミリ秒) 待機してからイベントを発生させるという点で、調整とは異なります。

デバウンスとスロットル: デバウンスの詳細については、視覚的な説明を参照してください。この記事が C# ではなく JavaScript に焦点を当てていることを理解していますが、原則は適用されます。

これの利点は、まだクエリを入力しているときに検索されないことです。その後、一度に 2 つの検索を実行しようとするのをやめる必要があります。

于 2014-01-27T11:13:52.073 に答える
11

別のスレッドで検索を実行し、そのスレッドの実行中にロード アニメーションまたは進行状況バーを表示します。

LINQクエリを並列化することもできます。

var queryResults = strings.AsParallel().Where(item => item.Contains("1")).ToList();

AsParallel() のパフォーマンス上の利点を示すベンチマークは次のとおりです。

{
    IEnumerable<string> queryResults;
    bool useParallel = true;

    var strings = new List<string>();

    for (int i = 0; i < 2500000; i++)
        strings.Add(i.ToString());

    var stp = new Stopwatch();

    stp.Start();

    if (useParallel)
        queryResults = strings.AsParallel().Where(item => item.Contains("1")).ToList();
    else
        queryResults = strings.Where(item => item.Contains("1")).ToList();

    stp.Stop();

    Console.WriteLine("useParallel: {0}\r\nTime Elapsed: {1}", useParallel, stp.ElapsedMilliseconds);
}
于 2014-01-27T11:09:09.563 に答える
9

接頭辞のみで照合していると仮定すると、探しているデータ構造はtrieと呼ばれ、「接頭辞ツリー」とも呼ばれます。現在IEnumerable.Where使用している方法では、アクセスごとに辞書内のすべての項目を反復処理する必要があります。

このスレッドは、C# でトライを作成する方法を示しています。

于 2014-01-27T11:24:40.440 に答える
7

まずListControl、 がデータ ソースを参照する方法を変更します。結果IEnumerable<string>を に変換していますList<string>。特に、数文字しか入力していない場合、これは非効率的 (かつ不要) になる可能性があります。データの大規模なコピーを作成しないでください。

  • (検索).Where()から必要なものだけを実装するコレクションに結果をラップします。IListこれにより、文字を入力するたびに新しい大きなリストを作成する手間が省けます。
  • 別の方法として、LINQを避け、より具体的な（そして最適化された）ものを書きます。リストをメモリに保持し、一致するインデックスの配列を作成し、配列を再利用して、検索ごとに再割り当てする必要がないようにします。

2 番目のステップは、小さなリストで十分な場合は、大きなリストを検索しないことです。ユーザーが「ab」と入力し始めて「c」を追加すると、大きなリストを調査する必要がなくなります。フィルタリングされたリストを検索するだけで十分です (そしてより高速です)。毎回完全な検索を実行しないでください。

3 番目のステップは難しいかもしれません。すばやく検索できるようにデータを整理します。ここで、データの格納に使用する構造を変更する必要があります。次のようなツリーを想像してください。

ABC
 より良い天井を追加
 骨の輪郭の上

これは単純に配列で実装できます (ANSI 名を使用している場合は、それ以外の場合は辞書の方が適しています)。次のようにリストを作成します (説明目的で、文字列の先頭に一致します)。

var dictionary = new Dictionary<char, List<string>>();
foreach (var user in users)
{
    char letter = user[0];
    if (dictionary.Contains(letter))
        dictionary[letter].Add(user);
    else
    {
        var newList = new List<string>();
        newList.Add(user);
        dictionary.Add(letter, newList);
    }
}

検索は最初の文字を使用して行われます。

char letter = textBox_search.Text[0];
if (dictionary.Contains(letter))
{
    listBox_choices.DataSource =
        new MyListWrapper(dictionary[letter].Where(x => x.Contains(textBox_search.Text)));
}

最初のステップで提案したとおりに使用したことに注意してくださいMyListWrapper()（ただし、簡潔にするために2番目の提案を省略しました。辞書キーに適切なサイズを選択すると、各リストを短く高速にして、他のものを避けることができます）。さらに、辞書に最初の 2 文字を使用しようとしてもよいことに注意してください (より多くのリストとより短い)。これを拡張すると、ツリーが作成されます (ただし、それほど多くの項目があるとは思いません)。

文字列検索には (関連するデータ構造を持つ)さまざまなアルゴリズムがありますが、いくつか挙げると:

  • 有限状態オートマトン ベースの検索: このアプローチでは、格納された検索文字列を認識する決定論的有限オートマトン (DFA) を構築することにより、バックトラックを回避します。これらは構築するのに費用がかかりますが (通常、powerset 構築を使用して作成されます)、非常に迅速に使用できます。
  • スタブ: Knuth–Morris–Pratt は、検索する文字列を接尾辞として入力を認識する DFA を計算します。Boyer–Moore は、針の最後から検索を開始するため、通常、各ステップで針の長さ全体をジャンプできます。Baeza–Yates は、前の j 文字が検索文字列のプレフィックスであったかどうかを追跡するため、あいまい文字列検索に適応できます。bitap アルゴリズムは、Baeza-Yates のアプローチを応用したものです。
  • インデックス メソッド: より高速な検索アルゴリズムは、テキストの前処理に基づいています。サフィックス ツリーやサフィックス配列などの部分文字列インデックスを作成すると、パターンの出現箇所をすばやく見つけることができます。
  • その他のバリエーション: トリグラム検索などの一部の検索方法は、「一致/不一致」ではなく、検索文字列とテキストの間の「近さ」スコアを見つけることを目的としています。これらは「あいまい」検索と呼ばれることもあります。

並列検索について一言。可能ですが、並列化するためのオーバーヘッドが検索自体よりもはるかに高くなるため、簡単なことはめったにありません。検索自体を並行して実行することはしませんが (パーティショニングと同期はすぐに拡張しすぎて複雑になる可能性があります)、検索を別のスレッドに移動します。メイン スレッドがビジーでない場合、ユーザーは入力中に遅延を感じることはありません (リストが 200 ミリ秒後に表示されるかどうかは気にしませんが、入力してから 50 ミリ秒待たなければならない場合は不快に感じます)。 . もちろん、検索自体は十分に高速でなければなりません。この場合、スレッドを使用して検索を高速化するのではなく、UI の応答性を維持します。別のスレッドではクエリが作成されないことに注意してくださいUI がハングすることはありませんが、クエリが遅かった場合でも、別のスレッドでは遅くなります (さらに、複数の連続したリクエストも処理する必要があります) 。

于 2014-01-27T11:22:56.713 に答える
4

PLINQ (Parallel LINQ)を使用してみることができます。これは速度の向上を保証するものではありませんが、試行錯誤して見つける必要があります.

于 2014-01-27T11:18:34.447 に答える
4

高速化できるとは思えませんが、次のことを行う必要があります。

a) AsParallel LINQ拡張メソッドを使用する

a）何らかのタイマーを使用してフィルタリングを遅らせます

b）別のスレッドにフィルタリングメソッドを配置します

ある種のstring previousTextBoxValueどこかに保管してください。previousTextBoxValue1000ミリ秒の遅延でタイマーを作成し、値と同じ場合にティックで検索を開始しますtextbox.Text。そうでない場合はpreviousTextBoxValue、現在の値に再割り当てし、タイマーをリセットします。タイマーの開始をテキストボックスの変更イベントに設定すると、アプリケーションがよりスムーズになります。1 ～ 3 秒で 120,000 レコードをフィルタリングすることは問題ありませんが、UI は応答性を維持する必要があります。

于 2014-01-27T11:20:11.920 に答える
2

コレクションをソートし、開始部分のみに一致するように検索し、検索をいくつかの数で制限しようとします。

などの初期化

allUsers.Sort();

と検索

allUsers.Where(item => item.StartWith(textBox_search.Text))

たぶん、いくつかのキャッシュを追加できます。

于 2014-01-27T16:03:10.987 に答える
1

BinarySearch メソッドを使用してみてください。Contains メソッドよりも高速に動作するはずです。

含む O(n) BinarySearch は O(lg(n))

ソートされたコレクションは、検索ではより高速に動作し、新しい要素の追加では遅く動作するはずですが、私が理解しているように、検索のパフォーマンスの問題のみがあります。

于 2014-01-29T08:44:16.610 に答える
1

私が見てきたことによると、リストをソートするという事実に同意します。

ただし、リストが構築されているときにソートすると非常に遅くなり、ビルド時にソートすると、実行時間が短縮されます。

それ以外の場合、リストを表示したり順序を維持したりする必要がない場合は、ハッシュマップを使用してください。

ハッシュマップは文字列をハッシュし、正確なオフセットで検索します。それは私が考えるより速いはずです。

于 2014-01-28T04:14:31.080 に答える