大数据量排序算法

无心人 · 发表于 2008-9-19 10:42:41

这么做行不行？

使用方法三
假设数字a
高位掩码是H，低位掩码是L
预先初始化一个数组A
将A[a & L]加一
如何？

liangbch · 发表于 2008-9-19 14:40:32

等有空的时间，把这3篇论文描述的算法重新实现一下，看看速度如何（预计应该不会超过我的程序）。另外，我又想到一个高cache命中率的分段排序算法，该算法的特点是，内存写采用顺序方式进行，因此L2 cache命中率较高，速度应该可以超过我现有的程序，不过内存占用率也是最高的，如对32bit 整数排序，辅助空间需要原始数据占用空间的1.5倍多。

无心人 · 发表于 2008-9-19 17:07:43

我也能写个辅助空间是(n + k)的算法
我想k最大是最大整数的1/16
k越大，速度越快

liangbch · 发表于 2008-9-28 10:00:38

1. 这几天仍然在继续研究大数据量快速排序算法。
2. 昨天重新实现了论文《无符号整数按位快速排序算法》，发现这个算法有局限性，只适用于最大关键字比较小的序列的排序。另外，文章对其复杂度的叙述也不太清楚，更精确的说法是，该算法的复杂度是O(ceil(log2(max+1))*n), max是最大关键字，ceil为向上取整函数，并不是作者宣称的O(n). 而快速排序的复杂度是O(log2(n)*n),显然，当max大于数组长度时，该算法慢于快速排序。实验表明，max 等于数组长度时，该算法略快与快速排序，原因是该算法对内存读取时，内存地址的连续性好于快速排序，故L2 cache的命中率比快速排序更高，所以速度比快速排序快些。

无心人 · 发表于 2008-9-28 10:28:58

如果不考虑辅助内存的问题
只要一次就能排好序

但目前关键是如何分组即保证排序速度又保证内存使用

hellomfk · 发表于 2009-5-18 07:37:28

great code
appreicate.

djj99888 · 发表于 2010-11-3 12:26:31

下载下来学习学习！

djj99888 · 发表于 2010-11-3 12:34:46

为什么下载不下来？

djj99888 · 发表于 2010-11-3 12:35:39

不知道为什么下载不下来！

KeyTo9_Fans · 发表于 2010-11-3 12:49:05

欢迎你来到数学研发论坛。

下载$1$个附件至少需要消耗$1$枚金币。

你的金币数为$0$，所以不能下载。

金币可以通过发贴获取。

每发$1$张贴子就可以获得$1$枚金币。

如果发够了$5$张贴子，还有机会赢得优秀新人奖。

希望这里可以给予你知识和乐趣。

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 大数据量排序算法

greate code