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

Posted on

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

永久链接:http://flysnow.iteye.com/blog/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)的值。 示意图如下: 三:详细编码实现 代码中有很详细的注释,这里就不解释了。 Java代码 收藏代码
  1. ///
  2. /* 计算List中所有整数的和
  3. /* 采用多线程,分割List计算
  4. /* @author 飞雪无情
  5. /* @since 2010-7-12
  6. /*/
  7. public class CountListIntegerSum {
  8. private long sum;//存放整数的和
  9. private CyclicBarrier barrier;//障栅集合点(同步器)
  10. private List list;//整数集合List
  11. private int threadCounts;//使用的线程数
  12. public CountListIntegerSum(List list,int threadCounts) {
  13. this.list=list;
  14. this.threadCounts=threadCounts;
  15. }
  16. ///
  17. /* 获取List中所有整数的和
  18. /* @return
  19. /*/
  20. public long getIntegerSum(){
  21. ExecutorService exec=Executors.newFixedThreadPool(threadCounts);
  22. int len=list.size()/threadCounts;//平均分割List
  23. //List中的数量没有线程数多(很少存在)
  24. if(len==0){
  25. threadCounts=list.size();//采用一个线程处理List中的一个元素
  26. len=list.size()/threadCounts;//重新平均分割List
  27. }
  28. barrier=new CyclicBarrier(threadCounts+1);
  29. for(int i=0;i<threadCounts;i++){
  30. //创建线程任务
  31. if(i==threadCounts-1){//最后一个线程承担剩下的所有元素的计算
  32. exec.execute(new SubIntegerSumTask(list.subList(i/*len,list.size())));
  33. }else{
  34. exec.execute(new SubIntegerSumTask(list.subList(i/len, len/(i+1)>list.size()?list.size():len/*(i+1))));
  35. }
  36. }
  37. try {
  38. barrier.await();//关键,使该线程在障栅处等待,直到所有的线程都到达障栅处
  39. } catch (InterruptedException e) {
  40. System.out.println(Thread.currentThread().getName()+":Interrupted");
  41. } catch (BrokenBarrierException e) {
  42. System.out.println(Thread.currentThread().getName()+":BrokenBarrier");
  43. }
  44. exec.shutdown();
  45. return sum;
  46. }
  47. ///
  48. /* 分割计算List整数和的线程任务
  49. /* @author lishuai
  50. /*
  51. /*/
  52. public class SubIntegerSumTask implements Runnable{
  53. private List subList;
  54. public SubIntegerSumTask(List subList) {
  55. this.subList=subList;
  56. }
  57. public void run() {
  58. long subSum=0L;
  59. for (Integer i : subList) {
  60. subSum += i;
  61. }
  62. synchronized(CountListIntegerSum.this){//在CountListIntegerSum对象上同步
  63. sum+=subSum;
  64. }
  65. try {
  66. barrier.await();//关键,使该线程在障栅处等待,直到所有的线程都到达障栅处
  67. } catch (InterruptedException e) {
  68. System.out.println(Thread.currentThread().getName()+":Interrupted");
  69. } catch (BrokenBarrierException e) {
  70. System.out.println(Thread.currentThread().getName()+":BrokenBarrier");
  71. }
  72. System.out.println("分配给线程:"+Thread.currentThread().getName()+"那一部分List的整数和为:\tSubSum:"+subSum);
  73. }
  74. }
  75. }

///

/ 计算List中所有整数的和
/
采用多线程,分割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;
}

//*/*
 /* 获取List中所有整数的和

 /* @return
 /*/

public long getIntegerSum(){
    ExecutorService exec=Executors.newFixedThreadPool(threadCounts);

    int len=list.size()/threadCounts;//平均分割List
    //List中的数量没有线程数多(很少存在)

    if(len==0){
        threadCounts=list.size();//采用一个线程处理List中的一个元素

        len=list.size()/threadCounts;//重新平均分割List
    }

    barrier=new CyclicBarrier(threadCounts+1);
    for(int i=0;i<threadCounts;i++){

        //创建线程任务
        if(i==threadCounts-1){//最后一个线程承担剩下的所有元素的计算

            exec.execute(new SubIntegerSumTask(list.subList(i/*len,list.size())));
        }else{

            exec.execute(new SubIntegerSumTask(list.subList(i/*len, len/*(i+1)>list.size()?list.size():len/*(i+1))));
        }

    }
    try {

        barrier.await();//关键,使该线程在障栅处等待,直到所有的线程都到达障栅处
    } 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整数和的线程任务
 /* @author lishuai

 /*
 /*/

public 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不等待的话,那么结果将是不可预料的。 Java代码 收藏代码

  1. ///
  2. /* 计算List中所有整数的和测试类
  3. /* @author 飞雪无情
  4. /* @since 2010-7-12
  5. /*/
  6. public class CountListIntegerSumMain {
  7. ///
  8. /* @param args
  9. /*/
  10. public static void main(String[] args) {
  11. List list = new ArrayList();
  12. int threadCounts = 10;//采用的线程数
  13. //生成的List数据
  14. for (int i = 1; i <= 1000000; i++) {
  15. list.add(i);
  16. }
  17. CountListIntegerSum countListIntegerSum=new CountListIntegerSum(list,threadCounts);
  18. long sum=countListIntegerSum.getIntegerSum();
  19. System.out.println("List中所有整数的和为:"+sum);
  20. }
  21. }

///

/ 计算List中所有整数的和测试类 / @author 飞雪无情

/ @since 2010-7-12 //

public class CountListIntegerSumMain {

//*/*
 /* @param args

 /*/
public static void main(String[] args) {

    List<Integer> list = new ArrayList<Integer>();
    int threadCounts = 10;//采用的线程数

    //生成的List数据
    for (int i = 1; i <= 1000000; i++) {

        list.add(i);
    }

    CountListIntegerSum countListIntegerSum=new CountListIntegerSum(list,threadCounts);
    long sum=countListIntegerSum.getIntegerSum();

    System.out.println("List中所有整数的和为:"+sum);
}

} 四:总结 本文主要通过一个淘宝的面试题为引子,介绍了并发的一点小知识,主要是介绍通过CyclicBarrier同步辅助器辅助多个并发任务共同完成一件工作。Java SE5的java.util.concurrent引入了大量的设计来解决并发问题,使用它们有助于我们编写更加简单而健壮的并发程序。 附mathfox提到的ExecutorService.invokeAll()方法的实现 这个不用自己控制等待,invokeAll执行给定的任务,当所有任务完成时,返回保持任务状态和结果的 Future 列表。sdh5724也说用了同步,性能不好。这个去掉了同步,根据返回结果的 Future 列表相加就得到总和了。

Java代码 收藏代码

  1. ///
  2. /* 使用ExecutorService的invokeAll方法计算
  3. /* @author 飞雪无情
  4. /*
  5. /*/
  6. public class CountSumWithCallable {
  7. ///
  8. /* @param args
  9. /* @throws InterruptedException
  10. /* @throws ExecutionException
  11. /*/
  12. public static void main(String[] args) throws InterruptedException, ExecutionException {
  13. int threadCounts =19;//使用的线程数
  14. long sum=0;
  15. ExecutorService exec=Executors.newFixedThreadPool(threadCounts);
  16. List> callList=new ArrayList>();
  17. //生成很大的List
  18. List list = new ArrayList();
  19. for (int i = 0; i <= 1000000; i++) {
  20. list.add(i);
  21. }
  22. int len=list.size()/threadCounts;//平均分割List
  23. //List中的数量没有线程数多(很少存在)
  24. if(len==0){
  25. threadCounts=list.size();//采用一个线程处理List中的一个元素
  26. len=list.size()/threadCounts;//重新平均分割List
  27. }
  28. for(int i=0;i<threadCounts;i++){
  29. final List subList;
  30. if(i==threadCounts-1){
  31. subList=list.subList(i/*len,list.size());
  32. }else{
  33. subList=list.subList(i/len, len/(i+1)>list.size()?list.size():len/*(i+1));
  34. }
  35. //采用匿名内部类实现
  36. callList.add(new Callable(){
  37. public Long call() throws Exception {
  38. long subSum=0L;
  39. for(Integer i:subList){
  40. subSum+=i;
  41. }
  42. System.out.println("分配给线程:"+Thread.currentThread().getName()+"那一部分List的整数和为:\tSubSum:"+subSum);
  43. return subSum;
  44. }
  45. });
  46. }
  47. List> futureList=exec.invokeAll(callList);
  48. for(Future future:futureList){
  49. sum+=future.get();
  50. }
  51. exec.shutdown();
  52. System.out.println(sum);
  53. }
  54. }
    ///

/ 使用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很久没这么疯狂过啦。这不是因为我的算法多好,而是因为这个题目、这篇帖子所体现出的意义。大家在看完这篇帖子后不光指正错误,还对方案进行了改进,关键是思考,人的思维是无穷的,只要我们善于发掘,善于思考,总能想出一些意想不到的方案。 从算法看,或者从题目场景对比代码实现来看,或许不是一篇很好的帖子,但是我说这篇帖子是很有意义的,方案也是在很多场景适用,有时我们可以假设这不是计算和,而是把数据写到一个个的小文件里,或者是分割进行网络传输等等,都有一定的启发,特别是回帖中的讨论。 单说一下回帖,我建议进来的人尽量看完所有的回帖,因为这里是很多人集思广益的精华,这里有他们分析问题,解决问题的思路,还有每个人提到的解决方案,想想为什么能用?为什么不能用?为什么好?为什么不好? 我一直相信:讨论是解决问题、提高水平的最佳方式!

希望本站内容对您有点用处,有什么疑问或建议请在后面留言评论
转载请注明作者(RobinChia)和出处 It so life ,请勿用于任何商业用途