81

问题:

我有一个包含大约120,000个用户(字符串)的文本文件,我想将其存储在一个集合中,然后再对该集合执行搜索。

每次用户更改 a 的文本时都会出现搜索方法,TextBox结果应该是包含TextBox.

我不必更改列表,只需提取结果并将它们放入ListBox.

到目前为止我已经尝试过:

我尝试了两个不同的集合/容器,我正在从外部文本文件中转储字符串条目(当然是一次):

  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

48

您可以考虑在后台线程上执行过滤任务,该任务完成后将调用回调方法,或者如果输入更改则简单地重新启动过滤。

一般的想法是能够像这样使用它:

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。这意味着您应该打开并编辑您FormDispose方法(在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);
}

在我的机器上,它运行得非常快,因此在寻求更复杂的解决方案之前,您应该对其进行测试和分析。

话虽如此,“更复杂的解决方案”可能是将最后几个结果存储在字典中,然后仅在新条目仅与最后一个字符的第一个不同时过滤它们。

于 2014-01-27T12:28:17.837 回答
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();

但是,我计算了访问TextBox.Text500,000 次需要多长时间,只用了 0.7 秒,远低于 OP 中提到的 1-3 秒。不过,这是一个值得的优化。

于 2014-01-27T11:28:17.113 回答
28

使用后缀树作为索引。或者更确切地说,只是构建一个排序字典,将每个名称的每个后缀与相应名称的列表相关联。

对于输入:

Abraham
Barbara
Abram

结构如下:

a -> Barbara
ab -> Abram
abraham -> Abraham
abram -> Abram
am -> Abraham, Abram
aham -> Abraham
ara -> Barbara
arbara -> Barbara
bara -> Barbara
barbara -> Barbara
bram -> Abram
braham -> Abraham
ham -> Abraham
m -> Abraham, Abram
raham -> Abraham
ram -> Abram
rbara -> Barbara

搜索算法

假设用户输入“bra”。

  1. 将用户输入的字典一分为二以找到用户输入或它可以去的位置。这样我们就可以找到“barbara”——最后一个键低于“bra”。它被称为“胸罩”的下限。搜索将花费对数时间。
  2. 从找到的键开始迭代,直到用户输入不再匹配。这将给出 "bram" -> Abram 和 "braham" -> Abraham。
  3. 连接迭代结果(Abram,Abraham)并输出。

这种树是为快速搜索子字符串而设计的。它的性能接近 O(log n)。我相信这种方法的运行速度足够快,可以直接被 GUI 线程使用。此外,由于没有同步开销,它会比线程解决方案更快地工作。

于 2014-01-27T14:42:51.767 回答
15

您需要文本搜索引擎(如Lucene.Net)或数据库(您可以考虑使用嵌入式搜索引擎,如SQL CESQLite等)。换句话说,您需要一个索引搜索。基于哈希的搜索在这里不适用,因为您搜索子字符串,而基于哈希的搜索非常适合搜索精确值。

否则,它将是一个遍历集合的迭代搜索。

于 2014-01-27T11:25:54.897 回答
12

拥有“去抖动”类型的事件也可能很有用。这与节流不同,它在触发事件之前等待一段时间(例如,200 毫秒)以完成更改。

有关去抖动的更多信息,请参阅Debounce and Throttle:视觉解释。我很欣赏这篇文章专注于 JavaScript,而不是 C#,但原则适用。

这样做的好处是当您仍在输入查询时它不会搜索。然后它应该停止尝试一次执行两个搜索。

于 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 回答
11

更新:

我做了一些分析。

(更新 3)

  • 列表内容:从 0 到 2.499.999 生成的数字
  • 过滤文本:123(20.477 个结果)
  • 酷睿 i5-2500,Win7 64 位,8GB 内存
  • VS2012 + JetBrains dotTrace

2.500.000 条记录的初始测试运行花了我 20.000 毫秒。

第一个罪魁祸首是对textBox_search.Textinside的调用Contains。这使得每个元素调用get_WindowText文本框的昂贵方法。只需将代码更改为:

    var text = textBox_search.Text;
    listBox_choices.DataSource = allUsers.Where(item => item.Contains(text)).ToList();

将执行时间减少到1.858ms

更新 2:

另外两个重要的瓶颈现在是调用string.Contains(大约 45% 的执行时间)和更新列表框元素set_Datasource(30%)。

