조회 최적화 : 사전 키 조회 대 배열 인덱스 조회

StackOverflow https://stackoverflow.com/questions/908050

  •  05-09-2019
  •  | 
  •  

문제

나는 내 애완 동물 프로젝트 중 하나로 7 카드 포커 핸드 평가자를 쓰고 있습니다. 속도를 최적화하려고 노력하는 동안 (도전을 좋아합니다) 사전 키 조회의 성능이 Array Index Lookup에 비해 상당히 느리다는 것을 알게되어 충격을 받았습니다.

예를 들어, 52 개를 모두 열거하는이 샘플 코드를 실행했습니다. 7 = 133,784,560 가능한 7 카드 핸즈 :

var intDict = new Dictionary<int, int>();
var intList = new List<int>();
for (int i = 0; i < 100000; i ++)
{
    intDict.Add(i, i);  
    intList.Add(i);
}

int result;

var sw = new Stopwatch();
sw.Start();
for (int card1 = 0; card1 < 46; card1++)
  for (int card2 = card1 + 1; card2 < 47; card2++)
    for (int card3 = card2 + 1; card3 < 48; card3++)
      for (int card4 = card3 + 1; card4 < 49; card4++)
        for (int card5 = card4 + 1; card5 < 50; card5++)
          for (int card6 = card5 + 1; card6 < 51; card6++)
            for (int card7 = card6 + 1; card7 < 52; card7++)
              result = intDict[32131]; // perform C(52,7) dictionary key lookups
sw.Stop();
Console.WriteLine("time for dictionary lookups: {0} ms", sw.ElapsedMilliseconds);

sw.Reset();

sw.Start();
for (int card1 = 0; card1 < 46; card1++)
  for (int card2 = card1 + 1; card2 < 47; card2++)
    for (int card3 = card2 + 1; card3 < 48; card3++)
      for (int card4 = card3 + 1; card4 < 49; card4++)
        for (int card5 = card4 + 1; card5 < 50; card5++)
          for (int card6 = card5 + 1; card6 < 51; card6++)
            for (int card7 = card6 + 1; card7 < 52; card7++)
              result = intList[32131]; // perform C(52,7) array index lookups
sw.Stop();
Console.WriteLine("time for array index lookups: {0} ms", sw.ElapsedMilliseconds);

출력 :

time for dictionary lookups: 2532 ms
time for array index lookups: 313 ms

이러한 유형의 행동이 예상됩니까 (성능은 8 배 감소)? IIRC, 사전은 평균적으로 O (1) 조회를 가지고 있으며, 배열에는 최악의 O (1) 조회가 있으므로 배열 조회가 더 빠르지 않지만 그다지 많지는 않습니다!

나는 현재 사전에 포커 핸드 랭킹을 저장하고 있습니다. 나는 이것이 사전 조회가 될 수있는만큼 빠른 경우, 내 접근 방식을 다시 생각하고 대신 배열을 사용해야한다고 생각하지만, 순위를 색인화하는 것은 약간 까다로워지고 아마도 그것에 대해 또 다른 질문을해야 할 것입니다.

도움이 되었습니까?

해결책

Big -O 표기법은 크기 (ETC)와 관련하여 복잡성이 어떻게 증가하는지 말하면 잊지 마십시오. 관련된 요인을 나타내는 것은 아닙니다. 그렇기 때문에 때로는 선형조차도됩니다 검색 키는 키가 충분하지 않은 경우 사전 조회보다 빠릅니다. 이 경우 배열과 함께 검색을 수행하지도 않습니다. 단지 직선 색인화 작업 만하면됩니다.

직선 인덱스 조회의 경우 배열이 기본적으로 이상적입니다. 

pointer_into_array = base_pointer + offset * size

(그리고 그런 다음 포인터 피로.)

사전 조회를 수행하는 것은 비교적 복잡합니다. 키가 많을 때 키의 선형 조회와 비교할 때 매우 빠르지 만 직선 어레이 조회보다 훨씬 더 복잡합니다. 키의 해시를 계산 한 다음 중복 해시 (또는 중복 버킷)를 다루는 버킷을 해결 한 다음 평등을 확인해야합니다.

항상 그렇듯이 작업에 적합한 데이터 구조를 선택하고 배열로 인덱싱을 할 수있는 경우 (또는 List<T>) 그렇습니다. 맹목적으로 빠를 것입니다.

다른 팁

이러한 유형의 행동이 예상됩니까 (성능은 8 배 감소)?

왜 안 돼? 각 배열 조회는 거의 참을성이 없거나 무시할 수있는 반면 사전 조회는 최소한 추가 서브 루틴 호출이 필요할 수 있습니다.

둘 다 O (1)의 요점은 각 컬렉션에 50 배 더 많은 항목이 있더라도 성능 감소는 여전히 (8)의 요인 일뿐임을 의미합니다.

무언가는 밀레늄을 취할 수 있지만 여전히 O (1) 일 수 있습니다.

분해 창 에서이 코드를 통해 단일 단계가 있다면 차이가 무엇인지 빠르게 이해하게됩니다.

사전 구조는 키 공간이 매우 크고 안정적인 시퀀싱 순서로 매핑 할 수없는 경우 가장 유용합니다. 키를 비교적 작은 범위의 간단한 정수로 변환 할 수 있다면 배열보다 더 잘 수행되는 데이터 구조를 찾기가 어려워집니다.

구현 메모에서; .NET에서 사전은 본질적으로 해체식입니다. 키가 고유 한 값의 큰 공간으로 키가 해시되도록함으로써 키 룩업 성능을 다소 향상시킬 수 있습니다. 그것은 당신의 경우, 당신은 간단한 정수를 열쇠로 사용하고 있습니다 (나는 자체 가치에 해시를 믿습니다) - 당신이 할 수있는 최선 일 수 있습니다.

배열 조회는 당신이 할 수있는 가장 빠른 일에 관한 것입니다. 본질적으로 모든 것은 배열의 시작에서 찾기 원하는 요소로 이동하는 단일 포인터 산술입니다. 반면, 사전 조회는 해싱을 수행해야하며 올바른 버킷을 찾는 데 관심이 있기 때문에 다소 느리게 발생할 수 있습니다. 예상 런타임도 O (1)이지만 알고리즘 상수가 더 커서 느려집니다.

Big-O 표기법에 오신 것을 환영합니다. 당신은 항상 일정한 요인이 관련되어 있음을 고려해야합니다.

하나의 dict-lookup을하는 것은 물론 배열 조회보다 훨씬 비쌉니다.

Big-O는 알고리즘이 어떻게 스케일되는지 알려줍니다. 조회량을 두 배로 늘리고 숫자가 어떻게 바뀌는 지 확인하십시오. 둘 다 시간이 두 번 걸립니다.

a에서 요소를 검색하는 비용 사전은 O (1)입니다., 그러나 그것은 사전이 해시 가능으로 구현 되었기 때문입니다. 따라서 먼저 해시 값을 계산하여 어떤 요소를 반환할지 알아야합니다. 해시블은 종종 그렇게 효율적이지 않지만 대형 데이터 세트 또는 고유 한 호쉬 값이 많은 데이터 세트에 좋습니다.

목록 (링크 된 목록이 아닌 배열을 비난하는 데 사용되는 쓰레기 단어와는 별도로)은 반환하려는 요소를 직접 계산하여 값을 반환하므로 더 빠릅니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top