找回密码
 欢迎注册
楼主: liangbch

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

[复制链接]
发表于 2008-9-12 18:09:28 | 显示全部楼层
记得曾用内存映射文件达到过500 MB / s的读写速度的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-9-13 07:32:31 | 显示全部楼层

回复 11# 无心人 的帖子

可能是内存映射文件相对于物理内存比较小的缘故吧,如果内存映射文件等于或者大于物理内存,500M每秒的速度是不可想象的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-13 18:33:29 | 显示全部楼层
600多M的
内存256M
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-9-16 22:57:59 | 显示全部楼层

回复 13# 无心人 的帖子

无心人能给出测试代码吗?我对你给出的 内存映射文件 读写速度还是不太相信。如果确实如此,那么对于 大量数据的 快速排序 就可能会有实质性的突破。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-17 07:37:49 | 显示全部楼层
读写速度 估计与数据读写点的连续性非常相关,
对于 排序 等操作,该指标将会大打折扣。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-9-17 18:13:10 | 显示全部楼层
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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-17 21:48:59 | 显示全部楼层


非常遗憾
俺白天在从事很低等的劳动
腾不出写代码的时间的


很想做这个题目的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-9-18 13:30:11 | 显示全部楼层
从万方上下了几篇关于整数排序的论文。这里贴出来。注意:这些文章可能有版权,不要大范围内传播。

分段快速排序的改进.pdf

255.75 KB, 阅读权限: 20, 下载次数: 1, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

售价: 1 枚金币  [记录]

无符号整数按位快速排序算法.pdf

128.79 KB, 阅读权限: 20, 下载次数: 3, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

售价: 1 枚金币  [记录]

一种非比较分段排序算法的研究.pdf

204.93 KB, 阅读权限: 20, 下载次数: 1, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

售价: 1 枚金币  [记录]

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-18 17:39:02 | 显示全部楼层
THX

有时间一定读下

另外,欢迎liangbch回归论坛
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-9-18 21:52:04 | 显示全部楼层

回复 19# 无心人 的帖子

论文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半左右,因此并不能减少总的排序时间。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 22:27 , Processed in 0.048118 second(s), 18 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表