1

如果可能在 C# 中（但不是强制性的），我正在为 Dictionary/KeyValuePair Collection 寻找一种快速有效的 Radix-Sort 实现。键是介于 1 000 000 和 9 999 999 999 之间的整数。值的数量在 5 到数千之间变化。目前我正在使用 LINQ-OrderBy，我认为这是 QuickSort。对我来说，性能真的很重要，我想测试 Radix-Sort 是否会更快。我发现只有 Array 实现。当然我可以自己尝试，但因为我是这个主题的新手，我相信它不会是最快和最有效的算法。;-） 谢谢。

雷内

4

1 回答 1

0

您是否测试过您的代码以确定基于 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 毫秒）。

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

于 2011-10-03T15:54:15.680 回答