词典/ 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收集的基数排序实现

回答

相关问题