淘宝面试题：如何充分利用多核CPU，计算很大的List中所有整数的和

by

at 2010-07-12 23:32:21

original http://www.javaeye.com/topic/711162

引用

前几天在网上看到一个淘宝的面试题：有一个很大的整数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)的值。

示意图如下：

三：详细编码实现
代码中有很详细的注释，这里就不解释了。

/
 * 计算List中所有整数的和<br>
 * 采用多线程，分割List计算
 * @author 飞雪无情
 * @since 2010-7-12
 */
public class CountListIntegerSum {
    private long sum;//存放整数的和
    private CyclicBarrier barrier;//障栅集合点(同步辅助器)
    private List<Integer> list;//整数集合List
    private int threadCounts;//使用的线程数
    public CountListIntegerSum(List<Integer> list,int threadCounts) {
        this.list=list;
        this.threadCounts=threadCounts;
        barrier=new CyclicBarrier(threadCounts+1);//创建的线程数和主线程main
    }
    /
     * 获取List中所有整数的和
     * @return List中所有整数的和
     /
    public long getIntegerSum(){
        ExecutorService exec=Executors.newFixedThreadPool(threadCounts);
        int len=list.size()/threadCounts;//平均分割List
                if(list.size()%threadCounts!=0){//不整除，增加一个线程
            threadCounts=threadCounts+1;
        }
        for(int i=0;i<threadCounts;i++){
            //创建线程任务
            exec.execute(new SubIntegerSumTask(list.subList(ilen, len(i+1))));
        }
        try {
            barrier.await();//关键，使该线程(main主线程)在障栅处等待，直到所有的线程都到达障栅处
        } catch (InterruptedException e) {
            System.out.println(Thread.currentThread().getName()+":Interrupted");
        } catch (BrokenBarrierException e) {
            System.out.println(Thread.currentThread().getName()+":BrokenBarrier");
        }
        exec.shutdown();
        return sum;
    }
    /**
     * 分割计算List整数和的线程(任务)<br>
     * 内部类实现，可以隐藏实现细节，更便于访问外部类的私有变量
     * @author 飞雪无情
     * @since 2010-7-12
     /
    private class SubIntegerSumTask implements Runnable{
        private List<Integer> subList;
        public SubIntegerSumTask(List<Integer> subList) {
            this.subList=subList;
        }
        public void run() {
            long subSum=0L;
            for(Integer i:subList){
                subSum+=i;
            }
            synchronized(CountListIntegerSum.this){//在CountListIntegerSum对象上同步
                sum+=subSum;
            }
            try {
                barrier.await();//关键，使该线程在障栅处等待，直到所有的线程都到达障栅处
            } catch (InterruptedException e) {
                System.out.println(Thread.currentThread().getName()+":Interrupted");
            } catch (BrokenBarrierException e) {
                System.out.println(Thread.currentThread().getName()+":BrokenBarrier");
            }
            System.out.println("分配给线程："+Thread.currentThread().getName()+"那一部分List的整数和为：\tSubSum:"+subSum);
        }

}


}

有人可能对barrier=new CyclicBarrier(threadCounts+1);//创建的线程数和主线程main有点不解，不是采用的线程(任务)数是threadCounts个吗？怎么为CyclicBarrier设置的给定数量的线程参与者比我们要采用的线程数多一个呢？答案就是这个多出来的一个用于控制main主线程的，主线程也要等待，它要等待其他所有的线程完成才能输出sum值，这样才能保证sum值的正确性，如果main不等待的话，那么结果将是不可预料的。

/*
 * 计算List中所有整数的和测试类
 * @author 飞雪无情
 * @since 2010-7-12
 /
public class CountListIntegerSumMain {

/**
 * @param args
 */
public static void main(String[] args) {
    List&lt;Integer&gt; list = new ArrayList&lt;Integer&gt;();
    int threadCounts = 10;//采用的线程数
    //生成的List数据
    for (int i = 1; i &lt;= 1000000; i++) {
        list.add(i);
    }
    CountListIntegerSum countListIntegerSum=new CountListIntegerSum(list,threadCounts);
    long sum=countListIntegerSum.getIntegerSum();
    System.out.println(&quot;List中所有整数的和为:&quot;+sum);
}


}

四：总结
本文主要通过一个淘宝的面试题为引子，介绍了并发的一点小知识，主要是介绍通过CyclicBarrier同步辅助器辅助多个并发任务共同完成一件工作。Java SE5的java.util.concurrent引入了大量的设计来解决并发问题，使用它们有助于我们编写更加简单而健壮的并发程序。

      <br><br>
      作者: <a href="http://flysnow.javaeye.com">飞雪无情</a> 
      <br>
      声明: 本文系JavaEye网站发布的原创文章，未经作者书面许可，严禁任何网站转载本文，否则必将追究法律责任！
      <br><br>
      <span style="color:red">
        <a href="http://www.javaeye.com/topic/711162" style="color:red">已有 <strong>28</strong> 人发表回复，猛击-&gt;&gt;<strong>这里</strong>&lt;&lt;-参与讨论</a>
      </span>
      <br><br><br>

JavaEye推荐

Google Reader