性能-我们何时应该使用Radix排序?

似乎Radix sort具有非常好的平均用例性能,即O(kN):[http://en.wikipedia.org/wiki/Radix_sort]

但是似乎大多数人仍在使用快速排序,不是吗?

11个解决方案
27 votes

与大多数其他排序算法相比,基数排序更难归纳。 它需要固定大小的键,以及一些将键分解成几块的标准方法。 因此,它永远不会进入图书馆。

Mark Ransom answered 2020-08-11T19:09:15Z
18 votes

根据您的评论进行编辑:

  • 基数排序仅适用于整数,固定大小的字符串,浮点以及“小于”,“大于”或“词典顺序”比较谓词,而比较排序可以适应不同的顺序。
  • k可以大于logN。
  • 快速排序可以在适当的位置进行,基数排序效率较低。
Alexandre C. answered 2020-08-11T19:09:48Z
17 votes

这里的其他答案太可怕了,它们没有给出实际使用基数排序的示例。

一个示例是使用偏斜DC3算法(Kärkkäinen-Sanders-Burkhardt)创建“后缀数组”时。 如果排序算法是线性时间,则该算法仅是线性时间,并且基数排序在这里是必要且有用的,因为键在构造上很短(整数的三元组)。

Mehrdad answered 2020-08-11T19:10:13Z
9 votes

除非您有一个庞大的列表或非常小的键,否则log(N)通常小于k,因此很少更高。 因此,选择具有O(N log N)个平均案例性能的通用排序算法并不一定比使用基数排序要差。

更正:正如@Mehrdad在评论中指出的那样,上面的论点并不合理:要么密钥大小是常数,然后基数排序是O(N),要么密钥大小是k,然后quicksort是O(k N log N)。 因此,从理论上讲,基数排序确实具有更好的渐近运行时间。

实际上,运行时将由以下术语主导:

  • 基数排序:c1 k N

  • 快速排序:c2 k N log(N)

其中c1 >> c2,因为从较长的密钥中“提取”位通常是一项昂贵的操作,涉及移位和逻辑操作(或至少是未对齐的内存访问),而现代CPU可以将密钥与64位,128位甚至256位进行比较 一次操作。 因此,在许多常见情况下,除非N巨大,否则c1将大于c2 log(N)

Niki answered 2020-08-11T19:10:56Z
8 votes

基数排序需要O(k * n)时间。 但是您必须问什么是K。K是“数字位数”(有点简单,但基本上是这样的)。

那么,您有几位数? 相当好的答案,超过了log(n)(以“数字大小”为底的对数),这使Radix算法成为O(nlogn)。

这是为什么? 如果您的位数少于log(n),则可能的位数少于n。 因此,您可以简单地使用耗时O(n)的“计数排序”(只计算每个数字中有多少个)。 所以我假设您有超过k> log(n)个数字...

这就是为什么人们不那么使用Radix排序的原因。 尽管在某些情况下值得使用它,但在大多数情况下,快速排序要好得多。

Guy answered 2020-08-11T19:11:30Z
8 votes

当n> 128时,我们应该使用RadixSort

当对int32排序时,我选择基数256,因此k = log(256,2 ^ 32)= 4,这比log(2,n)小得多

在我的测试中,在最佳情况下,基数排序比快速排序快7倍。

public class RadixSort {
    private static final int radix=256, shifts[]={8,16,24}, mask=radix-1;
    private final int bar[]=new int[radix];
    private int s[] = new int[65536];//不使用额外的数组t,提高cpu的cache命中率

    public void ensureSort(int len){
        if(s.length < len)
            s = new int[len];
    }   

    public void sort(int[] a){
        int n=a.length;
        ensureSort(n);
        for(int i=0;i<radix;i++)bar[i]=0;
        for(int i=0;i<n;i++)bar[a[i]&mask]++;//bar存放了桶内元素数量
        for(int i=1;i<radix;i++)bar[i]+=bar[i-1];//bar存放了桶内的各个元素在排序结果中的最大下标+1
        for(int i=0;i<n;i++)s[--bar[a[i]&mask]]=a[i];//对桶内元素,在bar中找到下标x=bar[slot]-1, 另s[x]=a[i](同时--bar[slot]将下标前移,供桶内其它元素使用)

        for(int i=0;i<radix;i++)bar[i]=0;
        for(int i=0;i<n;i++)bar[(s[i]>>8)&mask]++;
        for(int i=1;i<radix;i++)bar[i]+=bar[i-1];
        for(int i=n-1;i>=0;i--)a[--bar[(s[i]>>8)&mask]]=s[i];//同一个桶内的元素,低位已排序,而放入t中时是从t的大下标向小下标放入的,所以应该逆序遍历s[i]来保证原有的顺序不变

        for(int i=0;i<radix;i++)bar[i]=0;
        for(int i=0;i<n;i++)bar[(a[i]>>16)&mask]++;
        for(int i=1;i<radix;i++)bar[i]+=bar[i-1];
        for(int i=n-1;i>=0;i--)s[--bar[(a[i]>>16)&mask]]=a[i];//同一个桶内的元素,低位已排序,而放入t中时是从t的大下标向小下标放入的,所以应该逆序遍历s[i]来保证原有的顺序不变

        for(int i=0;i<radix;i++)bar[i]=0;
        for(int i=0;i<n;i++)bar[(s[i]>>24)&mask]++;
        for(int i=129;i<radix;i++)bar[i]+=bar[i-1];//bar[128~255]是负数,比正数小
        bar[0] += bar[255];
        for(int i=1;i<128;i++)bar[i]+=bar[i-1];     
        for(int i=n-1;i>=0;i--)a[--bar[(s[i]>>24)&mask]]=s[i];//同一个桶内的元素,低位已排序,而放入t中时是从t的大下标向小下标放入的,所以应该逆序遍历s[i]来保证原有的顺序不变      
    }
}
zhuwenbin answered 2020-08-11T19:11:59Z
3 votes

k =“要排序的数组中最长值的长度”

n =“数组的长度”

O(k * n)=“最坏的情况”

k * n = n ^ 2(如果k = n)

因此,在使用Radix排序时,请确保“最长整数比数组大小短”,反之亦然。 然后,您将击败Quicksort!

缺点是:在大多数情况下,您无法确定整数的大小,但是如果您有固定范围的数字,则应该采用基数排序。

kiltek answered 2020-08-11T19:12:41Z
2 votes

这是比较quicksort和radixsort的链接:

对于整数数组,基数排序是否比快速排序更快? (是的,是2-3倍)

这是分析几种算法的运行时间的另一个链接:

排序问题:

在相同数据上哪个更快? O(n)排序还是O(nLog(n))排序?

答:这取决于。 这取决于要排序的数据量。 它取决于要运行的硬件,并且取决于算法的实现。

johndoevodka answered 2020-08-11T19:13:23Z
2 votes

Radix排序不是基于比较的排序,只能对整数(包括指针地址)和浮点数之类的数字类型进行排序,而可移植地支持浮点数有点困难。

可能是因为它的适用范围很窄,因此许多标准库都选择忽略它。 它甚至不能让您提供自己的比较器,因为有些人甚至不希望直接对整数进行排序,就像将整数用作其他要用作排序键的索引一样。 基于比较的排序提供了所有的灵活性,因此可能是只希望选择一种能满足人们99%的日常需求的通用解决方案,而不是一味地满足这一1%的需求。

就是说,尽管适用范围很窄,但在我的领域中,我发现基数排序比内省排序或快速排序更有用。 我处于1%的水平,几乎没有使用过字符串键,但是经常会发现数字排序的用例。 这是因为我的代码库围绕实体和组件(实体组件系统)的索引以及诸如索引网格之类的东西,并且存在大量数字数据。

结果,就我而言,基数排序对于所有事物都变得有用。 在我的情况下,一个常见的例子是消除重复索引。 在那种情况下,我实际上不需要对结果进行排序,但是基数排序通常可以比其他方法更快地消除重复项。

另一个发现是,例如,沿着给定维度的kd树的中位数拆分。 将基数对给定维度的浮点值进行基数排序后,可以在线性时间内快速找到中间位置以拆分树节点。

另一个方法是,如果我们不打算在片段着色器中进行处理,则按std::sort对高级基元进行深度排序,以获得半适当的alpha透明度。 这也适用于GUI和矢量图形软件的z顺序元素。

另一个是使用索引列表的缓存友好型顺序访问。 如果索引被遍历了很多次,那么如果我对索引进行预先基数排序,那么遍历通常会提高性能,以便遍历顺序而不是随机顺序进行。 后者可以在内存中来回曲折,从高速缓存行中清除数据,只是在同一循环内重复重新加载相同的内存区域。 当我先对索引进行基数排序再重复访问它们时,这种情况就不再发生了,并且可以大大减少缓存丢失。 实际上,这是我最常用的基数排序,这是当系统要访问具有两个或多个组件的实体时ECS缓存友好的关键。

就我而言,我经常使用多线程基数排序。 一些基准:

--------------------------------------------
- test_mt_sort
--------------------------------------------
Sorting 1,000,000 elements 32 times...

mt_radix_sort: {0.234000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]

std::sort: {1.778000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]

qsort: {2.730000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]

我可以平均用6-7毫秒的时间在dinky硬件上一次对一百万个数字进行排序,这不如我想要的那样快,因为用户有时仍可以在交互上下文中注意到6-7毫秒,但仍然可以 与C ++的std::sort或C的qsort相比,它比55-85 ms好得多,这肯定会导致帧速率出现明显的打h。 我什至听说有人使用SIMD实现基数排序,尽管我不知道他们是如何管理的。 我还不够聪明,无法提出这样的解决方案,尽管与标准库相比,即使是我幼稚的小数基也能很好地解决问题。

Dragon Energy answered 2020-08-11T19:14:23Z
0 votes

一个示例是当您对非常大的整数集或数组进行排序时。基数排序和任何其他类型的分布排序都非常快,因为数据元素主要排入队列数组(对于LSD基数排序,最多10个队列),然后重新映射到要排序的同一输入数据的不同索引位置。由于没有嵌套循环,因此随着要排序的数据输入整数的数量显着变大,该算法的行为会趋于线性化。与其他排序方法(例如效率极低的bubbleSort方法)不同,基数排序不执行比较操作进行排序。这只是将整数重新映射到不同索引位置的简单过程,直到最终对输入进行排序。如果您想自己测试一个LSD基数排序,我已经写出了一个LSD基数,并存储在github上,可以轻松地在在线js ide(例如雄辩的javascript的编码沙箱)上对其进行测试。随意使用它,并观察不同n值下它的行为。我已经使用运行时间<300ms的多达900,000个未排序的整数进行了测试。如果您想使用它,这里是链接。

[HTTPS://gist.GitHub.com/St bean/4阿凡58的09021899发14打发585地方6从86地方6]

Anthony Poblacion answered 2020-08-11T19:14:50Z
-9 votes

快速排序的平均值为O(N logN),但最坏的情况为O(N ^ 2),因此即使在大多数实际情况下也不会达到N ^ 2,始终存在输入风险 对您而言将处于“不良状态”。 以基数排序不存在这种风险。 我认为这为基数排序提供了很大的优势。

Guy Nir answered 2020-08-11T19:08:55Z
translate from https://stackoverflow.com:/questions/4146843/when-should-we-use-radix-sort