C# 中是否有一个好的浮点数基数排序实现

2024-04-17

我有一个带有浮点类型字段的数据结构。这些结构的集合需要按浮点值排序。是否有一个基数排序实现。

如果没有,是否有一种快速的方法来访问指数、符号和尾数。 因为如果你首先对尾数、指数和最后一次的指数对浮点数进行排序。您对浮点数进行排序的时间复杂度为 O(n)。


Update:

我对这个主题很感兴趣,所以我坐下来实现了它(使用这种非常快速且节省内存的实现 https://en.wikibooks.org/wiki/Algorithm_implementation/Sorting/Radix_sort)。我也读过this one https://www.codercorner.com/RadixSortRevisited.htm(谢谢celion https://stackoverflow.com/users/224264/celion)并发现您甚至不必将浮点数拆分为尾数和指数来对其进行排序。您只需一对一地获取这些位并执行 int 排序。您只需要关心负值,这些负值必须在算法结束时相反地放在正值前面(我在算法的最后一次迭代中一步完成了这一点,以节省一些 CPU 时间)。

这是我的浮点基数排序:

public static float[] RadixSort(this float[] array)
{
    // temporary array and the array of converted floats to ints
    int[] t = new int[array.Length];
    int[] a = new int[array.Length];
    for (int i = 0; i < array.Length; i++)
        a[i] = BitConverter.ToInt32(BitConverter.GetBytes(array[i]), 0);

    // set the group length to 1, 2, 4, 8 or 16
    // and see which one is quicker
    int groupLength = 4;
    int bitLength = 32;

    // counting and prefix arrays
    // (dimension is 2^r, the number of possible values of a r-bit number) 
    int[] count = new int[1 << groupLength];
    int[] pref = new int[1 << groupLength];
    int groups = bitLength / groupLength;
    int mask = (1 << groupLength) - 1;
    int negatives = 0, positives = 0;

    for (int c = 0, shift = 0; c < groups; c++, shift += groupLength)
    {
        // reset count array 
        for (int j = 0; j < count.Length; j++)
            count[j] = 0;

        // counting elements of the c-th group 
        for (int i = 0; i < a.Length; i++)
        {
            count[(a[i] >> shift) & mask]++;

            // additionally count all negative 
            // values in first round
            if (c == 0 && a[i] < 0)
                negatives++;
        }
        if (c == 0) positives = a.Length - negatives;

        // calculating prefixes
        pref[0] = 0;
        for (int i = 1; i < count.Length; i++)
            pref[i] = pref[i - 1] + count[i - 1];

        // from a[] to t[] elements ordered by c-th group 
        for (int i = 0; i < a.Length; i++){
            // Get the right index to sort the number in
            int index = pref[(a[i] >> shift) & mask]++;

            if (c == groups - 1)
            {
                // We're in the last (most significant) group, if the
                // number is negative, order them inversely in front
                // of the array, pushing positive ones back.
                if (a[i] < 0)
                    index = positives - (index - negatives) - 1;
                else
                    index += negatives;
            }
            t[index] = a[i];
        }

        // a[]=t[] and start again until the last group 
        t.CopyTo(a, 0);
    }

    // Convert back the ints to the float array
    float[] ret = new float[a.Length];
    for (int i = 0; i < a.Length; i++)
        ret[i] = BitConverter.ToSingle(BitConverter.GetBytes(a[i]), 0);

    return ret;
}

它比 int 基数排序稍慢,因为在函数的开头和结尾进行数组复制,其中浮点数按位复制到 int 并返回。尽管如此,整个函数仍然是 O(n)。无论如何,比像你建议的那样连续排序 3 次要快得多。我看不到太多优化空间,但如果有人这样做:请随时告诉我。

要降序排序,请在最后更改此行:

ret[i] = BitConverter.ToSingle(BitConverter.GetBytes(a[i]), 0);

to this:

ret[a.Length - i - 1] = BitConverter.ToSingle(BitConverter.GetBytes(a[i]), 0);

测量:

我设置了一些简短的测试,包含浮点数的所有特殊情况(NaN、+/-Inf、最小/最大值、0)和随机数。它的排序顺序与 Linq 或Array.Sort对浮点数进行排序:

NaN -> -Inf -> Min -> Negative Nums -> 0 -> Positive Nums -> Max -> +Inf

所以我用大量 10M 数字进行了测试:

float[] test = new float[10000000];
Random rnd = new Random();
for (int i = 0; i < test.Length; i++)
{
    byte[] buffer = new byte[4];
    rnd.NextBytes(buffer);
    float rndfloat = BitConverter.ToSingle(buffer, 0);
    switch(i){
        case 0: { test[i] = float.MaxValue; break; }
        case 1: { test[i] = float.MinValue; break; }
        case 2: { test[i] = float.NaN; break; }
        case 3: { test[i] = float.NegativeInfinity; break; }
        case 4: { test[i] = float.PositiveInfinity; break; }
        case 5: { test[i] = 0f; break; }
        default: { test[i] = test[i] = rndfloat; break; }
    }
}

并停止了不同排序算法的时间:

Stopwatch sw = new Stopwatch();
sw.Start();

float[] sorted1 = test.RadixSort();

sw.Stop();
Console.WriteLine(string.Format("RadixSort: {0}", sw.Elapsed));
sw.Reset();
sw.Start();

float[] sorted2 = test.OrderBy(x => x).ToArray();

sw.Stop();
Console.WriteLine(string.Format("Linq OrderBy: {0}", sw.Elapsed));
sw.Reset();
sw.Start();

Array.Sort(test);
float[] sorted3 = test;

sw.Stop();
Console.WriteLine(string.Format("Array.Sort: {0}", sw.Elapsed));

输出是(更新:现在使用发布版本运行,而不是调试):

RadixSort: 00:00:03.9902332
Linq OrderBy: 00:00:17.4983272
Array.Sort: 00:00:03.1536785

大约比 Linq 快四倍多。那还不错。但还没有那么快Array.Sort,但也没有那么糟糕。但我对此感到非常惊讶:我预计它在非常小的数组上会比 Linq 稍微慢一些。但后来我只用 20 个元素进行了测试:

RadixSort: 00:00:00.0012944
Linq OrderBy: 00:00:00.0072271
Array.Sort: 00:00:00.0002979

即使这次我的 Radixsort 也比 Linq 更快,但是way比数组排序慢。 :)

