Dictionary

Question

과 비교했을 때 SortedDictionary의 예상치 못한 성능 저하 SortedDictionary의 성능이 값 설정 및 검색을 위해 사전보다 약 5 배 느린 이유를 알지 못합니다. 삽입과 삭제가 느리지 만 업데이트 나 검색이 아닌 것으로 예상됩니다. 나는 .Net 3.5와 .Net 4.0 컴파일 된 코드를 테스트했다. 랜덤 키의 배열은 무작위 변화가 랜덤 액세스의 차이에 대한 책임이 없음을 보장하기 위해 미리 계산되었습니다.

테스트 된 다음과 같은 시나리오가 있습니다.

각 값
1. 순차적 인 갱신하는 열쇠 접근 각 값
2. 순차 액세스하여를 이용하여 키] 접근
키 TryGetValue 각 값
3. 랜덤 액세스 사용하여 [사용하여 각 값
4. 순차 액세스 ] TryGetValue

사람이 왜 성능 차이를 알고 사용하여 각 값의

랜덤 액세스 접근 자?

내가 잘못하거나 어리석은 짓을하고 있다면 제발 지적 해주세요.

예제 코드 : SortedDictionary로 사전을 전환하여 차이를 테스트하기 만하면됩니다.

const int numLoops = 100; 
    const int numProperties = 30; 
    const int numInstances = 1000; 

    static void DictionaryBench(int numLoops, int numValues, int numInstances, string[] keyArray) 
    { 
     Stopwatch sw = new Stopwatch(); 
     double total = 0.0d; 

     for (int j = 0; j < numLoops; j++) 
     { 
      //sw.Start(); 
      Dictionary<string, object> original = new Dictionary<string, object>(numValues); 
      for (int i = 0; i < numValues; i++) 
      { 
       original.Add(String.Format("Key" + i.ToString()), "Value0:" + i.ToString()); 
      } 
      List<Dictionary<string, object>> collectionList = new List<Dictionary<string, object>>(numInstances); 
      for (int i = 0; i < numInstances; i++) 
      { 
       collectionList.Add(new Dictionary<string, object>(original)); 
      } 
      sw.Start(); 
      //Set values on each cloned instance to uniqe values using the same keys 
      for (int k = 0; k < numInstances; k++) 
      { 
       for (int i = 0; i < numValues; i++) 
       { 
        collectionList[k]["Key" + i.ToString()] = "Value" + k.ToString() + ":" + i.ToString(); 
       } 
      } 

      //Access each unique value 
      object temp; 
      for (int k = 0; k < numInstances; k++) 
      { 
       for (int i = 0; i < numValues; i++) 
       { 
        temp = collectionList[k]["Key" + i.ToString()]; 
       } 
      } 
      //Random access 
      //sw.Start(); 
      for (int k = 0; k < numInstances; k++) 
      { 
       for (int i = 0; i < numValues; i++) 
       { 
        collectionList[k].TryGetValue(keyArray[i],out temp); 
       } 
      } 
      sw.Stop(); 
      total += sw.ElapsedMilliseconds; 
      sw.Reset(); 
     } 

Answer 1

SortedDictionary은 O ( 로그 n) 인 이진 검색 조회를 사용합니다.
Dictionary은 O (1) 인 해시 테이블을 사용합니다.

따라서 Dictionary은 더 빠른 조회를 제공합니다.

차이점은 비교하는 데 비용이 많이 드는 문자열 키의 경우 더 커집니다.
Dictionary은 문자열을 두 번 반복합니다 (해시 충돌이있는 경우). 한 번만 해시 코드를 계산하고 한 번만 정확하게 일치하는지 확인합니다. SortedDictionary은 의 문자열을 모두 비교로 반복합니다.

Answer 2

나는 그렇게 생각하지 않는다. Others have gotten the same results.

나는 그것이 왜 다른 사람보다 느린 지 알기 쉽다. SortedDictionary는 더 많은 작업을 수행합니다. 그것은 정렬 중입니다. 사전은 아니므로 더 빠릅니다.

수행해야 할 대상과 수행해서는 안되는 유일한 진정한 테스트는 위에서 수행 한 테스트입니다. 네가 여기 뭔가 잘못한 것 같지 않아.