分布式实验一.doc

*大学本科实验报告专用纸(附页)*大学研究生实验报告专用纸课程名称 分布式系统 成绩评定 实验项目名称 二分法排序的多线程程序 实验项目编号 一 实验项目类型 设计 指导教师 周继鹏 学生姓名 学号 学院 信息科学技术 系 计算机科学 专业 计算机应用 实验时间 2009 年 10 月 17 日 实验地点 宿舍 【实验目的】1. 深刻理解并发计算的原理。2. 初步学习多线程编程技术。【实验内容】1. 给定2*n个数据,编写利用二分法排序的多线程程序。【实验环境】1. 操作系统：Windows XP2. 编程语言：Java3. 编程工具：Myeclipse 6.0，JDK1.6【实验步骤】一、 二分法排序算法描述二分排序又称为归并排序，该方法是把一个给定数组一分为二，递归地为每一半排序，之后合并排好序的两半。二、 二分法排序算法伪代码/* * 归并排序. * 下面的算法属于MergeSorter类，当MergeSorter给数组排序时， * 产生两个子数组，每个数组都是原大小的一半，然后递归地排序它们。 * 最后把排序好的两个数组合并到一起。 */public void sort () / 数组长度=1if (a.length = 1) return;/ 把数组一分为二int first = new inta.length / 2;int second = new inta.length - first.length;System.arraycopy( a, 0, first, 0, first.length );System.arraycopy( a, first.length, second, 0, second.length );/分别对每一半数组排序MergeSorter firstSorter = new MergeSorter ( first );firstSorter.sort();MergeSorter secondSorter = new MergeSorter ( second );secondSorter.sort();/ 合并两个排好序的数组merge( first, second );图表 1 传统二分法排序算法伪代码三、 加入多线程的二分法排序算法伪代码多线程机制的引入想要达到提高算法执行效率的目的，可惜最后结果并不像预期的那样。加入多线程的二分法排序算法的思想是：当一个数组被分成两个子数组后，分别启动两个线程对这两个子数组进行排序，最后当两个线程均进行完毕时，即线程终止时进行合并操作，这样貌似能达到对两个数组并发排序的目的，可以大大提高排序效率。/* * 归并排序. * 下面的算法属于MergeSorterRunnable类，当MergeSorterRunnable给数组排序 * 时，产生两个子数组，每个数组都是原大小的一半，然后用两个线程分别对两个数组进 * 行排序，然后递归地排序它们。最后当两线程均返回时，把排序好的两个数组合并到一* 起. */public void sort () / 数组长度=1if (a.length = 1) return;/ 把数组一分为二int first = new inta.length / 2;int second = new inta.length - first.length;System.arraycopy( a, 0, first, 0, first.length );System.arraycopy( a, first.length, second, 0, second.length );/ 启动两个线程，分别对每一半数组排序MergeSorterRunnable firstSorter = new MergeSorterRunnable( first );Thread firstThread = new Thread( firstSorter );firstThread.start();MergeSorterRunnable secondSorter = new MergeSorterRunnable( second );Thread secondThread = new Thread( secondSorter );secondThread.start();/ 等待两个线程全部终止try firstThread.join();secondThread.join(); catch (InterruptedException e) e.printStackTrace();/ 合并两个排好序的数组merge( first, second );图表 2加入多线程的二分法排序算法伪代码四、 算法实现算法用三个类实现：1. ArrayUtil类，负责生成由0-100的数字组成的随机数组，2. MergeSorterRunnable类，负责进行二分法排序，3. MergeSorterTest类，负责测试排序结果。thread工程的包结构图如下：五、 多线程二分排序实验1. 数组大小为100，排序结果如下：图表 3 多线程二分法排序的实验结果, 数组大小为1002. 数组大小为10000，排序结果如下：图表 4多线程二分法排序的实验结果, 数组大小为100003. 数组大小为10000，排序结果如下：图表 5 多线程二分法排序的实验结果, 数组大小为1000000这时算法的执行时间较图表3和图表4明显增长。为了更好地测试算法的执行时间，我们引入一个算法计时器类 StopWatch 类。/* * 秒表. * 可以重复启停秒表. * 可以使用秒表来测量程序的运行时间. */public class StopWatch /* * 构造一个处于停止状态并且没有累计时间的秒表. */public StopWatch () reset();/* * 启动秒表.现在开始累计时间. */public void start () if (isRunning) return;isRunning = true;startTime = System.currentTimeMillis();/* * 停止秒表.时间停止累计并被加到已流逝的时间中. */public void stop () if (!isRunning) return;isRunning = false;long endTime = System.currentTimeMillis();elapsedTime = elapsedTime + endTime - startTime;/* * 返回总的流逝时间. * return 总的流逝时间 */public long getElapsedTime () if (isRunning) long endTime = System.currentTimeMillis();return elapsedTime + endTime - startTime;elsereturn elapsedTime;/* * 让秒表停止并把流逝的时间重置为0. */public void reset () elapsedTime = 0;isRunning = false;private long elapsedTime;private long startTime;private boolean isRunning;图表 6 秒表 StopWatch 类源代码有了这个类的帮助以后，我们就可以轻松地计算出算法运行的毫秒级的时间。在下面的试验中我们将对比两种算法的执行效率，将用StopWatch 类计时。六、 对比实验在该实验中，将不引入多线程的二分排序算法和加入多线程的二分排序实验做对比，并对实验结果进行简单的分析。排序的数组大小设为1000000。1、不引入多线程的二分排序算法的算法用时取5次结果的平均值，最后得到：算法用时:531 ms2、引入多线程的二分排序算法的算法用时取5次结果的平均值，最后得到：算法用时:18218 ms由上可以看出，引入多线程的二分排序算法的用时反而多于没有引入多线程的传统二分排序算法。我们假设大量的线程的创建和释放消耗了大量的系统资源，致使算法运行效率降低。所以为了验证这一想法，提出了一种折中的改进方案：只在第一次分裂数组时创建两个线程，分别负责两半数组的排序，以后的递归过程中不再继续创建线程。算法如下：/ 秒表计时StopWatch timer = new StopWatch();timer.start();int first = new inta.length / 2;int second = new inta.length - first.length;System.arraycopy( a, 0, first, 0, first.length );System.arraycopy( a, first.length, second, 0, second.length );MergeSorterRunnable firstSorter = new MergeSorterRunnable( first );Thread firstThread = new Thread( firstSorter );firstThread.start();MergeSorterRunnable secondSorter = new MergeSorterRunnable( second );Thread secondThread = new Thread( secondSorter );secondThread.start();try firstThread.join();secondThread.join(); catch (InterruptedException e) / TODO Auto-generated catch blocke.printStackTrace();sorter.merge( first, second );timer.stop();图表 7 改进后的多线程二分排序算法源代码运行该算法，得到结果为：算法用时:734 ms可见，实验结果并没有像假设的一样。由于时间和能力有限，对多线程的研究先进行到此，找出问题所在并给出一种更好的解决方