前几日翻看各种排序算法时,对希尔排序印象深刻:仅仅是将数组分成多份分别排序,就比普通的插入排序快上很多,感慨之余,想到能否用多线程的方式并行的计算希尔排序中不同的分组,如果可行,效率岂不是提升很多,于是花了些时间,写了个多线程的实现,记录在这里。
原版希尔排序
原版的Shell排序,来源于《算法(第4版)》
public class ShellSort { public static void sort(Comparable[] a){ int key = 1; int length = a.length; while(key < length/3){ key = key*3 + 1; } while(key != 1) { key = key/3; for(int i = 1 ; i<=key; i++){ for(int j = i; j<length ;j=j+key){ for(int m =j ; m>=0 && m-key >= 0 && SortingTool.less(a[m], a[m-key]); m= m-key) SortingTool.exch(a,m,m-key); } } } } }
工具类
import java.security.SecureRandom; public class SortingTool { private static final SecureRandom RANDOM = new SecureRandom(); public static boolean less(Comparable v, Comparable w){ return v.compareTo(w) < 0; } public static void exch(Comparable[] a, int i , int j){ Comparable t = a[i]; a[i] = a[j]; a[j] = t; } public static Integer[] geneIntArr(int size) { Integer[] result = new Integer[size]; for(int i = 0; i<result.length; i++){ result[i] = RANDOM.nextInt(); } return result; } public static boolean isSort(Comparable[] a){ for(int i = 0 ; i<a.length - 1 ;i++){ if(less(a[i+1], a[i])) return false; } return true; } }
使用多线程的版本
public class ParallelShellSort { public static void sort(Comparable[] a) { ExecutorService service = Executors.newWorkStealingPool(); int k = 1; int length = a.length; while (k < length / 3) { k = k * 3 + 1; } while (k != 1) { k = k / 3; /** * 对于同一个k值来说,k个线程同时操作数组的不同部分,且没有任何交集,所以不会出现读写不一致的问题, * 但是对于不同的k值来说,数组的同一个位置有可能被多个线程同时操作,会出现读写不一致的问题, * 例如k=333,某个线程尚未处理完成,这时如果进入下轮迭代k=111,另一个线程就可能和之前没有完成的线程之间出现问题。 * 所以对于每个k,使用CountDownLatch,保证k个线程都操作完成之后,在进入下一轮迭代。 */ CountDownLatch latch = new CountDownLatch(k); for (int i = 1; i <= k; i++) { service.submit(new ParallelShellSortRunnable(a, i, k, latch)); } try { latch.await(); } catch (InterruptedException e) { System.out.println("err.." + e.getMessage()); } } service.shutdown(); try { service.awaitTermination(Integer.MAX_VALUE, TimeUnit.MILLISECONDS); } catch (InterruptedException e) { System.out.println("error..."); } } }
public class ParallelShellSortRunnable implements Runnable{ private Comparable[] a; private int start; private int k; private CountDownLatch latch; public ParallelShellSortRunnable(Comparable[] a , int start, int k, CountDownLatch latch){ this.a = a; this.start = start; this.k = k; this.latch = latch; } @Override public void run() { int length = a.length; for(int j = start; j<length ;j=j+ k){ for(int m = j; m>=0 && m- k >= 0 && SortingTool.less(a[m], a[m- k]); m= m- k) SortingTool.exch(a,m,m- k); } latch.countDown(); } }
测试和分析
在i7 8核CPU,JDK 1.8的环境上,使用Integer数组测试(bin下有个comparison.sh,运行这个脚本或者使用SortingComparison可以进行测试)。
从结果上看,多线程的的版本比原版的希尔算法好很多,比Arrays.sort()也好一些,比较意外的是,在几十万到几百万的数量级上,似乎和Arrays.parallelSort()这个JDK提供的多线程版本排序方法不分伯仲,甚至有时候还能更快些,不过数量更大的时候,JDK的多线程版本就胜出不少了。
部分测试数据:
arrayParallelSort,500000数据,耗时200毫秒
arrayParallelSort,500000数据,耗时218毫秒
arrayParallelSort,500000数据,耗时213毫秒
arrayParallelSort,500000数据,耗时231毫秒
arrayParallelSort,500000数据,耗时224毫秒
arrayParallelSort,2000000数据,耗时674毫秒
arrayParallelSort,2000000数据,耗时780毫秒
arrayParallelSort,2000000数据,耗时732毫秒
arrayParallelSort,2000000数据,耗时739毫秒
arrayParallelSort,2000000数据,耗时764毫秒
parallelShell,500000数据,耗时287毫秒
parallelShell,500000数据,耗时310毫秒
parallelShell,500000数据,耗时313毫秒
parallelShell,500000数据,耗时278毫秒
parallelShell,500000数据,耗时369毫秒
parallelShell,2000000数据,耗时705毫秒
parallelShell,2000000数据,耗时663毫秒
parallelShell,2000000数据,耗时785毫秒
parallelShell,2000000数据,耗时746毫秒
parallelShell,2000000数据,耗时755毫秒
然而不用为这点成绩沾沾自喜,因为更多的测试发现事情并非这么简单。
运行 mvn test -Dtest=TestArraysParalleSort
结果
300万数据,耗时906毫秒
300万数据,耗时242毫秒
300万数据,耗时256毫秒
300万数据,耗时236毫秒
300万数据,耗时265毫秒
运行 mvn test -Dtest=TestParallelShell
结果
300万数据,耗时1189毫秒
300万数据,耗时1131毫秒
300万数据,耗时1086毫秒
300万数据,耗时1076毫秒
300万数据,耗时1133毫秒
在JIT的优化下,Array.parallelSort有了近乎妖孽般的提升,而本人的代码,似乎得不到JIT的帮助。。。
本文到这里基本就结束了,至于如何写出更容易被JIT优化的程序,已经超出了本人的能力范围,JDK这种API,确实不是谁都能写出来的。。
本文中的代码在这里可以找到。
相关推荐
使用多线程 实现冒泡排序,选择排序,快速排序
多线程实现排序算法的比较:希尔排序、快速排序、堆排序。用java语言实现,很经典,需要的可以下载看看!
父进程创建三个子线程,第一个子线程对数组的前半部分进行选择排序,第二个子进程对数组的后半部分进行选择排序,第三个子线程对两个已经排序好的数组部分进行归并排序,最后当所有子线程结束之后,父进程输出排序好...
shell的多线程,以及使用多线程编写shell脚本实现当前文件夹下批量插入MySQL。
多线程 排序 win32 多线程 排序 win32 多线程 排序 win32 多线程 排序 win32 多线程 排序 win32 多线程 排序 win32 多线程 排序 win32 多线程 排序 win32 多线程 排序 win32 多线程 排序 win32 多线程 排序 win32 多...
归 并 方 式 的 多 线 程 快 速 排 序算法
java多线程排序源程序,三种排序算法。希尔排序,快速排序,堆排序。
一个小小的例子,用简单排序小例子诠释多线程的用法和多线程的效率等
多线程快速排序,应付网络编程的小作业是个好东西!
VC++多线程实现三种排序算法比较----冒泡排序、快速排序、归并排序,很有意思,可以下载看看!
1.使用三种VC的多线程同步方法编写一个多线程的程序(要求在屏幕上先显示Hello,再显示World)。 1)基于全局变量的多线程同步程序; 2)基于事件的多线程同步程序; 3)基于临界区的多线程同步程序。
这是在WINDOWS下实现的多进程多线程的快速排序程序,其中为了加快排序速度使用了文件映射技术。
C# 的多线程排序示例 C# 的多线程排序示例 C# 的多线程排序示例 C# 的多线程排序示例 适合初学者使用
描述:由C#编写的多线程异步抓取网页的网络爬虫控制台程序 功能:目前只能提取网络链接,所用的两个记录文件并不需要很大。网页文本、图片、视频和html代码暂时不能抓取,请见谅。 但需要注意,网页的数目是非常...
使用TCPServer编写(多线程)socket服务 http://blog.csdn.net/ghostfromheaven/article/details/8653421
多线程Shell资源扫描器 哇嘎网络安全小组
winsock api 使用多线程编写服务器程序winsock api 使用多线程编写服务器程序winsock api 使用多线程编写服务器程序winsock api 使用多线程编写服务器程序winsock api 使用多线程编写服务器程序
操作系统经典实验:多线程实现排序冒泡排序与快速排序,C++编写,简单易懂
一个用Shell脚本实现多线程操作的代码