怎么充分利用多核CPU，计算很大的List中所有整数的和

如何充分利用多核CPU，计算很大的List中所有整数的和

引用前几天在网上看到一个淘宝的面试题：有一个很大的整数list，需要求这个list中所有整数的和，写一个可以充分利用多核CPU的代码，来计算结果。
一：分析题目?
从题中可以看到“很大的List”以及“充分利用多核CPU”，这就已经充分告诉我们要采用多线程(任务)进行编写。具体怎么做呢？大概的思路就是分割List，每一小块的List采用一个线程(任务)进行计算其和，最后等待所有的线程(任务)都执行完后就可得到这个“很大的List”中所有整数的和。?
二：具体分析和技术方案?
既然我们已经决定采用多线程(任务)，并且还要分割List，每一小块的List采用一个线程(任务)进行计算其和，那么我们必须要等待所有的线程(任务)完成之后才能得到正确的结果，那么怎么才能保证“等待所有的线程(任务)完成之后输出结果呢”？这就要靠java.util.concurrent包中的CyclicBarrier类了。它是一个同步辅助类，它允许一组线程(任务)互相等待，直到到达某个公共屏障点 (common barrier point)。在涉及一组固定大小的线程(任务)的程序中，这些线程(任务)必须不时地互相等待，此时 CyclicBarrier 很有用。简单的概括其适应场景就是：当一组线程(任务)并发的执行一件工作的时候，必须等待所有的线程(任务)都完成时才能进行下一个步骤。具体技术方案步骤如下：?

• 分割List，根据采用的线程(任务)数平均分配，即list.size()/threadCounts。
• 定义一个记录“很大List”中所有整数和的变量sum，采用一个线程(任务)处理一个分割后的子List，计算子List中所有整数和(subSum)，然后把和(subSum)累加到sum上。
• 等待所有线程(任务)完成后输出总和(sum)的值。
  示意图如下：?
  
  ?三：详细编码实现?
  代码中有很详细的注释，这里就不解释了。

  /**  * 使用ExecutorService的invokeAll方法计算  * @author 飞雪无情  *  */  public class CountSumWithCallable {        /**      * @param args      * @throws InterruptedException       * @throws ExecutionException       */      public static void main(String[] args) throws InterruptedException, ExecutionException {          int threadCounts =19;//使用的线程数          long sum=0;          ExecutorService exec=Executors.newFixedThreadPool(threadCounts);          List<Callable<Long>> callList=new ArrayList<Callable<Long>>();          //生成很大的List          List<Integer> list = new ArrayList<Integer>();          for (int i = 0; i <= 1000000; i++) {              list.add(i);          }          int len=list.size()/threadCounts;//平均分割List          //List中的数量没有线程数多（很少存在）          if(len==0){              threadCounts=list.size();//采用一个线程处理List中的一个元素              len=list.size()/threadCounts;//重新平均分割List          }          for(int i=0;i<threadCounts;i++){              final List<Integer> subList;              if(i==threadCounts-1){                  subList=list.subList(i*len,list.size());              }else{                  subList=list.subList(i*len, len*(i+1)>list.size()?list.size():len*(i+1));              }              //采用匿名内部类实现              callList.add(new Callable<Long>(){                  public Long call() throws Exception {                      long subSum=0L;                      for(Integer i:subList){                          subSum+=i;                      }                      System.out.println("分配给线程："+Thread.currentThread().getName()+"那一部分List的整数和为：\tSubSum:"+subSum);                      return subSum;                  }              });          }          List<Future<Long>> futureList=exec.invokeAll(callList);          for(Future<Long> future:futureList){              sum+=future.get();          }          exec.shutdown();          System.out.println(sum);      }    }  

  ?

  一些感言?
  这篇文章是昨天夜里11点多写好的，我当时是在网上看到了这个题目，就做了一下分析，写了实现代码，由于水平有限，难免有bug，这里感谢xifo等人的指正。这些帖子从发表到现在不到24小时的时间里创造了近9000的浏览次数，回复近100，这是我没有想到的，javaeye很久没这么疯狂过啦。这不是因为我的算法多好，而是因为这个题目、这篇帖子所体现出的意义。大家在看完这篇帖子后不光指正错误，还对方案进行了改进，关键是思考，人的思维是无穷的，只要我们善于发掘，善于思考，总能想出一些意想不到的方案。?
  
  从算法看，或者从题目场景对比代码实现来看，或许不是一篇很好的帖子，但是我说这篇帖子是很有意义的，方案也是在很多场景适用，有时我们可以假设这不是计算和，而是把数据写到一个个的小文件里，或者是分割进行网络传输等等，都有一定的启发，特别是回帖中的讨论。?
  
  单说一下回帖，我建议进来的人尽量看完所有的回帖，因为这里是很多人集思广益的精华，这里有他们分析问题，解决问题的思路，还有每个人提到的解决方案，想想为什么能用?为什么不能用?为什么好?为什么不好??

  ?

  ?

  摘自：http://www.iteye.com/topic/711162

查看更多 下一篇