可并行递归算法的递归多线程实现

／。 2 —z 厚 一 一一一 擗衙鼢蝈孽膣 精蝈 鲶霪赛翱 民。1 r3{2 ’、 ’l⋯， (广东工业大学计算机一系，广州 51OO90) 摘 要 本文讨亍}J 递归多残程方法．井用于实现可蕾行鎏扫算法。 关蝴并行．避 · ，登加 精国 {l 1 引 言 目前 ．包括 C和 C++在内的绝大多数程序设 计语言都不支持并行处理，仍然是以“单线程控制” 方式串行执行。Java提供了多线程枷制，支持一个 程序的多个任意层次的模块同时执行，向并行处理 跨出了一太步。从逻辑上讲．多线程是指在一个程 序中，同一时刻(或在单 CPU机器的一个极小时间 段 内)有多行程序在执行 。Java的线程 Thread与 Unix的进程 process是有区别的。在 Unix中，用 fork创建的子进程和父进程位于不 同的地址空间 ． 子进程拷贝了一份父进程的代码和数据。这种方 式不仅 CPU开销大，而且占用大量内存。而对Java 来说，数据区由各线程共享。Java语言的这一可以 指定并行处理多个活动的多线程功能，不仅能够用 于开发基于单处理器、多处理器以及网络韵各种应 用程序和多媒体软件，而且为正苦于没有合适的语 言达和演示并行概念及算法的课程，如数据结构 和操作系统等，提供了简明有效的工具。 Java的发展异常迅速，它的应用潜能仍有待 不断开发。本文提出了一种 Java递归多线程方法 ， 并用于实现可并行的递归算法。 2 可并行的尾递归算法的递归多线程实现 以快速排序为侧，对常规的单线程递归算法 l 来说，一趟扫描将当前排序区问一分为二，并依次 ． J 对两个子区间分别递归快速排序。由于是单线程 l 的，所以在前一个子区间层层递归排序且返回后， 计『 后一个子区间才开始递归排序。但是，按照教科书 1 的“趟”的概念 ，这两个子区间是可并行递归排序 算l 机I9 MoDERH c0MPuT { l 的，而且每一个递归导致对两个更小区间的递归也 是并行的。用 Java的多线程机制可 以如下递归地 实现快速排序算法 ： public cla8s QSort extends Thread f privateint a【 排序数组的引用 privateintlo~v； 本线程在数组 n中的排序区间的下界 p rate inthi ； 本线程在数组 a中的排序区间的上界 产构造器，线程之间的参数传递在构造线程时实现 -／ public QSort(int an[】1 int hi，int hi){ a=art；, 耐数组的引用赋值 l0w=l0： high=hi； l 产Quj Sort算法 void QuickSc~()throws Exception{ intlo=law： 血 hi =hi ； _啊tmid； 讧(hi >low1i 取区间的中间元素为枢纽元素 mid= (1ow+hi )／2】； 从区间的两端变善地向中间扫描 while(1o(=hi){ 从 当前左下标开始向右查 找第一个太于或等于枢纽元素的元素 wbn州1o《l1i )＆＆(a口o】low)＆＆(a【I| >mid" - - hi； 如果左 右下标未变错 ，则变换两个元素 1o<=hi)i intT= 咄 维普资讯 http://www.cqvip.com a J= hi]； al = H 10： — ·hi： l 线程休眠片捌，以实现与其它线程的 并行 tryi deeP ；) catch(]nterraptedExeeption e)f System．err．println( Exception +e．teStri~g()1； l l tryl 如果右下标未到选区间左端，则需对左于区间递归捧序 if(1owlIi 右子区间已完成归并 a[cu川=tem 1州 ； else ff(tem 1】