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

发布于 12-07 12:21 字数 258 浏览 2 评论 0原文

如果可能的话,我正在寻找一种快速有效的字典/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

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

滴情不沾2024-12-14 12:21:41

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

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

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.

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);

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.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文