사전에 foreach 루프를 반복 실행하려면 일반적인 해시 테이블 액세스가 필요합니까?

Question

주로 성능 집약적 인 응용 프로그램을 작성 중입니다. 오늘 빠른 벤치 마크를 작성한 후 사전 액세스 시간이 배열 액세스 시간 (최대 100 배)보다 현저히 느린 것을 발견했습니다. 둘 다 O (1)이지만. 인터넷에서 비슷한 결과를 찾으려고했지만 아무 소용이 없습니다. 이게 옳은 것 같니? 사전에는 해싱이 관련되어 있고 배열에는 해싱이 없기 때문에 나에게 의미가 있습니다.

저는 이제 사전의 찬반 양론에 대해 무게를 달고, 더 빠른 구현을 시도해야한다고 생각합니다. 적어도 3 개의 응용 프로그램 인스턴스에서 foreach 루프를 사용하여 모든 사전 (상당수 있음)을 반복합니다. 이제는 내 질문에 도달하기 위해 foreach 루프가 "느린"해싱 프로세스를 거쳐야합니까? 아니면 단순히 반복 할 수있는 내부 목록을 유지 관리합니까? 이 경우 사전을 계속 사용할 가능성이 더 큽니다.

몇 가지 추가 정보로, 응용 프로그램은 간단한 2D 게임이며 사전은 게임 엔티티에 저장됩니다. 정말 많은 것이 있습니다. 그리고 네, 이미 작동하는 솔루션이 있습니다. 이것은 사전 최적화가 아닌 사후 최적화입니다.

여기 제가 작성한 벤치 마크입니다. 나는이 분야의 전문가는 아니지만 그것은 매우 잘못된 일 수 있습니다

 public static int dict(Dictionary<key,int> dict, key k) 
     { 
      int i; 
      //dict.TryGetValue(k,out i); 
      i = dict[k]; //both these version yield the same results 

      return i; 
     } 

     public static int arr(int[,] arr, key k) 
     { 
      int i; 
      i = arr[k.x, k.y]; 

      return i; 
     } 

     public struct key 
     { 
      public int x, y; 

      public key (int x, int y){ 
       this.x = x; 
       this.y = y; 
      } 
     } 

     public static void Main() 
     { 
      int dim = 256; 
      Dictionary<key,int> dictVar = new Dictionary<key,int>(dim*dim*10); 

      int[,] arrVar = new int[dim,dim]; 

      for (int i = 0; i < dim; ++i) 
      { 
       for (int j = 0; j < dim; ++j) 
       { 
        arrVar[i, j] = i + j * i; 
        dictVar.Add(new key(i, j), i + i * j); 
       } 
      } 

      const int iterations = 1000000; 
      key k = new key(200, 200); 
      TestTime(dict, dictVar, k, iterations); 
      TestTime(arr, arrVar, k, iterations); 
     } 

     public static void TestTime<T1, T2, TR>(Func<T1, T2, TR> action, T1 obj1, 
               T2 obj2, int iterations) 
     { 
      Stopwatch stopwatch = Stopwatch.StartNew(); 
      for (int i = 0; i < iterations; ++i) 
       action(obj1, obj2); 
      Console.WriteLine(action.Method.Name + " took " + stopwatch.Elapsed); 
     } 

Answer 1

그것이 이상 루프 내부 목록을 유지하지만 목록 유형 Entry<TKey, TValue>[]이다, 그래서 그것은 KeyValuePair 매번를 구성한다. 나는 이것이 경기 침체의 원인이라고 생각할 것입니다.