Dictionary/KeyValuePair集合的基数排序实现

Question

我正在寻找一个快速有效的基数排序实现字典/KeyValuePair集合，如果可能的话在C#中(但不是强制性的)。密钥是介于1,000 000和9,999 999 999之间的整数。值的数量在5到数千之间变化。目前我使用的是LINQ-OrderBy，我认为是QuickSort。对我来说，性能真的很重要，我想测试基数排序是否会更快。我只找到了数组实现。当然，我可以自己尝试，但因为我对这个主题还不熟悉，所以我认为它不会是最快、最有效的算法。;-)谢谢。

Rene

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时间(第一次通过循环，大约需要35毫秒)。

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