我们可以通过创建后缀树来在速度和内存使用之间进行权衡,因为 Basilevs 建议减少必要的比较次数,并将一些处理时间从按键后的搜索推到从文件加载名称可能更适合用户。

为了提高将元素加载到列表框中的性能,我建议仅加载前几个元素并向用户指示还有其他可用元素。通过这种方式,您可以向用户反馈有可用的结果,以便他们可以通过输入更多字母来优化搜索,或者只需按一下按钮即可加载完整列表。

使用BeginUpdateEndUpdate没有改变set_Datasource.

正如其他人在这里指出的那样,LINQ 查询本身运行得非常快。我相信你的瓶颈是列表框本身的更新。您可以尝试以下方法:

if (textBox_search.Text.Length > 2)
{
    listBox_choices.BeginUpdate(); 
    listBox_choices.DataSource = allUsers.Where(item => item.Contains(textBox_search.Text)).ToList();
    listBox_choices.EndUpdate(); 
}

我希望这有帮助。

于 2014-01-27T13:52:47.027 回答
9

假设您仅通过前缀匹配,您要查找的数据结构称为trie,也称为“前缀树”。您现在使用的IEnumerable.Where方法必须在每次访问时遍历字典中的所有项目。

这个线程展示了如何在 C# 中创建一个 trie。

于 2014-01-27T11:24:40.440 回答
8

WinForms ListBox 控件确实是您的敌人。加载记录会很慢,而且 ScrollBar 会与您争夺所有 120,000 条记录。

尝试使用老式的 DataGridView 数据源到具有单列 [UserName] 的 DataTable 来保存您的数据:

private DataTable dt;

public Form1() {
  InitializeComponent();

  dt = new DataTable();
  dt.Columns.Add("UserName");
  for (int i = 0; i < 120000; ++i){
    DataRow dr = dt.NewRow();
    dr[0] = "user" + i.ToString();
    dt.Rows.Add(dr);
  }
  dgv.AutoSizeColumnsMode = DataGridViewAutoSizeColumnsMode.Fill;
  dgv.AllowUserToAddRows = false;
  dgv.AllowUserToDeleteRows = false;
  dgv.RowHeadersVisible = false;
  dgv.DataSource = dt;
}

然后在 TextBox 的 TextChanged 事件中使用 DataView 来过滤数据:

private void textBox1_TextChanged(object sender, EventArgs e) {
  DataView dv = new DataView(dt);
  dv.RowFilter = string.Format("[UserName] LIKE '%{0}%'", textBox1.Text);
  dgv.DataSource = dv;
}
于 2014-01-27T21:26:47.740 回答
7

首先,我将更改ListControl查看数据源的方式,将结果转换IEnumerable<string>List<string>. 特别是当您只输入几个字符时,这可能效率低下(并且不需要)。不要对您的数据进行大量复制

  • 我会将结果包装到一个仅实现(搜索).Where()所需内容的集合中。IList这将节省您为输入的每个字符创建一个新的大列表。
  • 作为替代方案,我会避免使用 LINQ,我会写一些更具体(和优化)的东西。将您的列表保存在内存中并构建一个匹配索引的数组,重用数组,这样您就不必为每次搜索重新分配它。

第二步是小一个就够了,不要在大列表中搜索。当用户开始输入“ab”并添加“c”时,您无需在大列表中进行研究,在过滤列表中搜索就足够了(而且速度更快)。每次都可以优化搜索,不要每次都执行完整搜索。

第三步可能更难:保持数据有条理以便快速搜索。现在您必须更改用于存储数据的结构。想象一棵这样的树:

美国广播公司
 添加更好的天花板
 骨轮廓上方

