标签: radix-sort

这是一篇很长的文字.请多多包涵.简而言之,问题是:是否有可行的就地基数排序算法？

初步

我有很多小的固定长度字符串,只使用字母"A","C","G"和"T"(是的,你猜对了:DNA)我想要排序.

目前,我使用的是在STL的所有常见实现中std::sort使用introsort.这非常有效.但是,我相信,基数排序适合我的问题完全设置,并应工作多在实践中更好.

细节

我已经用非常天真的实现来测试这个假设,并且对于相对较小的输入(大约10,000),这是真的(好吧,至少快两倍以上).但是,当问题规模变大(N > 5,000,000)时,运行时会出现严重下降.

原因很明显:基数排序需要复制整个数据(实际上我的天真实现不止一次).这意味着我已经将~4 GiB放入我的主内存中,这显然会影响性能.即使它没有,我也承担不起使用这么多内存,因为问题规模实际上变得更大.

用例

理想情况下,对于DNA和DNA5(允许额外的通配符"N"),甚至DNA与IUPAC 模糊代码(导致16个不同的值),此算法应该适用于2到100之间的任何字符串长度.但是,我意识到所有这些情况都无法涵盖,所以我对任何提速都感到满意.代码可以动态决定要分派的算法.

研究

不幸的是,关于基数排序的维基百科文章是没用的.关于就地变体的部分是完全垃圾.关于基数排序的NIST-DADS部分几乎不存在.有一篇名为Efficient Adaptive In-Place Radix Sorting的有前途的论文描述了算法"MSL".不幸的是,这篇论文也令人失望.

特别是,有以下几点.

首先,该算法包含几个错误,并留下了许多无法解释的问题.特别是,它没有详细说明递归调用(我只是假设它递增或减少一些指针来计算当前的移位和掩码值).同时,它采用了功能dest_group并dest_address没有给出定义.我没有看到如何有效地实现这些(即在O(1)中;至少dest_address不是微不足道的).

最后但并非最不重要的是,该算法通过使用输入数组内的元素交换数组索引来实现就地.这显然只适用于数值数组.我需要在字符串上使用它.当然,我可以只是强调打字并继续进行,假设内存可以容忍我存储一个不属于它的索引.但这只有在我将字符串压缩到32位存储器(假设32位整数)时才有效.这只有16个字符(暂时忽略16> log(5,000,000)).

其中一位作者的另一篇论文根本没有给出准确的描述,但它给出了MSL的运行时为次线性,这是错误的.

回顾一下:是否有希望找到一个工作的参考实现或至少一个良好的伪代码/描述工作就地基数排序,适用于DNA字符串？

我正在阅读基数,计数和桶排序的定义,似乎所有这些都只是下面的代码:

public static void sort(int[] a, int maxVal){
    int [] bucket=new int[maxVal+1];

    for (int i=0; i<bucket.length; i++){
        bucket[i]=0;
    }

    for (int i=0; i<a.length; i++){
        bucket[a[i]]++;
    }

    int outPos=0;
    for (int i=0; i<bucket.length; i++){
        for (int j=0; j<bucket[i]; j++){
            a[outPos++]=i;
        }
    }
}

我知道我不对,所以我错过了什么？如果您认为可以帮助解释Java或C,请显示代码

铲斗分类和基数排序是近亲; bucket sort从MSD到LSD,而radix sort可以同时进入"方向"(LSD或MSD).两种算法如何工作,特别是它们有何不同？

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

但似乎大多数人仍在使用Quick Sort,不是吗？

为什么quicksort(或introsort)或任何基于比较的排序算法比radix-sort更常见？特别是对于数字排序.

基数排序不是基于比较的,因此可能比O(n logn)更快.实际上,它是O(k n),其中k是用于表示每个项目的位数.并且内存开销并不重要,因为您可以选择要使用的桶数,并且所需的内存可能小于mergesort的要求.

它与缓存有关吗？或者可能访问数组中的随机字节整数？

我不知道为什么这对我来说是如此困难.我查看了wiki页面和伪代码(以及实际代码),试图了解基数排序算法的工作原理(关于存储桶).

我在这里看错了吗？我应该考虑一下桶排序吗？有人能给我一个愚蠢的版本吗？作为参考,这里是一个可能执行基数排序的代码块:

// Sort 'size' number of integers starting at 'input' according to the 'digit'th digit
// For the parameter 'digit', 0 denotes the least significant digit and increases as significance does
void radixSort(int* input, int size, int digit)
{
    if (size == 0)
        return;

    int[10] buckets;    // assuming decimal numbers

    // Sort the array in place while keeping track of bucket starting indices.
    // If bucket[i] is meant to be empty (no numbers with i at the …

"算法简介"一书提到了基数排序的LSD(最低有效数字)版本.但是,正如其他人在stackoverflow中指出的那样,MSD(最高有效数字)版本也存在.所以我想知道每一个的利弊.我的猜测是LSD版本比MSD版本有一些好处,但我不确定.因此问题.

我试图为整数实现基数排序,包括负整数.对于非负的int,我计划为数字0-9创建一个10个队列的队列,并实现LSD算法.但我对负整数感到困惑.我现在想的是,继续为他们创建10个队列的另一个队列并分别对它们进行排序,然后在最后,我将给出2个列表,一个包含负的整数排序,另一个包含非负的整数.最后我会合并它们.

你怎么看待这件事？是否有更有效的方法来处理负整数？

谢谢!

基数排序是否能够对浮动数据进行排序,例如0.5,0.9,1.02等？

考虑一个n数字具有最大k数字的数组(请参阅编辑).从这里考虑基数排序程序:

def radixsort( aList ):
  RADIX = 10
  maxLength = False
  tmp, placement = -1, 1

  while not maxLength:
    maxLength = True
    # declare and initialize buckets
    buckets = [list() for _ in range( RADIX )]

    # split aList between lists
    for  i in aList:
      tmp = i / placement
      buckets[tmp % RADIX].append( i )
      if maxLength and tmp > 0:
        maxLength = False

    # empty lists into aList array
    a = 0
    for …