大数据量排序算法

无心人

记得曾用内存映射文件达到过500 MB / s的读写速度的

liangbch

可能是内存映射文件相对于物理内存比较小的缘故吧，如果内存映射文件等于或者大于物理内存，500M每秒的速度是不可想象的。

无心人

600多M的 内存256M

liangbch

无心人能给出测试代码吗？我对你给出的 内存映射文件 读写速度还是不太相信。如果确实如此，那么对于 大量数据的 快速排序 就可能会有实质性的突破。

gxqcn

读写速度 估计与数据读写点的连续性非常相关， 对于 排序 等操作，该指标将会大打折扣。

liangbch

10# 的第二个附件已更新，对大数据量的快速排序的探索暂时到此为止，暂时难以取得突破，欢迎大家提出新算法或者代码。 程序功能：测试3个排序函数的性能， 函数1，调用c++库函数qsort 函数2，使用快速排序算法 myQSort 函数3，有三个版本， 如果调用test2(1), 将调用sort1, 如果调用test2(2), 将调用sort2, 如果调用test2(3), 将调用sort3, 测试结果， 环境：WINDOWS XP, PIV2.6 ,RAM:768M, 测试数据30M(DATA_LEN=30*1048576) test2参数 qsort myQsor sortx 调用test2(1): 17829 6597 8016 调用test2(2): 17797 6563 6640 调用test2(2): 17796 6563 5453 其中第三个函数，在3个阶段所用的时间 调用test2(1): 297 4406 3313 调用test2(2): 594 2718 3313 调用test2(3): 281 1875 3297

无心人

非常遗憾 俺白天在从事很低等的劳动 腾不出写代码的时间的 唉 很想做这个题目的

liangbch

从万方上下了几篇关于整数排序的论文。这里贴出来。注意：这些文章可能有版权，不要大范围内传播。

无心人

THX 有时间一定读下 另外，欢迎liangbch回归论坛

liangbch

论文1： 分段快速排序的改进 论文2：无符号整数按位快速排序算法 论文3：一种非比较分段排序算法的研究 3篇文章都看了一遍。结果令人失望。 第1篇实际上和我实现的几个程序原理是一样的。从表面上看，当分的段数足够多，后期的快速排序就越接近O(n),而前期的分段过程用的时间也是O(n),因此总的复杂度也是O(n),似乎速度快了好多。对于一个长度为n的整数数组，作者并没有给出分多少段最合适，从算法描述上看，似乎段数越多越好。但是遗憾的是，作者并没有对cache这个因素加以考虑。虽然说不管分多少段，都需要将n个数据分派到合适的片段，复杂度和段的多少没有关系，但测试表明，分的段数越多，对内存的写就越缺乏连续性，cache的命中率就越低。我的测试表明，当分的段数等于$sqrt{n)$时，总的时间最少。 对于第2篇文章，仅当数据范围相对于数据个数 很小时有效。它从数据的最高bit(实际上是最高非0bit比特，如已经知道做高8bit是0，则从24bit开始检查) 开始，对每一个bit,都需要对每个元素检查一遍。 如数据的的范围是$2^32$, 数据个数是$2^16$, 则使用该法，所用时间为 32*65536, 而使用快速排序所用的时间是16*65536,这时，该方法慢于快速排序。 如数据的的范围是$2^16$, 数据个数是$2^24$, 则使用该法，时间复杂度度为 16*16M, 而使用快速排序的时间复杂度是24*16M，这时，该方法快于快速排序。 表面上是O(n)的算法，如16n 或者 32n。 实际上，如果数据范围大于数据个数时，该方法慢于快速排序。这种情况不少见。我发这个帖子的初衷是要解决64bit 整数的排序问题，这些数据具有数据值得范围大的特点，因此这个方法根本不适用我的问题。 对于第3篇文章，本质上和第一篇文章算法上没有多大区别。在分段的时候，根据关键字高位bit将数据分发到不同的片段，和第一篇文章一样，首先有确定每一段的元素的个数，这样，在将源数据分发到不同的片段时，才能放到适当的位置。和第一篇不同，这个算法采用递归的办法，如第一趟考察关键字的最高8bits（25-32bit）,则最高8bits不同的数被分派的不同的区域。则第二趟对每一个片段，则考察其17-24bit. 将次8bit不同的数放到不同的更小的片段。每一趟都需要统计片段的大小和分发数据2个步骤。表明上看来，每一趟(第一趟考察25-32bit,第2趟考察17-24bi,第3趟考察9-16bit，,第3趟考察1-8bit )的复杂度都是O(n),但由于数据写的非连续性，cache的命中率很低，每一趟数据分发 都接近使用快速排序所用时间的1半左右，因此并不能减少总的排序时间。