字典/KeyValuePair集合的基数排序实现

本文关键字：基数排序 实现 集合 KeyValuePair 字典 | 更新日期: 2023-09-27 18:10:29

如果可能的话，我正在寻找一个快速有效的字典/KeyValuePair集合的基数排序实现(但不是强制性的)。密钥为1 000 000 ~ 9 999 999 999之间的整数。值的数量在5到几千之间变化。现在我用的是LINQ-OrderBy，也就是快速排序。对我来说，性能真的很重要，我想测试一下基数排序是否会更快。我发现只有数组实现。当然，我可以自己尝试一下，但因为我是这个话题的新手，我相信它不会是最快和最有效的算法。;-）谢谢你。

Rene

字典/KeyValuePair集合的基数排序实现

您是否测试了您的代码以确定基于linq的排序是程序中的瓶颈?LINQ的排序非常快。例如，下面的代码对包含1,000到10,000个条目的字典进行排序。超过1000次运行的平均值大约为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毫秒)。

虽然一个好的基数排序实现可能会提高您的排序性能，但我怀疑您的优化工作最好花在其他地方。

相关文章：