1

しばらく前に書かれたコードを改善しようとしています。この機能はシステムのコア機能にとって非常に重要であるため、抜本的なオーバーホールには慎重です。

オブジェクトを保持するために辞書を使用しています

Dictionary<Node, int> dConnections

オブジェクトNode自体は、多くの属性といくつかのリストを含む複雑なオブジェクトです。このディクショナリは、約 100 以上のエントリを保持する非常に大きなものになる可能性があります。

現在、辞書に次のようなノードが含まれているかどうかがチェックされています

dConnections.ContainsKey(Node)

したがって、(このノードが辞書にあるかどうかを確認するために) 辞書は、ノード全体とその属性が辞書内のノードと一致するかどうかを確認する必要があると想定しています (一致が見つかるまで、辞書を反復処理し続けます)。これはパフォーマンスに大きな影響を与えますか?

ディクショナリ内のオブジェクトを使用せずに、オブジェクト ID を使用したほうがよいでしょうか。

4

2 に答える 2

5

.NET ディクショナリは内部のハッシュ テーブルです。これは、Node が GetHashCode および Equals メソッドをオーバーライドしない場合、ContainsKey を呼び出すと、次のものと一致することを意味します。

免責事項：要約です。物事はもう少し複雑です。単純化しすぎたので、名前を呼ばないでください。

  1. Node オブジェクトの参照アドレスのハッシュコードのパーティション。パーティションの数は、ハッシュテーブルのバケットの数によって異なります (辞書内のキーの総数によって異なります)。
  2. 複数のノードが同じバケットにある場合は、正確な参照アドレス。

このアルゴリズムは非常に効率的です。辞書に100以上のエントリがあると言っても、それは「たくさん」ではありません。いくつかです。

また、Node オブジェクトのコンテンツは、ContainsKey が一致する方法とは関係がないことも意味します。まったく同じ参照に対して一致し、この参照に対してのみ一致します。

GetHashCode と Equals を自分で実装する場合は、これらのメソッドの戻り値は、インスタンス プロパティが変更されても変更されない (不変である) ことに注意してください。そうしないと、間違ったバケットでキーを取得する可能性が高くなり、完全に到達できなくなります (辞書全体を列挙しなければ)。

于 2012-10-15T10:20:40.033 に答える
3

一致するものが見つかるまで辞書を反復し続けます

いいえ、辞書はすべてのノードを繰り返して一致を見つけるわけではありません。ハッシュコードが最初に取得され、候補を 1 つ、場合によっては少数に制限するために使用されます (ハッシュ方法の良さとバケットサイズによって異なります)。

したがって、（このノードが辞書にあるかどうかを確認するために）辞書は、ノード全体とその属性が辞書のノードと一致するかどうかを確認する必要があると想定しています

いいえ、各候補について、最初にハッシュコードをチェックします。これは、不等号と可等号を非常に迅速に検出するためのショートカットとなることを目的としています。

したがって、ここでの鍵は次のとおりです。あなたNodeのハッシュ方法、別名GetHashCode. これが複雑な場合は、最初に必要になったときにキャッシュするという別の方法があります。つまり、

int cachedHashCode;
public override int GetHashCode() {
    if(cachedHashCode == 0) {
       cachedHashCode = /* some complex code here */
       if(cachedHashCode == 0) {
           cachedHashCode = -45; // why not... just something non-zero
       }
    }
    return cachedHashCode;
}

最後の「同じもの」であるため、これも引き続き使用されることに注意してください。EqualsEqualsEquals

于 2012-10-15T10:22:25.633 に答える