比较两个列表时提高性能

Question

在比较两个列表中的项目时,我有哪些选择？我遇到了一些性能问题,我想知道是否有更快的替代方案:

int[] foo = { 1, 2, 3, 4, 5 };
int[] bar = { 6, 7, 8, 9, 1 };

var result = foo.Any(x => bar.Contains(x));

无论我使用lambda方法foreach还是单独使用,我都认为性能损失仍然存在O(N^2).我可以做任何影响吗？

Answer 1

您可以使用Enumerable.Intersect:

var result = foo.Intersect(bar).Any();

这是Set<T>从bar项目创建,然后枚举foo直到找到第一个匹配.内部看起来像:

Set<int> set = new Set<int>();

foreach (int local in bar) // M times
    set.Add(local); // O(1)

foreach (int value in foo) // N times max
{
    if (!set.Remove(value)) // O(1)
        continue;

    yield return value;
}

正如PatrykĆwiek正确指出的那样,给你O(N + M)而不是O(N*M)