标签: sorting

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

初步

我有很多小的固定长度字符串,只使用字母"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字符串？

我有一个像这样的.csv文件:

stack2@example.com,2009-11-27 01:05:47.893000000,example.net,127.0.0.1
overflow@example.com,2009-11-27 00:58:29.793000000,example.net,255.255.255.0
overflow@example.com,2009-11-27 00:58:29.646465785,example.net,256.255.255.0
...

我必须从文件中删除重复的电子邮件(整行)(即overflow@example.com上面示例中包含的一行).如何uniq仅在字段1上使用(以逗号分隔)？根据man,uniq没有列的选项.

我尝试了一些东西,sort | uniq但它不起作用.

我有一个这样的数据框:

print(df)

        0          1     2
0   354.7      April   4.0
1    55.4     August   8.0
2   176.5   December  12.0
3    95.5   February   2.0
4    85.6    January   1.0
5     152       July   7.0
6   238.7       June   6.0
7   104.8      March   3.0
8   283.5        May   5.0
9   278.8   November  11.0
10  249.6    October  10.0
11  212.7  September   9.0

如您所见,月份不是日历顺序.所以我创建了第二列,以获得与每个月相对应的月份数(1-12).从那里,我如何根据日历月的顺序对此数据框进行排序？

简而言之:有没有办法对GROUP_CONCAT语句中的值进行排序？

查询:

GROUP_CONCAT((SELECT GROUP_CONCAT(parent.name SEPARATOR " » ") 
FROM test_competence AS node, test_competence AS parent 
WHERE node.lft BETWEEN parent.lft AND parent.rgt 
  AND node.id = l.competence 
  AND parent.id != 1 
ORDER BY parent.lft) SEPARATOR "<br />\n") AS competences

我得到这一行:

工艺品»细木工

管理»组织

我希望这样:

管理»组织

工艺品»细木工

我有一个非常简单的HTML表,有4列:

Facility Name, Phone #, City, Specialty

我希望用户能够按设施名称和仅城市进行排序.

我如何使用jQuery编写代码？

我有一个格式如下的数据:

foo<tab>1.00<space>1.33<space>2.00<tab>3

现在我尝试逐渐根据最后一个字段对文件进行排序.我尝试了以下命令,但它没有像我们预期的那样排序.

$ sort -k3nr file.txt  # apparently this sort by space as delimiter

$ sort -t"\t" -k3nr file.txt
  sort: multi-character tab `\\t'

$ sort -t "`/bin/echo '\t'`" -k3,3nr file.txt
  sort: multi-character tab `\\t'

什么是正确的方法呢？

这是样本数据.

哪种排序算法最适合大多数排序数据？

我的同事们带我回到了我的大学时代,今天早上讨论了排序算法.我们回忆起我们最喜欢的StupidSort,我们其中一个人确信我们已经看到了一种排序算法O(n!).这让我开始寻找可以找到的"最差"排序算法.

我们假设一个完全随机的排序会非常糟糕(即随机化元素 - 它是否按顺序排列？没有？再次随机化),我环顾四周,发现它显然叫做BogoSort,或者是Monkey Sort,或者有时只是随机排序.

Monkey Sort似乎具有最差的表现O(?),最好的表现O(n)和平均表现O(n·n!).

是否存在任何比平均性能更差的命名算法O(n·n!)？或者只是比一般的猴子排序更愚蠢？

我有一个List<String>包含国家/地区名称的对象.如何按字母顺序对此列表进行排序？

list.sort()对列表进行排序并保存已排序的列表,同时sorted(list)返回列表的已排序副本,而不更改原始列表.

• 但什么时候使用哪个？
• 哪个更快？又快多少？
• 可以在之后检索列表的原始位置list.sort()吗？