这可以简单地用一个数组来实现(如果你使用的是 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()按照第一步中的建议使用(但为了简洁起见,我在第二个建议中省略了,如果您为字典键选择正确的大小,您可以使每个列表简短而快速 - 也许 - 避免其他任何事情)。此外请注意,您可以尝试在字典中使用前两个字符(更多列表和更短的列表)。如果你扩展它,你将有一棵树(但我认为你没有这么多的项目)。

字符串搜索有许多不同的算法(具有相关的数据结构),仅举几例:

  • 基于有限状态自动机的搜索:在这种方法中,我们通过构建识别存储搜索字符串的确定性有限自动机 (DFA) 来避免回溯。这些构造起来很昂贵——它们通常是使用 powerset 构造创建的——但使用起来非常快。
  • Stubs:Knuth–Morris–Pratt 计算一个 DFA,它使用要搜索的字符串作为后缀来识别输入,Boyer–Moore 从针的末端开始搜索,因此它通常可以在每一步跳出整个针长度。Baeza-Yates 跟踪前面的 j 个字符是否是搜索字符串的前缀,因此适用于模糊字符串搜索。bitap 算法是 Baeza-Yates 方法的应用。
  • 索引方法:更快的搜索算法基于文本的预处理。建立子字符串索引后,例如后缀树或后缀数组,可以快速找到模式的出现。
  • 其他变体:一些搜索方法,例如三元组搜索,旨在找到搜索字符串和文本之间的“接近度”分数,而不是“匹配/不匹配”。这些有时被称为“模糊”搜索。

关于并行搜索的几句话。这是可能的,但它很少是微不足道的,因为使其并行的开销很容易比搜索本身高得多。我不会并行执行搜索本身(分区和同步很快就会变得过于庞大并且可能很复杂),但我会将搜索移至单独的线程。如果主线程不忙,您的用户在输入时不会感到任何延迟(他们不会注意到列表是否会在 200 毫秒后出现,但如果他们必须在输入后等待 50 毫秒,他们会感到不舒服) . 当然,搜索本身必须足够快,在这种情况下,您不使用线程来加快搜索速度,而是保持 UI 响应。请注意,单独的线程不会进行您的查询更快,它不会挂起 UI,但如果您的查询很慢,它在单独的线程中仍然会很慢(此外,您还必须处理多个顺序请求)。

于 2014-01-27T11:22:56.713 回答
4

您可以尝试使用PLINQ(并行 LINQ)。虽然这并不能保证速度提升,但您需要通过反复试验找出答案。

于 2014-01-27T11:18:34.447 回答
4

我怀疑你能否让它更快,但你肯定应该:

a) 使用 AsParallel LINQ扩展方法

a) 使用某种定时器来延迟过滤

b) 将过滤方法放在另一个线程上

string previousTextBoxValue在某处保留某种东西。制作一个延迟为 1000 毫秒的计时器,如果与您的值previousTextBoxValue相同,则会在滴答声上触发搜索。textbox.Text如果不是 - 重新分配previousTextBoxValue当前值并重置计时器。将计时器启动设置为文本框更改事件,它会使您的应用程序更流畅。在 1-3 秒内过滤 120,000 条记录是可以的,但您的 UI 必须保持响应。

于 2014-01-27T11:20:11.920 回答
3

您也可以尝试使用BindingSource.Filter函数。我已经使用过它,它就像从一堆记录中过滤出来的魅力一样,每次都使用正在搜索的文本更新此属性。另一种选择是将AutoCompleteSource用于 TextBox 控件。

希望能帮助到你!

于 2014-01-28T07:54:01.257 回答
2

我会尝试对集合进行排序,搜索以仅匹配开始部分并将搜索限制为某个数字。

等等初始化

allUsers.Sort();

并搜索

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

也许你可以添加一些缓存。

于 2014-01-27T16:03:10.987 回答
1

使用并行LINQPLINQ是 LINQ to Objects 的并行实现。PLINQ 将整套 LINQ 标准查询运算符实现为 T:System.Linq 命名空间的扩展方法,并具有用于并行操作的附加运算符。PLINQ 将 LINQ 语法的简单性和可读性与并行编程的强大功能相结合。就像以任务并行库为目标的代码一样,PLINQ 查询根据主机的能力在并发程度上进行扩展。

PLINQ 简介

了解 PLINQ 中的加速

你也可以使用Lucene.Net

Lucene.Net 是 Lucene 搜索引擎库的一个端口,用 C# 编写,面向 .NET 运行时用户。Lucene 搜索库基于倒排索引。Lucene.Net 有三个主要目标:

于 2014-01-27T16:56:18.863 回答
1

根据我所看到的,我同意对列表进行排序的事实。

但是在构建列表时排序会很慢,在构建时排序,您将有更好的执行时间。

否则,如果您不需要显示列表或保持顺序,请使用哈希图。

hashmap 将散列您的字符串并在确切的偏移量处搜索。我认为它应该更快。

于 2014-01-28T04:14:31.080 回答
1

尝试使用 BinarySearch 方法,它应该比 Contains 方法工作得更快。

包含将是一个 O(n) BinarySearch 是一个 O(lg(n))

我认为排序后的集合在搜索时应该更快,在添加新元素时应该更慢,但据我所知,你只有搜索性能问题。

于 2014-01-29T08:44:16.610 回答