1

文字列のペアである次の 2 つのリストがあります。1 つは私が期待するもので、もう 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 に答える