詞典/ KeyValuePair收集的基數排序實現

如果可能在C＃（但不是強制性的），我正在尋找一個快速和有效的詞典/ KeyValuePair收集的基數排序實現。關鍵是1 000 000和9 999 999 999之間的整數。值的數量在5到數千之間變化。目前我正在使用LINQ-OrderBy，這是我認爲的QuickSort。對我而言，性能非常重要，我想測試一個基數排序是否會更快。我只找到數組實現。當然，我可以自己嘗試，但因爲我對這個主題不熟悉，所以我認爲它不會是最快和最有效的算法。 ;-) 謝謝。詞典/ KeyValuePair收集的基數排序實現

劉若英

來源

2011-10-03 Rene

使用您找到的數組實現之一併保留兩個數組：一個使用鍵，一個使用值。修改實現，以便對鍵數組進行排序，並且每當進行修改時，都會對values數組進行相同的修改。 – dtb

是的，我已經有了一個類似的想法，也有兩個列表。但我認爲管理兩個列表會破壞快速基數排序的優勢，因爲這種差異對QuickSort來說不夠大。 – Rene

有您測試代碼，以確定基於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時間（第一次通過循環，大約需要35 ms）。

鑑於一個好的基數排序實現可能會提高排序性能，我懷疑你的優化工作會更好地花在其他地方。

來源

2011-10-03 15:54:15

感謝Jim的測試。我沒有說這種類型是我的程序中的瓶頸，但我試圖改善我的代碼在各個角落的性能。我已經在毫秒範圍內運行我的程序。所以一切都很重要:-) – Rene

詞典/ KeyValuePair收集的基數排序實現

回答

相關問題