字典/KeyValuePair 集合的基数排序实现
如果可能的话,我正在寻找一种快速有效的字典/KeyValuePair 集合的基数排序实现(如果可能的话)(但不是强制性的)。键是 1 000 000 到 9 999 999 999 之间的整数。值的数量在 5 到几千之间变化。 目前我正在使用 LINQ-OrderBy,我认为这就是 QuickSort。对我来说,性能非常重要,我想测试基数排序是否会更快。 我只找到了数组实现。当然,我可以自己尝试,但因为我对这个主题很陌生,所以我相信它不会是最快和最有效的算法。 ;-) 谢谢。
雷内
I'm looking for a fast and efficient Radix-Sort Implementation for Dictionary/KeyValuePair Collection if possible in C# (but not mandatory). The key is an Integer between 1 000 000 and 9 999 999 999. The number of values are varying between 5 to several thousand.
At the moment I'm using LINQ-OrderBy, which is I think QuickSort. For me performance is really important and I would like to test whether a Radix-Sort would be faster.
I found only Array implementations. Of course I could try it by myself but because I'm new to this topic I believe it wouldn't be the fastest and most efficient algorithm. ;-)
Thank you.
Rene
您是否测试过代码以确定基于 LINQ 的排序是程序中的瓶颈? LINQ 的排序非常快。例如,下面的代码对包含 1,000 到 10,000 个项目的字典进行排序。超过 1,000 次运行的平均时间约为 3.5 毫秒。
请注意,报告的平均值包括 JIT 时间(第一次通过循环,大约需要 35 毫秒)。
尽管良好的基数排序实现可能会提高排序性能,但我怀疑您的优化工作最好花在其他地方。
Have you tested your code to determine that the LINQ-based sort is the bottleneck in your program? LINQ's sort is pretty darned quick. For example, the code below times the sorting of a dictionary that contains from 1,000 to 10,000 items. The average, over 1,000 runs, is on the order of 3.5 milliseconds.
Note that the reported average includes the JIT time (the first time through the loop, which takes approximately 35 ms).
Whereas it's possible that a good radix sort implementation will improve your sorting performance, I suspect your optimization efforts would be better spent somewhere else.