c# - 比较两个列表时提高性能

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)