Java并发编程笔记（七）并行模式与算法2

并发编程算法设计模式

 2017/10/07   Share

改进的插入排序：希尔排序

插入排序是一种很常用的排序算法，它的基本思想是：一个未排序的数组（当然也可以是链表）可以分为2个部分，前半部分是已经排序的，后半部分是未排序的，在进行排序时候只需要在未排序的部分中选择一个元素将其插入到前面有序的数组中即可，最终未排序的元素越来越少直至为0，初始时可以假设已排序部分就是第一个元素。
插入排序算法如下：

/**
	 * 插入排序展示
	 */
	public static void insertSort(int arr[]){
		
		Objects.requireNonNull(arr,"数组不能为空！");
		
		int len = arr.length;
		int i,j,key;
		for(i=1;i<len;i++){
			//key为要插入的值 (未排序序列的第一个值)
			key = arr[i];
			j=i-1;
			//在已排序队列中找到这个元素的插入位置
			while(j >=0 && arr[j]>key){
				arr[j+1]= arr[j];
				j--;
			}
			//插入元素
			//插入到合适的位置
			arr[j+1]=key;
		}
		//使用java8 的流式编程遍历
		System.out.println("插入排序遍历：");
		Arrays.stream(arr).forEach(System.out::print);
	}

串行简单的插入排序是很难并行化的，因为这一次的数据插入依赖于上次一得到的有序数列。因此多个步骤之间无法并行。希尔排序是将整个数组间隔H分割为若干个子数组，子数组相互穿插在一起，每一次排序分别对每一个子数组进行排序。每组排序后递减H的值进行下轮更精确的排序直到H为1，此时就等价于插入排序。希尔排序的一个主要优点是即使一个最小元素在末尾由于每次移动以h为间隔进行因此数组末尾的小元素可以在很少的交换次数下被置换到最接近元素最终位置的地方。
下面为希尔排序的串行实现：

//以下为串行的希尔排序的实现
	public static void shellSortSingle(int[] arr){
		//定义跨度h
		int h=1;
		//获取一个合适的跨度值
		if(h <= arr.length/3){
			h = h*3+1;
		}
		while(h>0){
			//下面进行跨度为h的插入排序
			for(int i=h;i<arr.length;i++){
				if(arr[i] < arr[i-h]){
					int temp = arr[i];
					int j = i-h;
					while(j>=0 && arr[j] > temp){
						arr[j+h] = arr[j];
						j-=h;
					}
					//插入合适的位置
					arr[j+h]=temp;
				}
				//计算出下一个h的值 直到h为1  退化为插入排序
				h = (h-1)/3;
			}
		}
		System.out.print("希尔排序结果为：");
		Arrays.stream(arr).forEach(System.out::println);
	}

很显然，希尔排序针对不同的子数组进行排序，这样的话各个子数组之间是完全独立的，易于改写成并行程序：
并发希尔排序：

public static class ConcurrShellSort implements Runnable
	{
		int i=0;
		int h=0;
		CountDownLatch l ;
		static int[] arr;
		public ConcurrShellSort(int i, int h, CountDownLatch l) {
			super();
			this.i = i;
			this.h = h;
			this.l = l;
		}
		@Override
		public void run() {
			if(arr[i]<arr[i-h]){
				int temp = arr[i];
				int j = i -h;
				while( j>=0 && arr[j]>temp){
					arr[j+h]=arr[j];
					j -= h;
				}
				arr[j+h] = temp;
			}
			//一个线程执行完计数器减少1
			l.countDown();
		}
	}

main方法：

int h=1;
		ConcurrShellSort.arr = arr;
		CountDownLatch latch=null;
		ExecutorService pool = Executors.newCachedThreadPool();
		while (h<= ConcurrShellSort.arr.length /3){
			 h = h*3 +1;
		}
		while(h>0){
			System.out.println("h= "+h);
			if(h>=4) latch = new CountDownLatch(ConcurrShellSort.arr.length-1);
			for(int i = h ; i<ConcurrShellSort.arr.length;i++){
				//控制线程数量 如果h大于4就并行 小于4串行执行
				if(h>=4){
					pool.execute(new ConcurrShellSort(i, h, latch));
					System.out.println(Arrays.toString(ConcurrShellSort.arr));
				}else{
					//执行串行的插入排序
					if(ConcurrShellSort.arr[i]>ConcurrShellSort.arr[i-h]){
						int temp = ConcurrShellSort.arr[i];
						int j= i-h;
						while(j>=0 && ConcurrShellSort.arr[j]>temp){
							ConcurrShellSort.arr[j+h]=ConcurrShellSort.arr[j];
							j-=h;
						}
						ConcurrShellSort.arr[j+h]=temp;
					}
					System.out.println(Arrays.toString(ConcurrShellSort.arr));
				}
			}
			//等待下一个线程完成
			latch.await();	
			//计算下一个h的值
			h  = (h-1)/3;
		}

并行算法：矩阵乘法

Linus认为并行程序最有用的地方就是服务端和图像处理方面，那么矩阵乘法是非常有用的，包括在神经网络、模式识别等领域有着广泛的作用。这里介绍矩阵乘法的并行化实现。
在矩阵乘法中，第一个矩阵的列数必须和第二个矩阵的行数相同，例如矩阵A和矩阵B相乘，矩阵A为4行2列，矩阵B为2行四列，它们相乘后得到的是4行4列的矩阵，新矩阵每一个元素为矩阵A和B对应的行列乘积求和。如果需要并行计算，一种简单的策略就是对A矩阵进行垂直分割，得到子矩阵B1和B2，此时我们只需要分别计算这些子矩阵的乘积将结果进行拼接，就能得到原始矩阵A和B的乘积。如图展示了这种并行计算的策略

当然还可以拆分的更小，看需求。
矩阵乘法性质：

Java中我们使用开源ForkJoin框架来实现矩阵乘法并行的想法，为了方便矩阵计算我们使用jMatrices开源软件，作为矩阵的计算工具，其中使用的主要API如下：

具体操作可参阅官方文档，这里简单介绍不再赘述。

CATALOG

1. 改进的插入排序：希尔排序
2. 并行算法：矩阵乘法

