c# - LINQ Where(Array.Contains) 中的速度改进

Question

我最初有一个包含 LINQ 查询返回的方法，int[]后来以类似于以下方式使用它：

int[] result = something.Where(s => previousarray.Contains(s.field));

事实证明这非常慢，直到第一个数组被检索为 native IQueryable<int>。它现在运行得非常快，但我想知道如果我int[]从其他地方提供了一个然后必须按上述方式使用的情况，我将如何处理这种情况。

在这种情况下有没有办法加快查询速度？转换为列表似乎没有帮助。

score 17 · Accepted Answer

在 LINQ-SQL 中，aContains将转换为 aSELECT ... WHERE field IN(...)并且应该相对较快。然而，在 LINQ-Objects 中，ICollection<T>.Contains如果源是ICollection<T>.

当 LINQ-SQL 结果被视为 anIEnumerable而不是时IQueryable，您将丢失 linq 提供程序 - 即，任何进一步的操作都将在内存中而不是在数据库中完成。

至于为什么它的内存慢得多：

Array.Contains()是一个 O(n) 操作所以

something.Where(s => previousarray.Contains(s.field));

是 O(p * s)，其中p是的大小，previousarrays是的大小something。

HashSet<T>.Contains()另一方面是 O(1) 操作。如果你首先创建一个哈希集，你会看到操作上有很大的改进，.Contains因为它将是 O(s) 而不是 O(p * s)。

例子：

var previousSet = new HashSet<int>(previousarray);
var result = something.Where(s => previousSet.Contains(s.field));

score 0 · Accepted Answer

Lists/Arrays/ IEnumarables等是 O[N] 操作。在HashSet上是 O[~1] 。所以你应该尝试使用它。

2 回答 2