Dictionary/KeyValuePair 컬렉션을위한 기수 정렬 구현

Question

가능한 경우 C#에서 Dictionary/KeyValuePair 컬렉션을위한 빠르고 효율적인 기수 정렬 구현을 찾고 있습니다 (필수는 아니지만). 키는 1 000 000에서 9 999 999 999까지의 정수입니다. 값의 수는 5에서 수천까지 다양합니다. 현재 LINQ-OrderBy를 사용하고 있습니다. QuickSort라고 생각합니다. 필자에게 성능은 정말로 중요하며 기수 정렬이 더 빠를 것인지 테스트하고 싶습니다. 배열 구현 만 발견되었습니다. 물론 혼자서 시도해 볼 수도 있습니다.하지만이 주제에 익숙하지 않아 가장 빠르고 효율적인 알고리즘이 될 수 없다고 생각합니다. ;-) 고맙습니다.

르네

Answer 1

당신은 LINQ 기반 종류의 프로그램에서 병목 현상이 있음을 결정하기 위해 코드를 테스트 한 적이 있습니까? LINQ의 정렬은 꽤 빠르다. 예를 들어, 아래 코드는 1,000 ~ 10,000 개의 항목을 포함하는 사전 정렬 시간입니다. 1,000 회 이상의 평균 실행 시간은 3.5 밀리 초입니다.

static void DoIt() 
{ 
    int NumberOfTests = 1000; 

    Random rnd = new Random(); 

    TimeSpan totalTime = TimeSpan.Zero; 
    for (int i = 0; i < NumberOfTests; ++i) 
    { 
     // fill the dictionary 
     int DictionarySize = rnd.Next(1000, 10000); 
     var dict = new Dictionary<int, string>(); 
     while (dict.Count < DictionarySize) 
     { 
      int key = rnd.Next(1000000, 9999999); 
      if (!dict.ContainsKey(key)) 
      { 
       dict.Add(key, "x"); 
      } 
     } 
     // Okay, sort 
     var sw = Stopwatch.StartNew(); 
     var sorted = (from kvp in dict 
         orderby kvp.Key 
         select kvp).ToList(); 
     sw.Stop(); 
     totalTime += sw.Elapsed; 
     Console.WriteLine("{0:N0} items in {1:N6} ms", dict.Count, sw.Elapsed.TotalMilliseconds); 
    } 
    Console.WriteLine("Total time = {0:N6} ms", totalTime.TotalMilliseconds); 
    Console.WriteLine("Average time = {0:N6} ms", totalTime.TotalMilliseconds/NumberOfTests); 

보고 된 평균에는 JIT 시간 (루프를 처음 실행하는 데 약 35ms 소요됨)이 포함됩니다.

기수 정렬을 잘 수행하면 정렬 성능이 향상 될 수 있지만 최적화 노력이 다른 곳에서 더 잘 수행 될 것으로 판단됩니다.