1

我有以下两个列表，它们是成对的字符串。一个是我所期望的，另一个是我发现的。我想找出缺少的东西。该代码有效，但有些情况比其他情况慢得多。

  • 当 n = 1 时，调用需要 21 秒.Except()。
  • 当 n = 10 时，调用需要 2 秒.Except()。

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

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");

我的数据确实是字符串，我在这个测试用例中只使用整数，因为它很简单。

4

1 回答 1

5

是的，我认为问题在于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>）。

于 2012-10-18T20:34:23.120 回答