资源描述:
《应用forkjoin——精益求精-java开发java经验技巧》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、应用Forkjoin精益求精木文由ImportNew■靳禹翻译自javaadvento欢迎加入翻译小组。转载请见文末要求。随着JDK7被广大程序员所使用,Forkjoin也随着映入很多人的眼帘。不过,可能大多数人还没有机会在日常工作中真止使用Forkjoin。在没有真止使用ForkjoinZ前,大家可能述分不清楚它究竟跟一个常见的线程池冇什么区别[1]0所以,我写这篇文章的目的就是以一个简单但是乂有说明性的代码示例来阐释对Forkjoin的用法。在本文的示例中,我会分别对线性方式、线程池和Forkjoin处理模式进行性能测试。测试代码托管在Github:https://github・com
2、/fbunau/javaadvent-forkjoin0实际问题设想一下我们有这样一个系统,系统屮部分组建需要吋刻保留每一吋刻最终的股价数据。这些数据可以用一个整型数组保存在内存中(如果我们用bps,字节/秒來统计)。这个组件的客户端会发起一些请求,比如:在timel和time2ZMj,哪个时间点的股价是最低的?请求的发起可以是自动的算法,也可以是操作员在操作界面上使用鼠标进行框选。示例中的7次查询请求然后我们不妨假设,我们得到了來自同一个客户端的若干个这种请求,所冇请求组成了一个杳询任务。这样的合并可能是为了减少网络传输和通信的往返时间。接下来,我们的服务组建就会得到大小不等的任务包,例
3、如10次查询(由手工操作形成的查询),或者是100次查询的任务甚至10000000次查询的任务(由算法生成的查询)。同吋,我们还有很多这样的客户端程序,每个客户端程序都在发出不同大小的查询任务。参考Task.TaskTypeo核心问题和解决方案我们要解决的核心问题就是RMQ问题。下面是Wikipedia对RMQ的解释[2]:“给定一组对象,这些对彖来自有完善的大小,顺序定义的集合(比如数字)。一个从数组索引i到索引j的范围最小查询(RMQ)就是查找在子数组A[i,j]中最小元素的下标。”“例如,有数组A=[0,5,2,5,4,3,1,6,3],则RMQA[3,8]的结果就是7,因为A[3,
4、8]=[2,5,4,3,1,6]。其屮最小值1的下标在数组A中是7。”我们有一个非常高效的数据结构来解决这个问题,那就是“分段树”(SegmentTree)。我不会详细讲什么是分段树,有兴趣的读者可以参考经典的Topcoder文章⑶。因为这些细节对于我的ForkJoin示例并不是很重要,我提及分段树是因为它远比简单的加法要冇意思,而月•它的核心思想与fork-join相同:这就是分治的原理,把任务拆散进行计算,最后合并结果!这种数据结构的初始化时间复朵度为0(n),之后的查询复朵度为0(logN),N就是我们单位时间内数组中的价格总数。假设一个任务T包含了M个需要执行的杳询。如杲按照计算机
5、科学中的学术方式进行执行,你就会说我们就用这种数据结构依次处理每一个任务,然后我们会得到如下的时间复杂度:难道我们不能更有效率吗!?在一个理论上的冯•诺依曼计算机上,这已经是最有效率的了,但是我们在实践中可以更有效率。一个很容易造成混淆的时间复杂度比较是因为学术上认为0(n/4)==0(n),所以有人会以为上面对N除以一个常数不会对最终执行效率造成多大影响,但是影响确实存在!不妨停下來想一想,等待10分钟、10小吋、10年,还是40分钟、40小时、40年,能一样吗?并行计算所以就我们面对的问题而言,我们怎么计算能更快一些?因为现在的计算机都右多个核心可以进行独立计算,所以我们可以利用这一点
6、让他们同时做不同的计算。借助Forkjoin框架,我们很容易实现这一点。我一开始试图改变一些RMQ的数据结构然后将一些操作并行化,这些操作已经达到了logN的负责度。当然,我的尝试失败了,调度上的开销对于这些简短的逻辑运算来说太高昂了。最后,我发现」I•:确的途径是针对Mi常数参数进行并行化处理。线程池在我们演示如何使用ForkJoinZ前,我们先來看看如果是线程池的话,我们的实现会是怎样的。代码见:TaskProcessorPool.java我们可以有一个4个worker线程的线程池,当一个任务到达时,我们把任务放到队列里。当一个worker线程空闲时,这个worker就从队头取一个待执
7、行的任务并月•执行。这种方式对于大小相同,口任务大小适中可控的任务来说是不错的。但是当任务大小不一致的吋候就会遇到问题。就是说,一个worker可能被缠在冗长的任务中,然后其他的worker闲着没事做。图中显示线穆池的实现在4个单位时间内,且没有更多的的任务加入到队列小的情况下,4个线程在最多可能的完成16任务的情况下完成了9个任务。(效率是56%)分治合并ForkJoin方式在你可以把一个大任务分成若干个小任务吋非常的