[解決済み] 文字列コレクションを検索する最速の方法

質問

問題です。

私の手元にあるテキストファイルは 120,000 ユーザー (文字列) のテキストファイルがあり、これをコレクションに保存して、後でそのコレクションで検索を実行したいと思います。

検索メソッドは、ユーザが TextBox の文字列を検索し、その結果 を含む のテキストは TextBox .

リストを変更する必要はなく、結果を引っ張ってきて、それを ListBox .

今まで試したこと

私は2つの異なるコレクション/コンテナで試してみました。私は外部のテキストファイルから文字列のエントリをダンプしています（もちろん一度だけ）。

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 秒間)。

質問です。

私のボトルネックはどこだと思いますか？私が使用したコレクション？検索方法？両方ですか？

どうすれば、より良いパフォーマンスとより流暢な機能を得ることができますか？

どのように解決するのですか？

フィルタリングをバックグラウンドスレッドで行い、終了したらコールバックメソッドを呼び出すか、入力が変更されたら単純にフィルタリングを再開することを検討することができます。

一般的なアイデアとしては、このように使用することができます。

public partial class YourForm : Form
{
    private readonly BackgroundWordFilter _filter;

    public YourForm()
    {
        InitializeComponent();

        // setup the background worker to return no more than 10 items,
        // and to set ListBox.DataSource when results are ready

        _filter = new BackgroundWordFilter
        (
            items: GetDictionaryItems(),
            maxItemsToMatch: 10,
            callback: results => 
              this.Invoke(new Action(() => listBox_choices.DataSource = results))
        );
    }

    private void textBox_search_TextChanged(object sender, EventArgs e)
    {
        // this will update the background worker's "current entry"
        _filter.SetCurrentEntry(textBox_search.Text);
    }
}

ラフスケッチは次のようなものです。

public class BackgroundWordFilter : IDisposable
{
    private readonly List<string> _items;
    private readonly AutoResetEvent _signal = new AutoResetEvent(false);
    private readonly Thread _workerThread;
    private readonly int _maxItemsToMatch;
    private readonly Action<List<string>> _callback;

    private volatile bool _shouldRun = true;
    private volatile string _currentEntry = null;

    public BackgroundWordFilter(
        List<string> items,
        int maxItemsToMatch,
        Action<List<string>> callback)
    {
        _items = items;
        _callback = callback;
        _maxItemsToMatch = maxItemsToMatch;

        // start the long-lived backgroud thread
        _workerThread = new Thread(WorkerLoop)
        {
            IsBackground = true,
            Priority = ThreadPriority.BelowNormal
        };

        _workerThread.Start();
    }

    public void SetCurrentEntry(string currentEntry)
    {
        // set the current entry and signal the worker thread
        _currentEntry = currentEntry;
        _signal.Set();
    }

    void WorkerLoop()
    {
        while (_shouldRun)
        {
            // wait here until there is a new entry
            _signal.WaitOne();
            if (!_shouldRun)
                return;

            var entry = _currentEntry;
            var results = new List<string>();

            // if there is nothing to process,
            // return an empty list
            if (string.IsNullOrEmpty(entry))
            {
                _callback(results);
                continue;
            }

            // do the search in a for-loop to 
            // allow early termination when current entry
            // is changed on a different thread
            foreach (var i in _items)
            {
                // if matched, add to the list of results
                if (i.Contains(entry))
                    results.Add(i);

                // check if the current entry was updated in the meantime,
                // or we found enough items
                if (entry != _currentEntry || results.Count >= _maxItemsToMatch)
                    break;
            }

            if (entry == _currentEntry)
                _callback(results);
        }
    }

    public void Dispose()
    {
        // we are using AutoResetEvent and a background thread
        // and therefore must dispose it explicitly
        Dispose(true);
    }

    private void Dispose(bool disposing)
    {
        if (!disposing)
            return;

        // shutdown the thread
        if (_workerThread.IsAlive)
        {
            _shouldRun = false;
            _currentEntry = null;
            _signal.Set();
            _workerThread.Join();
        }

        // if targetting .NET 3.5 or older, we have to
        // use the explicit IDisposable implementation
        (_signal as IDisposable).Dispose();
    }
}

また、実際にディスポーザブルにするのは _filter インスタンスを破棄しなければなりません。 Form が破棄されたときです。つまり Form 's Dispose メソッド(内部 YourForm.Designer.cs ファイル内) を以下のように変更します。

// inside "xxxxxx.Designer.cs"
protected override void Dispose(bool disposing)
{
    if (disposing)
    {
        if (_filter != null)
            _filter.Dispose();

        // this part is added by Visual Studio designer
        if (components != null)
            components.Dispose();
    }

    base.Dispose(disposing);
}

私のマシンでは、かなり速く動作するので、より複雑な解決策をとる前に、これをテストしてプロファイルする必要があります。

とはいえ、quot;より複雑なソリューションは、辞書に最後の結果のカップルを格納し、新しいエントリが最後の文字の最初だけで異なっていることが判明した場合にのみフィルタリングすることです。