C#中的高速字符串匹配

Question

我有一个大约10,000个工作人员的列表,List<T>我有一个ListBox包含这些工作人员的子集,具体取决于文本框中的搜索词.

假设某个Staff对象具有以下公开公开的属性:

string FirstName
string LastName
string MiddleName
   int StaffID
   int CostCentre

我可以写一个这样的函数:

bool staffMatchesSearch(Staff stf)
{
  if (tbSrch.Text.Trim() == string.Empty)
    return true; // No search = match always.

  string s = tbSrch.Text.Trim().ToLower();

  // Do the checks in the order most likely to return soonest:
  if (stf.LastName.ToLower().Contains(s))
    return true;
  if (stf.FirstName.ToLower().Contains(s))
    return true;
  if (stf.MiddleName.ToLower().Contains(s))
    return true;

  if (stf.CostCentre.ToString().Contains(s))
    return true; // Yes, we want partial matches on CostCentre
  if (stf.StaffID.ToString().Contains(s))
    return true; // And also on StaffID

  return false;
}

然后做类似的事情:

tbSrch_TextChanged(object sender, EventArgs e)
{
  lbStaff.BeginUpdate();
  lbStaff.Items.Clear();

  foreach (Staff stf in staff)
    if (staffMatchesSearch(stf))
      lbStaff.Items.Add(stf);

  lbStaff.EndUpdate();
}

每次用户更改tbSrch框的内容时,都会重新评估过滤.

这是有效的,并没有非常缓慢,但我想知道我能不能更快？

我试图将整个事情重新编写为多线程,但是只有10,000名员工,开销似乎带走了大部分收益.此外,还有一堆其他的错误,如果搜索"John",用户首先按下"J",它会调整线程,但是当用户按下"o"时,另一组会在第一批产品出现之前进行假脱机有机会返回结果.很多时候,结果会以混乱的顺序返回,并且会发生各种令人讨厌的事情.

我可以想到一些调整可以使最佳情况显着改善,但它们也会使最坏情况更糟糕.

您对如何改进这一点有什么想法吗？

---

我已经实施了很好的建议,结果如下:

• 在ValueChanged事件上添加延迟,以便如果用户在键盘上快速键入5个字符的名称,它最后只执行1次搜索而不是5次串行搜索.
• 预先评估ToLower()并存储在Staff类中(作为[NonSerialized]属性,因此它不会占用保存文件中的额外空间).
• 添加一个get属性,Staff其中将所有搜索条件作为单个,长小写的连续字符串返回.然后单独运行Contains().(此字符串存储在Staff对象中,因此只构造一次.)

到目前为止,这些搜索时间从大约140ms减少到大约60ms(尽管这些数字非常主观,取决于实际搜索和返回的结果数量).

Answer 1

1)正如评论中指出的那样,你可能不应该.ToString数字字段 - 只是匹配数字

2)ToLower调用是一个perf perf.将这些属性的小写版本添加到Staff类,因此ToLower只需执行一次

3)当用户输入另一个字符时,您不需要重新评估所有项目.输入一个字符只会减少匹配数,所以只能重新评估以前的匹配.

4)使用计时器在用户输入和开始搜索之间引入延迟.如果他们快速输入多个字符,你不妨等到他们暂停了半秒钟

5)检查按下的键.如果NaN则不检查int属性.