这是一篇很长的文字.请多多包涵.简而言之,问题是:是否有可行的就地基数排序算法？
我有很多小的固定长度字符串,只使用字母"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字符串？