.NET 제네릭 사전을 포함 할 항목 수와 동일한 용량으로 초기화해야합니까?

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

문제

예를 들어 사전에 저장 될 100 개 항목이 있으면 초기화해야합니까?

var myDictionary = new Dictionary<Key, Value>(100);

내 이해는 .NET 사전이 주어진 하중에 도달 할 때 내부적으로 크기를 조정하고 로딩 임계 값은 용량의 비율로 정의된다는 것입니다.

즉, 100 개의 항목이 위 사전에 추가되면 항목 중 하나가 추가 될 때 크기를 조정할 것입니다. 사전 크기를 조정하는 것은 성능에 맞고 기억이 낭비되므로 피하고 싶은 것입니다.

해싱 충돌 가능성은 사전의 하중에 비례합니다. 따라서 사전이 자체적으로 크기를 조정하지 않고 모든 슬롯을 사용하더라도 이러한 충돌로 인해 성능이 저하되어야합니다.

사전 내부에 얼마나 많은 항목이 있는지 알고 있다고 가정하면 사전을 초기화 할 수있는 용량을 어떻게 가장 잘 결정해야합니까?

도움이 되었습니까?

해결책

사전 용량을 초기화 해야하는 것은 두 가지 요소에 따라 다릅니다. (1) gethashcode 함수의 분포 및 (2) 삽입해야 할 항목 수.

해시 함수는 무작위로 분산되어야하거나 입력 세트에 대해 특별히 공식화되어야합니다. 첫 번째를 가정 해 봅시다. 그러나 두 번째로 완벽한 해시 함수를 찾는 데 관심이 있다면.

무작위로 분산 된 해시 함수 인 사전에 삽입 할 100 개의 항목이있는 경우 용량을 100으로 설정 한 다음 ITH 항목을 해시 테이블에 삽입하면 (i-1) / 100 확률이 있습니다. 삽입시 항목은 다른 항목과 충돌합니다. 충돌 확률을 낮추려면 용량을 늘리십시오. 예상 용량을 두 배로 늘리면 충돌 가능성이 떨어집니다.

또한 사전에서 각 항목에 얼마나 자주 액세스 할 것인지 알고 있다면 먼저 삽입 한 항목이 평균적으로 액세스하기가 더 빠르기 때문에 주파수 감소 순서대로 항목을 삽입 할 수 있습니다.

다른 팁

나는 과학적이지 않은 빠른 테스트를했지만 크기를 설정하면 백만 항목을 추가하는 데 1.2207780 초가 걸렸으며 사전에 크기를주지 않으면 추가하는 데 1.5024960 초가 걸렸습니다 ... 이것은 나에게 무시할 수없는 것 같습니다. .

여기 내 테스트 코드가 있습니다. 누군가가 더 엄격한 테스트를 수행 할 수는 있지만 중요하다고 의심합니다.

static void Main(string[] args)
        {
            DateTime start1 = DateTime.Now;
            var dict1 = new Dictionary<string, string>(1000000);

            for (int i = 0; i < 1000000; i++)
                dict1.Add(i.ToString(), i.ToString());

            DateTime stop1 = DateTime.Now;

            DateTime start2 = DateTime.Now;
            var dict2 = new Dictionary<string, string>();

            for (int i = 0; i < 1000000; i++)
                dict2.Add(i.ToString(), i.ToString());

            DateTime stop2 = DateTime.Now;

            Console.WriteLine("Time with size initialized: " + (stop1.Subtract(start1)) + "\nTime without size initialized: " + (stop2.Subtract(start2)));
            Console.ReadLine();
        }

나는 당신이 과도하게 복잡하고 있다고 생각합니다. 사전에 몇 개의 품목이 있는지 아는 경우, 구성시이를 지정하십시오. 이것은 사전이 내부 데이터 구조에 필요한 공간을 할당하여 데이터를 재 할당하고 개편하는 데이터를 피할 수 있도록 도와줍니다.

초기 용량을 지정합니다 Dictionary 추가 작업 중에 사전 값을 저장하는 내부 구조에 크기가 적을 수 있으므로 생성자는 성능을 증가시킵니다.

K의 초기 용량을 Dictionary 그러면 생성자 :

  1. 그만큼 Dictionary K 요소를 저장하는 데 필요한 메모리의 양을 예약합니다.
  2. 사전에 대한 쿼리 성능은 영향을받지 않으며 더 빠르거나 느리지 않습니다.
  3. 추가 작업에는 더 많은 메모리 할당이 필요하지 않으므로 (아마도 비싸다) 더 빨라질 것이다.

에서 MSDN:

사전 (tkey, tvalue)의 용량은 크기 조정이 필요하기 전에 사전 (tkey, tvalue)에 추가 할 수있는 요소의 수입니다. 요소가 사전 (tkey, tvalue)에 추가됨에 따라 내부 배열을 재 할당하여 필요한대로 용량이 자동으로 증가합니다.

컬렉션의 크기를 추정 할 수있는 경우 초기 용량을 지정하면 사전에 요소를 추가하면서 여러 가지 크기 조정 작업을 수행 할 필요가 없습니다 (Tkey, Tvalue).

예, a HashTable 충돌을 해결하기위한 방법으로 재사용을 사용하고 Dictionary 체인을 사용합니다. 그렇습니다. 카운트를 사용하는 것이 좋습니다. a HashTable 당신은 아마 사용하고 싶을 것입니다 count * (1/fillfactor)

초기 크기는 단지 제안 일뿐입니다. 예를 들어, 대부분의 해시 테이블은 소수 또는 2의 전력 인 크기를 갖고 싶어합니다.

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