大数据量排序算法

liangbch

排序算法是一个永恒的话题，不同的排序算法则适用于不同特点的数据。我们这里讨论的待排序的数据具有这样的特点。
1.数据量很大，几乎充满整个内存，比如有一亿个整数（需占用400M内存空间）。
2.数据为整数。
3.数据的分布大致均衡，如果将数据分成几个区间，每个区间的数的个数差别不是太大。

需求：
1.需要完成这个大数组的排序，要求速度比直接使用编译器内置的快速排序更快。
2.可以使用辅助存储空间，但辅助存储空间相对于待排序的数据所占的空间要小得多，比如是原始数据的1/16或者更小。

无心人

这显然可以用基数排序的
首先分若干段
每段都进行基数排序
然后两两合并
直到整个序列合并

liangbch

我现在的想法也是分段，但是最后阶段不需要归并排序。

无心人

关键是如何界定分界点？
数据均匀分布么？

liangbch

回楼上，题目中已提到

据的分布大致均衡，如果将数据分成几个区间，每个区间的数的个数差别不是太大。

无心人

假设要分N段，总共S个
则需要工作量
S * N次比较并分组，S次排序操作
显然总工作量是(N + 1) S
空间是S /  N

关键是如何最少运算得到分组
如果允许文件存储中间结果
则分组操作只需要S次

注意到使用高位掩码与就能得到分组的信息

liangbch

汇报一下我的测试结果。

1.测试数据用rand()函数生成，所有的数据都大于0（），下面是生成测试数据的代码

1. void buildData(DWORD *pData,int len,DWORD *min,DWORD *max)
   
2. {
   
3. *min=~0;
   
4. *max=0;
   
5. 
   
6. int i;
   
7. for (i=0;i<len;i++)
   
8. {
   
9. pData[i]=(rand()<<16)+rand()+1; //the all of data not equal 0
   
10. if ( pData[i] > *max)
    
11. *max=pData[i];
    
12. if (pData[i]< *min)
    
13. *min=pData[i];
    
14. 
    
15. }
    
16. }

复制代码

2. 测试程序对2组数据分别排序，2组数据完全相同，每组数据 30M 个整数，分别占用空间 30M * 4=120M。
3. 第一组数据用qsort排序，用时17141 ms. 第二组数据用我的程序排序，用时13172 ms

程序算法。
1.将数据分为n组，第一组数据记为s[1], 第二组数据记为s[2],  第n组数据记为s[n],每组数据的范围(起始值和终值)事先确定，max-min 相同，每组数据的个数一般不相同，各组数据相邻，即第一组数据的最后一个数据与第二组数据的第一个数地址的相邻的。

2.将数据初步排序，使得s[i+1]中的任意一个数据均大于s[ i ]中的数据。

3.将每组数据用qsort进行排序，在排序前，由于满足上面的条件，故所有的数据是有序的。

各位可编制程序，看看能否有更快的算法。

无心人

请看6#
首先，你的分组的比较操作要重复N次，N是分组数
所以是否用文件保存？
如果用文件，则只需要一次就能达到分组效果

其次，对整数这种特殊数据的排序，快速排序并不是最快的

liangbch

原帖由 无心人 于 2008-9-12 07:16 发表
所以是否用文件保存？
其次，对整数这种特殊数据的排序，快速排序并不是最快的

不用文件保存，文件I/O很慢，甚至慢于快速排序本省，故这里不考虑使用文件。
上次给出的程序有bug,故关于性能测试的数据是错的，下面是修改后的结构

下面汇报一下最新的测试结果。
1.使用自编的快速排序函数比系统库函数qsort要快，速度大约是qsort的3倍。
2.我自己编了3个排序的函数，其算法描述如下

  2.1 相同点，使用类似桶排序算法，先统计各个桶，算出每个桶需要存放的数据的个数，以及每个桶的地址(各个桶的地址相邻),然后检查每个数据，如果它的位置不在它应该所在的桶，则放入相应的桶。最后对每个桶中的数据进行快速排序。

2.2  不同点：
    第1个函数使用很少的辅助空间，在将某个数据放到适当的桶内的时候，对内存的访问方式是随机访问。

    第2个函数使用和待排序数据相同大小的辅助空间，在将某个数据放到适当的桶内的时候，对内存的访问方式是顺序访问，由于有多个内存块需要写操作，cache命中率仍然较低，这个函数的缺点是使用的辅助空间较大，内存的I/O也比第一个函数多，速度也慢于第1个函数快。
   
    第3个函数使用和待排序数据相同大小的辅助空间，在第二个函数的基础上，减小了内存读写操作，速度比第1个函数和第2个函数快了不少，但相对于自己写的直接使用快速排序的函数，速度仍没有本质的提高。

[ 本帖最后由 liangbch 于 2008-9-16 22:46 编辑 ]

liangbch

附上源代码，好的东西要共享！！！

[ 本帖最后由 liangbch 于 2008-9-17 18:14 编辑 ]