为什么这个List.Except在某些情况下如此缓慢(以及如何加快速度)？

Question

我有以下两个列表,它们是字符串对.一个是我的期望,另一个是我发现的.我想找出遗漏的东西.代码有效,但有些情况比其他情况慢得多.

• 当n = 1时,.Except()呼叫需要21秒.
• 当n = 10时,.Except()呼叫需要2秒.

在这两种情况下,它都是相同数量的元素.这只是一些哈希表冲突吗？我能做些什么来使所有案件同样快速？

List<KeyValuePair<string, string>> FoundItems = new List<KeyValuePair<string, string>>();
List<KeyValuePair<string, string>> ExpectedItems = new List<KeyValuePair<string, string>>();

int n = 1;
for (int k1 = 0; k1 < n; k1 ++)
{
    for (int k2 = 0; k2 < 3500/n; k2++)
    {
        ExpectedItems.Add(new KeyValuePair<string, string>( k1.ToString(), k2.ToString()));
        if (k2 != 0)
        {
            FoundItems.Add(new KeyValuePair<string, string>(k1.ToString(), k2.ToString()));
        }
    }
}

Stopwatch sw = new Stopwatch();
sw.Start();

//!!!! This is the slow line.
List<KeyValuePair<string, string>> MissingItems = ExpectedItems.Except(FoundItems).ToList();
//!!!! 

string MatchingTime = "Matching Time: " + sw.ElapsedMilliseconds.ToString() + " (" + sw.ElapsedMilliseconds / 1000 + " sec)";
MessageBox.Show(MatchingTime + ", " + ExpectedItems.Count() + " items");

我的数据确实是字符串,我只是在这个测试用例中使用整数,因为它很容易.

Answer 1

是的,我相信问题是KeyValuePair在第一个领域实际上只有哈希(有一些奇怪的东西 - 它并不那么简单).

例如:

using System;
using System.Collections.Generic;

class Test
{
    static void Main()
    {
        ShowPairHash("a", "b");
        ShowPairHash("a", "c");
        ShowPairHash("Z", "0");
        ShowPairHash("Z", "1");
    }

    static void ShowPairHash(string x, string y)
    {
        var pair = new KeyValuePair<string, string>(x, y);
        Console.WriteLine(pair.GetHashCode());
    }
}

输出:

733397256
733397256
733397325
733397325

所以当n = 1,所有项目具有相同的散列码......所以一切都需要进行检查完全平等每除了HashSet<T>这里面建Except.

如果您将KeyValuePair通话更改为

new KeyValuePair<string, string>(k2.ToString(), k1.ToString())

...然后n = 1的情况非常快.

但更好:使用具有更好哈希码计算的类型.例如,匿名类型,或者Tuple<string, string>,或者您自己的自定义结构版本Tuple<string, string>(但实现IEquatable<T>).