LINQ中的速度提升Where(Array.Contains)

Question

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

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

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

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

Answer 1

在LINQ-SQL中,a Contains将被转换为a SELECT ... WHERE field IN(...)并且应该相对较快.但是在LINQ-Objects中,ICollection<T>.Contains如果源是一个,它将调用ICollection<T>.

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

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

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

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

为O(P*S),其中p是的大小previousarray和小号是的大小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));