c# - LINQ .Where 查询执行时间超过 5 分钟

Question

我需要过滤 List<object>这样我就可以删除所有 string 所在的项目属性在另一个内部不存在 List<string> .

我创建这个控制台应用程序只是为了确保我的 LINQ 语法正确:

class FooBar
{
    public int Id { get; set; }
    public string ValueName { get; set; }
}

然后……

List<FooBar> foobars = new List<FooBar>
{
    new FooBar { Id = 1, ValueName = "Val1" },
    new FooBar { Id = 2, ValueName = "Val2" },
    new FooBar { Id = 3, ValueName = "Val3" },
    new FooBar { Id = 4, ValueName = "Val4" }
};

List<string> myStrings = new List<string>
{
    "Val1",
    "Val3"
};

// Only keep records where ValueName is found in `myStrings`
foobars = foobars.Where(f => myStrings.Contains(f.ValueName)).ToList();

所以，这一行:

foobars = foobars.Where(f => myStrings.Contains(f.ValueName)).ToList();

完全按照我的意愿行事，它返回了这两条记录:

{ Id = 1, ValueName = "Val1" }
{ Id = 3, ValueName = "Val3" }

一切顺利。但是...在实际应用中，foobars拥有超过 20 万件元素，并且 myStrings大约有190k。当执行该 LINQ 行时，需要 5 分钟以上的时间才能完成。

我显然做错了什么。 20 万条记录并不大。和真正的FooBar并没有那么复杂(没有嵌套对象，只有 9 个属性)。

这是怎么回事？

Answer 1

这里的问题是你在做 foobars.Where(f => myStrings.Contains(f.ValueName)) ，所以对于 foobars 中的每个项目你正在检查 myStrings 的所有 项。

按二次比例缩放。也称为 O(n^2)，阅读更多 here . 所以如果你有 10+10 件元素，你会做 100 次检查(10*10)，如果你有 10,000+10,000 件元素，你会做 100,000,000 次检查。 在您的情况下，您正在进行 38,000,000,000 次以上的检查；)

解决方案:创建一个 HashSet来自 myStrings 并使用 HashSet 的 Contains。

例如替换为:

var myStringsSet = new HashSet<string>(myStrings);
foobars = foobars.Where(f => myStringsSet.Contains(f.ValueName)).ToList();

现在有 10,000+10,000 件元素，您将进行 10,000 次检查，而不是 100,000,000 次。在您的情况下，这将是 200,000 张支票，而不是 38,000,000,000 张。