什么是在多个属性中搜索List<T>的最快方法？

Question

我正在将从另一种语言继承而来的进程转换为C#。 过程中的许多步骤循环遍历大量记录（100K-200K）进行计算。 作为这些过程的一部分，通常会查找另一个列表以检索某些值。 我通常会将这种事情移动到SQL语句中（在我们能够做到的情况下，我们已经这样做了），但在这些情况下，确实没有简单的方法可以做到这一点。 在某些地方，我们尝试将代码转换为存储过程并发现它的效果并不像我们希望的那样好。

实际上，代码执行以下操作：

var match = cost.Where(r => r.ryp.StartsWith(record.form.TrimEnd()) && 
                       r.year == record.year && 
                       r.period == record.period).FirstOrDefault();

cost是一个本地的List类型。如果我只在一个字段上进行搜索，我可能会将它移入Dictionary中。记录也不总是唯一的。

显然，这样做非常慢。

我发现开源库I4O可以构建索引，但它在我的各种查询中失败了（我确实没有时间尝试调试源代码）。它也不支持.StartsWith或.Contains（其中.StartsWith更为重要，因为很多原始查询利用了搜索“A”会在“ABC”中找到匹配项的事实）。

还有其他的项目（开源或商业）可以做到这一点吗？

编辑：

根据反馈结果，我进行了一些搜索，找到了Power Collections，它支持具有非唯一键的字典。

我测试了ToLookup()，效果非常好——虽然仍然不如原始代码快，但至少是可以接受的。时间从45秒降到了3-4秒。我会看看Trie结构来进行其他查找。

谢谢。

- Paul Mrozowski

---

进程循环在同一组记录上进行了大量查找，还是仅在需要新记录时才使用了少数记录集？ - Telastyn

它在同一组记录上进行循环。因此，整个过程中都使用相同的查找。旧代码中需要1-2秒钟的一个步骤，在新代码中需要35秒钟。 - Paul Mrozowski

另一个需要考虑的问题可能是将问题映射到不同的线程（通过Parallel.ForEach），具体取决于是否有必要按特定顺序迭代，再加上索引查找。 - Adam Houldsworth

Answer 1

循环处理100K-200K个项目并不需要太长时间。但如果使用嵌套循环（n ^ 2）在列表中查找匹配项，则会花费很长时间。我推断这就是您正在做的事情（因为您将其赋值给本地匹配变量）。

如果您想快速匹配项目，请使用.ToLookup。

var lookup = cost.ToLookup(r => new {r.year, r.period, form = r.ryp});

foreach(var group in lookup)
{
  // do something with items in group.
}

您的startswith标准对于基于键的匹配来说是有问题的。解决该问题的一种方法是在生成键时忽略它。

var lookup = cost.ToLookup(r => new {r.year, r.period });
var key = new {record.year, record.period};
string lookForThis = record.form.TrimEnd();
var match = lookup[key].FirstOrDefault(r => r.ryp.StartsWith(lookForThis))

理想情况下，您应该创建一次查询并将其重复使用多次。即使您没有这样做... 即使您每次都创建查找表，它仍然比n^2快。

- Amy B

Answer 2

当然，您可以做得更好。让我们从考虑字典不仅在查询一个字段时有用开始；您可以非常容易地创建一个键是聚合多个字段的不可变值的字典。因此，对于这个特定的查询，一个立即的改进就是创建一个键类型：

// should be immutable, GetHashCode and Equals should be implemented, etc etc
struct Key
{
    public int year;
    public int period;
}

然后将数据打包成类似于IDictionary<Key, ICollection<T>>的结构，其中T是您当前列表的类型。这样可以大大减少每次迭代中考虑的行数。

下一步是不使用ICollection<T>作为值类型，而是使用trie（这个看起来很有前途），这是一种专门用于查找具有指定前缀的字符串的数据结构。

最后，一个自由微小优化是将TrimEnd从循环中取出。

当然，所有这些只适用于给定的特定示例，并且可能需要重新审视由于您情况的其他特定情况，但无论如何，您应该能够从中或类似的东西中提取实际收益。

- Jon

---

对我来说致命的是这些记录不是唯一的 - 即使在它搜索的字段上也是如此。原始代码利用了最初的排序顺序。 - Paul Mrozowski

@PaulMrozowski：哪些记录不是唯一的，为什么这很重要？我建议使用集合的字典。 - Jon