更新2:

我做了一些更多的测量,发现了一些有趣的事情:更长的组长度常数意味着更少的迭代和更多的内存使用。如果使用 16 位的组长度(仅 2 次迭代),则在对小数组进行排序时会产生巨大的内存开销,但可以击败Array.Sort如果数组的元素数量超过 100k,即使数量不是很多。图表轴均已对数化:

comparison chart
(source: daubmeier.de http://daubmeier.de/philip/stackoverflow/radixsort_vs_arraysort.png)

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

C# 中是否有一个好的浮点数基数排序实现 的相关文章

随机推荐

  • 在 Fabric.js 中真正旋转等边三角形的中心

    使用 Fabric js 我无法真正围绕其中心点旋转三角形 或者至少我认为应该是中心点 我创建了一个jsFiddle http jsfiddle net UW8Be 这表明 三角形很简单 我用了originX center 原点Y 也是如此
  • 将 Typeahead 与 Google 自定义搜索引擎结合使用

    我正在尝试让 Twitter Typeahead Bloodhound 与 Google 的 CSE 配合使用 到目前为止 我已经成功返回结果 但无法计算出 datumTokenizer var results new Bloodhound
  • SSIS 错误 - 无法执行事务操作,因为有正在处理此事务的待处理请求

    在执行 ssis 包时 出现以下错误 The transaction operation cannot be performed because there are pending requests working on this tran
  • Excel - 从单元格范围创建图表,同时排除空值?

    我有这张 Excel 工作表 其中基本上包含大量数据 现在 此 Excel 工作表通过导入数据的宏动态更新 因此数据可能会发生变化 这意味着某些单元格可能会被填充 而其他单元格则不会 所以我在工作表 2 中从 A2 A60 到 M2 M60
  • 如何更改TTLauncherItem中标题的颜色?

    我在尝试更改 TTLauncherItem 中的颜色时遇到很多麻烦 因为默认的灰色不适合我的背景 有任何想法吗 这是我用来更改文本颜色的TTLauncherItem从默认的灰色变为黑色 在白色背景上看起来更好 1 创建一个继承自的样式表TT
  • 如何更改诺基亚全触摸 lwuit 表单标题颜色

    我想更改基于诺基亚 lwuit 的全触摸表单的标题颜色 我尝试过 setTitleComponent 方法 但它不起作用 另请检查以下链接http projects developer nokia com LWUIT for Series
  • 有没有像 Haskell 的 Threadscope 这样的 C/C++ 线程跟踪器?

    有没有像这样的免费开源工具线程范围 http research microsoft com en us projects threadscope 并且比NPTL 追踪工具 http nptltracetool sourceforge net
  • 从 SQL Server 查询 Python 中的二进制值

    我正在执行这个查询 SELECT CMDB ID FROM DB1 dbo CDMID 当我在 SSMS 18 上执行此操作时 我得到以下信息 我知道这些是十六进制值 尽管我不是该主题的专家 我需要在 python 上执行这个精确的查询 以
  • 在python中逐层打印二叉树

    我想按以下方式打印二叉树 10 6 12 5 7 11 13 我已经编写了用于插入节点的代码 但无法编写用于打印树的代码 所以请帮忙解决这个问题 我的代码是 class Node def init self data self data d
  • 让 Graphstream 只渲染发生变化的部分

    我使用以下方法创建了一个表示特定区域路线图的图表Graphstream 现在我想让蓝色节点看起来像在图表上移动 为此我在另一个线程上显示图表 并且每秒将不同的节点着色为蓝色 如下所示 public void drawGraph List
  • Git lfs(大文件存储)表示 lfs 管理的文件在 git lfs pull 后被修改

    我有一个存储库的工作副本 它使用 git lfs 来存储一些大文件 我安装了 git lfs 二进制文件 但可能没有在工作副本中运行 git lfs install 当我想在添加 lfs 文件后更新本地工作副本时 我执行以下命令 git p
  • C:scanf循环

    char buf 1024 0 send a message if status 0 while 1 printf Enter message scanf 1023 n buf fflush stdin if strcmp buf quit
  • SQL Server 图形数据库 - 使用多种边类型的最短路径

    我已经对 SQL Server GraphDB 进行了研究 但到目前为止我发现的所有人为示例仅使用单个边缘表 总是如此Person friend of gt Person 例如 就我而言 我创建了数据中心中已部署软件组件的图表 并且存在不同
  • Android - 如何在启动后启动 /sdcard 上的应用程序

    有没有一种方法可以在启动后自动启动Android应用程序 如果它位于Android应用程序上 sdcard 好吧 大概是通过BroadcastReceiver 但哪种行动是正确的呢 ACTION BOOT COMPLETED does no
  • Html.ActionLink 无法动态调度

    我的 MVC3 有问题 我正在尝试使用 Html ActionLink 为我的博客项目中的标题生成链接 在中使用常量字符串ActionLink效果很好 但如果我使用Posts Title 当前帖子模型的标题被循环 我得到这个异常 CS197
  • 如何减少flutter web应用程序的加载时间

    截至目前 我们可以将 flutter web 应用程序作为单个文件启动 该文件将立即加载 因此需要花费大量时间和带宽来加载 这并不理想 有没有办法一次只加载一个页面 而不是整个网络应用程序 我的意思是 一次加载一个小部件 任何建议将不胜感激
  • 卡夫卡高级消费者 error_code=15

    当尝试使用高级消费者 使用全新的消费者组 从 Kafka 进行消费时 消费者永远不会开始运行 当我将日志记录级别切换为调试时 我可以看到以下两行一遍又一遍地重复 DEBUG AbstractCoordinator 09 43 51 192
  • 了解跟踪*

    再会 当试图理解数学使用标准的评估顺序Trace and TraceScan最近开发的命令及其漂亮的视觉表示thread https stackoverflow com questions 5459735 the clearest way
  • foreach(... in ...) 或 .ForEach();这就是问题[重复]

    这个问题在这里已经有答案了 可能的重复 C foreach 与函数式each https stackoverflow com questions 2024305 c sharp foreach vs functional each 这是一个
  • C# 中是否有一个好的浮点数基数排序实现

    我有一个带有浮点类型字段的数据结构 这些结构的集合需要按浮点值排序 是否有一个基数排序实现 如果没有 是否有一种快速的方法来访问指数 符号和尾数 因为如果你首先对尾数 指数和最后一次的指数对浮点数进行排序 您对浮点数进行排序的时间复杂度为