c# - 为什么这个 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> )。