桶排序的并行优化算法
摘要:本文从桶排序出发,提出了新的并行的桶排序的程序实现方案,并把用于并行的额
外开销减少到了一个比较理想的范围内。它的效率比原实现方式提高了 41%,而且突破了
原始桶排序内存的限制,使能桶排可以真正的处理大量数据。
关键词:优化 桶排序 并行 空间
一、 引言:
排序可以说是在计算机中最常见的问题之一了,而且不论是在操作系统,人工智
能,计算机网络还是各种应用,都对于排序有大量的需求,因此设计出来一种效率高,
开销少的排序算法就显得格外重要。于此同时,随着计算机的高速发展,传统的单线
程排序已经不能为人所接受,本文基于桶排序,提出了一种并行化的优化桶排算法,
不同于原始桶排,该算法在时间复杂度上都有了 35%的提高。同时这种桶排序,对于
内存有很大开销,不利于处理大量数据,于是我们提出了基于链表的新的桶排序算法,
在各个数据进桶时采用指针将各个数据练成一个表,而不是原始的拷贝方法,这种方
法极大地减少了内存的使用,而且,研究又将链表方式的桶排序并行化,效率提高了。
二、 原始桶排序:
桶排序的典型实现方式是基于数组的( Array-Based Bucket Sorng ), 以下简称
ABS。其物理结构如图所示。
数据规模为 N 时,图中的大小为 N 的一维数组用于存放数据,叫做 Buckets 的 Buer 是
一个 10*N 的二位数组,其中,第 1 行代表 0 号桶,第 2 行代表 1 号桶……. 以此类推。
桶号对应了一个数字特定位的值。
其排序过程用一个例子说明:有 2,10,22 三个数依次排在一维数组中。首先,比较个位:
从左到右依次取数,2 的个位是 2,放入 2 号桶(桶中也是从左到右依次排放)。取
10,放入 00 号桶;取 22,放入 2 号桶;然后对桶从上到下,从左到右依次遍历,取出
数据,回填到一维数值中。此时一维数组中存放顺序是 10,2,22;再比较十位,投入
桶中并填回,此时一维数值中存放顺序是 2,10,22。由于最大的位数是十位,故做两次
即停止,排序完成。
从上例中可以看出,桶排序中有两个主要部分——“投桶”和“回填”;对于规模为 N 的排