跨多个属性搜索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类型.如果我只在一个字段上进行搜索,我可能只是将其移动到字典中.记录也不总是唯一的.

显然,这真的很慢.

我遇到了可以构建索引的开源库I4O,但是在各种查询中我都失败了(我没有时间尝试调试源代码).它也不适用于.StartsWith或.Contains(StartsWith更重要,因为许多原始查询利用了搜索"A"会在"ABC"中找到匹配的事实).

有没有其他项目(开源或商业)做这种事情？

编辑:

我根据反馈进行了一些搜索,发现了Power Collections,它支持具有非唯一键的字典.

我测试了ToLookup()效果很好 - 它仍然不如原始代码快,但它至少是可以接受的.它从45秒下降到3-4秒.我将看看Trie结构的其他看起来.

谢谢.

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.
}

您的启动标准对于基于密钥的匹配很麻烦.解决该问题的一种方法是在生成密钥时忽略它.

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更快.

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的当前列表的类型.这样,您可以大大减少每次迭代中考虑的行数.

下一步是使用not a ICollection<T>作为值类型而不是trie(这看起来很有希望),这是一种为查找具有指定前缀的字符串而定制的数据结构.

最后,一个免费的微优化将是TrimEnd走出循环.

现在肯定所有这些仅适用于给定的具体示例,并且由于您的情况的其他细节可能需要重新审视,但无论如何您应该能够从这个或类似的东西中获取实际收益.