1

グラフ エッジを表すために、C# で次の構造を使用しています。

struct Edge
{
    public Edge(int leftA, int leftB, int leftC, int leftD, int rightA, int rightB, int rightC, int rightD)
    {
        LeftIdA = leftA;
        LeftIdB = leftB;
        LeftIdC = leftC;
        LeftIdD = leftD;

        RightIdA = rightA;
        RightIdB = rightB;
        RightIdC = rightC;
        RightIdD = rightD;
    }

    public readonly int LeftIdA;
    public readonly int LeftIdB;
    public readonly int LeftIdC;
    public readonly int LeftIdD;

    public readonly int RightIdA;
    public readonly int RightIdB;
    public readonly int RightIdC;
    public readonly int RightIdD;
}

そして、重複がないように、HashSet に大量 (約 500 万個) を格納する必要があります。速度を最適化するための GetHashCode の適切な実装は何でしょうか?

次のように、返された整数に各 ID の 4 ビットを格納しようとしました。

    public override int GetHashCode()
    {
        int A = LeftIdA & 0xF;
        int B = LeftIdB & 0xF;
        int C = LeftIdC & 0xF;
        int D = LeftIdD & 0xF;

        int E = RightIdA & 0xF;
        int F = RightIdB & 0xF;
        int G = RightIdC & 0xF;
        int H = RightIdD & 0xF;

        int result = A;
        result = (result << 4) | B;
        result = (result << 4) | C;
        result = (result << 4) | D;
        result = (result << 4) | E;
        result = (result << 4) | F;
        result = (result << 4) | G;
        result = (result << 4) | H;

        return result;
    }

リストに項目を追加するよりも 80% 遅くなります。

4

3 に答える 3

1

速度を最適化するための GetHashCode の適切な実装は何でしょうか?

すべてのフィールドが読み取り専用であるため、おそらく最善の策は、コンストラクターでハッシュコードを事前に計算し、それを から返すことですGetHashCode。

ハッシュコードを事前に計算するには、Guffa の回答の式を使用できます。

于 2013-07-15T15:33:27.947 に答える
0

willへの追加にはHashSet時間がかかりますが、これは GetHashCode()実装の戦略が悪いためではありません。実際、この実装はかなり良さそうです。AHashSetは、バケツをセットアップしてそれらに物を入れるなど、あらゆる種類の狂ったがらくたを内部で行う必要があります。

パフォーマンスの向上は、ハッシュセット内の要素の検索にあります。500 万個の個別の項目をリストとハッシュセットに追加してみて、特定の Edge が含まれているかどうかをどのコンテナーがより迅速に判断できるかを確認してください。その場合、2 倍未満のセットアップ時間を喜んで支払うかもしれません。

于 2013-07-14T23:41:56.377 に答える
0

最適に機能するには、ハッシュ コードは衝突をできるだけ少なくする必要があります。つまり、できるだけ多様なハッシュ コードを生成する必要があります。

すべてのメンバーからのすべてのデータが使用されるように、ハッシュ コードを作成してみてください。

public override int GetHashCode() {
  return
    LeftIdA ^ LeftIdB ^ LeftIdC ^ LeftIdD ^
    RightIdA ^ RightIdB ^ RightIdC ^ RightIdD;
}

素数を掛けると非常に良い分布が得られるため、自分のケースでパフォーマンスが向上するかどうかをテストする必要があります。

public override int GetHashCode() {
  return
    ((((((LeftIdA * 251 + LeftIdB) * 251 + LeftIdC) * 251 +
    LeftIdD) * 251 + RightIdA) * 251 + RightIdB) * 251 +
    RightIdC) * 251 + RightIdD;
}

注: 構造体に対して最適化された等値比較も提供していることを確認してください。デフォルトの実装では、リフレクションを使用して比較するすべてのメンバーを決定するため、かなり遅くなります。

編集：

いくつかのテストを行ったところ、2 番目の実装では、約 2 秒で 500 万の項目を HashSet に追加できました。

于 2013-07-15T00:04:13.600 に答える