사전 성능 향상

Question

나는 잠시 후에 작성된 일부 코드를 개선하려고합니다. 이 기능은 시스템의 핵심 기능에 매우 중요하므로 과감한 점검에 대해 신중합니다.

나는 객체

Dictionary<Node, int> dConnections 

Node 자체에 많은 속성과 일부 목록을 포함하는 복잡한 객체 인 객체를 유지하기 위해 사전을 사용하고 있습니다. 이 사전은 100 개가 넘는 항목을 포함하고있을 수 있습니다. 그것은 그래서 그렇게 추정하고

dConnections.ContainsKey(Node) 

같은 노드를 포함하는 경우

는 현재 사전이 확인되고있는 사전 확인해야합니다 (이 노드가 사전에 있는지 확인하기 위해) 경우 전체 노드 및 그것의 속성은 사전에있는 노드와 일치합니다 (일치하는 것을 찾을 때까지 사전을 계속 반복합니다). 그러면 성능에 큰 영향을 미칩니 까?

사전에서 개체를 사용하지 않고 개체 ID를 사용하는 것이 나을 것입니다.

Answer 1

.NET 사전은 Inside의 해시 테이블입니다. 즉, Node가 GetHashCode 및 Equals 메서드를 재정의하지 않으면 ContainsKey를 호출 할 때 다음과 일치합니다.

면책 조항 : 요약입니다. 상황은 좀 더 복잡합니다. 내가 지나치게 단순화했기 때문에 내 이름을 부르지 마라.

1. 노드 객체의 참조 주소의 해시 코드 파티션입니다. (해시 테이블의 총 키 수에 따라) 해시 테이블의 버킷 수에 따른 파티션 수
2. 둘 이상의 노드가 동일한 버킷에있는 경우 정확한 참조 주소.

이 알고리즘은 매우 효율적입니다. 사전에 100 개 이상의 항목이 있다고 말하면 "많이"는 아닙니다. 그것은 약간이다.

이는 Node 객체의 내용이 ContainsKey와 일치하는 방식과 아무 관련이 없음을 의미합니다. 정확히 동일한 참조와 일치하며이 참조에만 적용됩니다.

GetHashCode 및 Equals를 직접 구현하는 경우 인스턴스 속성이 변경 될 때 (변경 불가능한 경우) 이러한 메서드 반환 값이 변경되어서는 안된다는 점에 유의하십시오. 그렇지 않으면 잘못된 버킷에있는 키를 얻을 수 있으므로 전체 사전을 열거하지 않고서는 완전히 도달 할 수 없습니다.

Answer 2

이

아니, 사전은 모든 노드를 반복하여 일치하는 항목을 찾을 수없는 일치를 찾을 때까지이 사전을 반복 계속됩니다

; 먼저 해시 코드를 얻은 다음 해시 코드를 가져와 후보를 1, 어쩌면 몇 가지로 제한하는 데 사용됩니다 (해시 방법이 얼마나 좋고 버킷 크기에 따라 다름)

그래서 나는 이 노드가 사전에 있는지 확인하십시오. 사전은 전체 노드와 그 속성이 사전의 노드와 일치하는지 확인해야합니다.

아니요. 각 후보에 대해 먼저 해시 코드를 확인합니다. 비 -equality vs 가능 -equality 매우 빨리

열쇠는 여기 Node의 해싱 방법 인 GetHashCode입니다. 이 복잡한 경우, 또 다른 트릭은, 그래서 그것을 처음 당신이 그것을 필요로 할 때, 그것은 여전히 마지막으로 "그들에게 동일"너무 Equals를 사용 않는 즉

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; 
} 

주를 캐시하는 것입니다 분명히 Equals도 가능한 한 빨리되도록하고 싶습니다. 그러나 Equals은 비교적 드물게 호출됩니다.