c# - C#中的高速字符串匹配

Question

我在 List<T> 中有大约 10,000 名员工的列表我有一个 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属性(property) Staff它将所有搜索条件作为单个、长的、小写的、连接的字符串返回。然后运行单个 Contains()在那上面。 (此字符串存储在 Staff 对象中，因此它只构造一次。)

到目前为止，这些已将搜索时间从大约 140 毫秒减少到大约 60 毫秒(尽管这些数字非常主观，具体取决于实际执行的搜索和返回的结果数量)。

Answer 1

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

2) ToLower 调用会消耗性能。将这些属性的小写版本添加到 Staff 类，这样 ToLower 只需执行一次

3) 当用户输入另一个字符时，您不需要重新评估所有 项。输入字符只会减少匹配项的数量，因此只能重新评估之前的匹配项。

4) 使用定时器在用户输入和您开始搜索之间引入延迟。如果他们快速输入多个字符，您不妨等到他们停顿半秒

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