10

我有一个继承的过程，我正在从另一种语言转换为 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 是本地列表类型。如果我只在一个字段上进行搜索，我可能会将其移至字典中。记录也不总是唯一的。

显然，这真的很慢。

我遇到了可以构建索引的开源库I4O，但是它在各种查询中对我来说都失败了（而且我真的没有时间尝试调试源代码）。它也不适用于 .StartsWith 或 .Contains （StartsWith 更为重要，因为许多原始查询都利用了搜索“A”会在“ABC”中找到匹配项的事实）。

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

编辑：

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

我测试了 ToLookup() 效果很好 - 它仍然没有原始代码那么快，但它至少是可以接受的。它从 45 秒减少到 3-4 秒。我将看一下其他查找的 Trie 结构。

谢谢。

4

2 回答 2

14

循环遍历 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 快。

于 2012-04-11T16:30:32.237 回答
13

当然，你可以做得比这更好。让我们首先考虑字典不是仅在您想查询一个字段时才有用；您可以很容易地拥有一个字典，其中键是聚合许多字段的不可变值。所以对于这个特定的查询，一个直接的改进是创建一个键类型：

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

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

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

最后，免费的微优化将TrimEnd脱离循环。

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

于 2012-04-11T16:15:37.017 回答