转载

并发进阶(八)算法的并发执行

导读


并发运行的一个很重要的功能就是提升系统的性能,当我们的程序中有很多IO操作时,使用多线程并发执行就可以显著的提升系统的性能,本篇将以多线程并发下载为例,讲解并发的优越性。

我们先定义两个类Image和DownloadTask,Image用于模拟一个从网络上下载的图片,这个类没有实际的功能,它会为每个Image的对象提供一个名字("Image"+编号);DownloadTask用于模拟下载任务,它实现了Callable接口,call()方法里面会等待1秒钟(假装自己在下载),等待一秒后创建一个新的Image对象返回给调用者(假装自己下载成功)。具体代码如下:

class Image {
    private static int counter = 0;
    private String name = "Image" + counter++;
    public String toString() {
	return name;
    }
}
class DownloadTask implements Callable<Image> {
    public Image call() throws Exception {
	try {
	    Thread.sleep(1000);
	} catch (InterruptedException e) {}
	return new Image();
    }
}

定义完下载任务我们应该定义存储任务的结构,通常情况下分为两种:线性结构和树形结构。线性结构很简单,典型的例子就是将这些任务都存储在ArrayList里面,使用一个循环就可以遍历ArrayList;树形结构稍微有些复杂,更适合使用递归遍历。

01

循环算法

根据上面定义的DownloadTask,我们可以将DownloadTask存储在ArrayList中。创建一个CachedThreadPool用于执行DownloadTask,此外使用Future获取下载的结果,所有DownloadTask返回的Future都需要保存到ArrayList中,用于最后获取所有的结果。具体代码如下:

public class ParallelLoop {
    public static void main(String[] args) throws Exception {
	ExecutorService exec = Executors.newCachedThreadPool();
	List<Future<Image>> futures = new ArrayList<Future<Image>>();
	List<DownloadTask> downloadTasks = getDownloadTaskList();
	    long startTime = System.currentTimeMillis();
	    for(DownloadTask dt : downloadTasks) {
	    futures.add(exec.submit(dt));
	}
	for(Future<Image> f : futures) {
	    System.out.println(f.get());
	}
	long endTime = System.currentTimeMillis();
	System.out.println("Download cost " + (endTime-startTime)/1000.0 + " Second.");
	exec.shutdown();
    }
    private static List<DownloadTask> getDownloadTaskList() {
	List<DownloadTask> downloadTasks = new ArrayList<DownloadTask>();
	for(int i=0; i< 10000; i++) {
	    downloadTasks.add(new DownloadTask());
	}
	return downloadTasks;
    }
}

运行结果如下:

...

Image9400

Download cost 4.663 Minutes.

在上面的代码中我们创建了一万个下载任务,将所有的任务都提交到缓存线程池中,在前面的章节中我们提到过缓存线程池是一个没有最大线程数的线程池,因此可以根据需要无限扩展。创建了一个ArrayList<Future>用于存储提交任务时返回的Future对象,最后循环遍历这个ArrayList<Future>,将Future的结果打印出来。在这段代码中我们使用System.currentTimeMillis()获取当前时间,最后计算出并发下载一万个任务所消耗的总时间(4.663s),如果使用单线程下载则需要消耗一万秒,可以看出多线程可以大幅提升系统的性能。

递归算法

02

首先我们需要定义一个树形的数据结构,具体代码如下。每个节点有两个属性:当前节点的任务和子节点。DownloadTaskTree类有两个构造函数,无参数的构造函数可以生成一个叶子节点,另一个构造函数可以接受一个子节点的集合,生成一个树枝节点。

class DownloadTaskTree {
    private DownloadTask downloadTask;
    private List<DownloadTaskTree> childrenTask;
    public DownloadTaskTree() {
	this.downloadTask = new DownloadTask();
	this.childrenTask = new ArrayList<DownloadTaskTree>();
    }
    public DownloadTaskTree(List<DownloadTaskTree> childrenTask) {
	this.downloadTask = new DownloadTask();
	this.childrenTask = childrenTask;
    }
    public DownloadTask getDownloadTask() {
	return downloadTask;
    }
    public List<DownloadTaskTree> getChildrenTask() {
	return childrenTask;
    }
}

接下来就可以实现递归算法了,我们使用getDownloadTaskTree()方法对这个树形结构进行初始化,getDownloadTaskTree()方法也是一个递归方法。得到下载任务树后需要遍历树的每个枝节点和叶子节点,submitTask()方法得到树的根节点后,先提交根节点上的任务,再将所有的子节点提交给submitTask()方法,整个过程中所有submitTask()方法使用的都是一个线程池和ArrayList<Future>。

public class ParallelRecursive {
    public static void main(String[] args) throws Exception {
	ExecutorService exec = Executors.newCachedThreadPool();
	List<Future<Image>> futures = new ArrayList<Future<Image>>();
	DownloadTaskTree root = getDownloadTaskTree(6);		
	long startTime = System.currentTimeMillis();
	submitTask(exec, root, futures);
	for(Future<Image> f : futures) {
	    System.out.println(f.get());
	}
	long endTime = System.currentTimeMillis();
	System.out.println(futures.size());
	System.out.println("Download cost " + (endTime-startTime)/1000.0 + " Second.");
	exec.shutdown();
    }	
    private static DownloadTaskTree getDownloadTaskTree(int deep) {
 	if(deep-- == 1) {
	    return new DownloadTaskTree();
	}
	List<DownloadTaskTree> childrenTask = new ArrayList<DownloadTaskTree>();
	for(int i=0; i < 6; i++) {
	    childrenTask.add(getDownloadTaskTree(deep));
	}
	return new DownloadTaskTree(childrenTask);
    }	
    private static void submitTask(ExecutorService exec, 
                                 DownloadTaskTree root, 
                                 List<Future<Image>> futures) {
	futures.add(exec.submit(root.getDownloadTask()));
 	for(DownloadTaskTree child : root.getChildrenTask()) {
	    submitTask(exec, child, futures);
	}
    }
}

运行结果如下:

...

Image7926

9331

Download cost 4.278 Second.

由上面的运行结果可以看出,此次共运行了9331个任务,和循环算法的任务数差不多,总共消耗的时间也相差不多,因此可以得出结论:循环和递归的性能是不相上下的。


小码的总结

如果系统运行的任务不是计算密集型的,使用并发可以有效的提高系统整体的性能。使用线程池可以有效的重复利用已有的线程,规避了频繁创建、销毁线程的情况,在一定程度上避免浪费系统的性能。如果任务是计算密集型的,使用这种方法就很难提升性能了(除非CPU的核心数很多),因为创建线程时需要消耗一部分性能,而任务运行过程中CPU一直没有空闲,因此多线程的优越性就无从体现了。

原文链接:https://mp.weixin.qq.com/s?__biz=MzU0MjgxNTg5Mg==&mid=2247483820&idx=1&sn=ee7dce38e308c9616f1fd82f84f9139e&chksm=fb15a257cc622b411c133ec0b4ed4daf648f8cc7017c5307a294a1d0016df59af00896043fbd&mpshare=1&scene=23&srcid=0726VbBlYL8J8oTpczIUAjJ4#rd

正文到此结束
Loading...