前几日翻看各种排序算法时,对希尔排序印象深刻:仅仅是将数组分成多份分别排序,就比普通的插入排序快上很多,感慨之余,想到能否用多线程的方式并行的计算希尔排序中不同的分组,如果可行,效率岂不是提升很多,于是花了些时间,写了个多线程的实现,记录在这里。
原版希尔排序
原版的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,确实不是谁都能写出来的。。
本文中的代码在这里可以找到。
相关推荐
7. 希尔排序(Shell Sort):希尔排序是插入排序的一种更高效的改进版本,通过比较相距一定间隔的元素来工作,逐步减小间隔直到为1,这样可以减少元素的移动次数。C语言实现希尔排序需要用到间隔序列和插入排序。 8...
4. **希尔排序(Shell Sort)**: 希尔排序是插入排序的一种更高效的改进版本。它通过将待排序的数组元素按某个增量分组,然后对每组使用直接插入排序算法排序。随着增量逐渐减少,每组包含的关键词越来越多,当...
希尔排序(Shell Sort)是数据结构中的一个经典排序算法,由Donald Shell于1959年提出。它是插入排序的一种更高效的改进版本,通过将待排序的元素按照一个增量序列分组,然后对每个组进行插入排序,逐步减小增量,...
- **希尔排序(Shell Sort)**:是插入排序的改进版,通过间隔序列(如Hibbard、Shell、Sedgewick等)来减少比较次数,提高了效率。 - **计数排序(Counting Sort)、桶排序(Bucket Sort)和基数排序(Radix Sort...
是否可以使用其他的排序算法,如希尔排序(Shell Sort)?在这里,我们可以比较不同的排序算法,分析它们的时间和空间复杂度,并选择合适的算法来解决实际问题。 此外,本文还涉及到链表的反转问题,即将单链表 1->...
5. 希尔排序(Shell Sort): 希尔排序是一种插入排序的优化版本,通过增量序列对数组进行多次插入排序,逐步减小增量以提高效率。题目中未给出具体排序过程,所以无法推断出确切的排序结果。 6. 虚拟存储系统与...
void shellSort(int arr[]) { int n = arr.length; // 开始间隔排序 for (int gap = n / 2; gap > 0; gap /= 2) { for (int i = gap; i ; i++) { int temp = arr[i]; int j; for (j = i; j >= gap && arr[j ...
- **希尔排序**(Shell Sort):改进版插入排序,通过分组减少数据移动距离,复杂度介于O(nlog2n)到O(n^2)之间,不稳定。 - **快速排序**:通过“分而治之”的思想,把一个数组分为较小和较大的两个子数组,复杂度...
- **知识点解析**:希尔排序(Shell Sort)是一种基于插入排序的算法,但它通过引入间隔(gap)的概念来改进插入排序的效率。希尔排序属于插入排序的一种变体,因此正确答案是**D.插入排序**。 ### 16. 八进制到二...
希尔排序(Shell Sort)是一种插入类排序算法,通过比较相隔一定间隔的元素来进行排序。随着算法的进行,间隔逐渐减小直至为1,此时变成简单的插入排序。 ### 13. Java 线程同步机制 **知识点概述:** `...
- **希尔排序(Shell Sort)**:是一种基于插入排序的算法,通过引入间隔序列来提高插入排序的效率。 - **插入排序(Insertion Sort)**:基本思想是从数组的第二个元素开始,逐个将其插入到已排序的序列中。 #### ...