淘宝面试题：如何充分利用多核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)的值。

示意图如下：

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

/**
 * 计算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;
	}
	/**
	 * 获取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不等待的话，那么结果将是不可预料的。

/**
 * 计算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 列表相加就得到总和了。

/**
 * 使用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很久没这么疯狂过啦。这不是因为我的算法多好，而是因为这个题目、这篇帖子所体现出的意义。大家在看完这篇帖子后不光指正错误，还对方案进行了改进，关键是思考，人的思维是无穷的，只要我们善于发掘，善于思考，总能想出一些意想不到的方案。

从算法看，或者从题目场景对比代码实现来看，或许不是一篇很好的帖子，但是我说这篇帖子是很有意义的，方案也是在很多场景适用，有时我们可以假设这不是计算和，而是把数据写到一个个的小文件里，或者是分割进行网络传输等等，都有一定的启发，特别是回帖中的讨论。

单说一下回帖，我建议进来的人尽量看完所有的回帖，因为这里是很多人集思广益的精华，这里有他们分析问题，解决问题的思路，还有每个人提到的解决方案，想想为什么能用?为什么不能用?为什么好?为什么不好?

我一直相信：讨论是解决问题、提高水平的最佳方式！

评论

145 楼 mercyblitz 2010-07-16  

linchao198401 写道

请看看我给的join的例子的链接，看看里面是等谁die。

然后javadoc说的是this thread die。而不是说current thread die.
this是通过对象调用的。
当你调用的是thatThread.join()，那么你等的就是thatThread的die。

已经试过currentThread().join()是不会完成就已经知道自己等自己die是不行的了。

嗯，貌似Thread#currentThread()方法，返回是当前线程，也就是执行Thread#currentThread()语句的方法的线程。

线程有父子关系，你看下Thread#init()方法（被被构造器其调用）。当一个新的线程在start方法调用之前，Thread#currentThread是其父线程，在start方法之中，再调用Thread#currentThread则是其对象本身。

父线程执行完之后，子线程不一定启动。你给的资源中，子线程join之后，该子线程必须等待到die，而这时main方法中，Thread#currentThread()是Main Thread，这个时候调用Thread#currentThread().join()会发生无限期等待。但是，比如在一个方法中，在Thread#currentThread()的join和其他Thread实例start，如果不存在父子关系的话，那么不一定其他Thread实例在调用start方法后也不一定会执行。不知道你是否能够想到这种场景。

总之，Thread对象调用join()方法仅仅让自身等待到die，和其他的线程执行没有关系。

144 楼 linchao198401 2010-07-16  

请看看我给的join的例子的链接，看看里面是等谁die。

然后javadoc说的是this thread die。而不是说current thread die.
this是通过对象调用的。
当你调用的是thatThread.join()，那么你等的就是thatThread的die。

已经试过currentThread().join()是不会完成就已经知道自己等自己die是不行的了。

143 楼 mercyblitz 2010-07-16  

linchao198401 写道

join()方法不应该等待当前的线程，而应该等待其他线程的执行的结束，当然等待的那个线程必须要可以结束的，不能是
http://deepfuture.iteye.com/blog/599684

你的说法不对，如果是等待其他线程执行结束，那么设计API时候，完全可以把join方法设计成静态方法。

Javadoc上面说了：

引用

Waits for this thread to die.

This thread 就是指本Thread实例。

142 楼 linchao198401 2010-07-16  

我尝试了一下。
确实是会导致无限期的等待。
join()方法不应该等待当前的线程，而应该等待其他线程的执行的结束，当然被等待的那个线程必须要可以结束的，不能是while(true)

我也不知道这应该就死锁还是活锁。或者根本就跟锁没有关系。
只是线程的无限期的等待而已。没有任何的同步块或者资源在里面。

跟while(true) {

}
是差不多的。

我用了jvisualvm工具之后发现
Thread.currentThread().join();比while的方式还好一点。
就是Thread.currentThread().join();是线程等待，不会有CPU的时间片的执行。
而while是不断的执行时间片。

join的用法参考搜索到的文章
http://deepfuture.iteye.com/blog/599684

141 楼 mercyblitz 2010-07-16  

kakaluyi 写道

mercyblitz 写道

kakaluyi 写道

skzr.org 写道

使用Gedit编辑的，难免有语法错误，呵呵
我的一个解法：

public class MyWorkThread extends Thread {
	private static BigDecimal sum;
	private List<Integer> list;
	private int start, end;
	private long value;

	public static BigDecimal getSum() {
		return sum;
	}

	public static synchronized void addSum(long v) {
		if (sum == null) {
			sum = new BigDecimal(v);
		} else {
			sum.add(BigDecimal.valueOf(v));
		}
	}

	
	public MyWorkThread(List<Integer> list, Integer start, Integer end) {
		this.list = list;
		this.start = start;
		this.end = end;
	}


	private void add(int v) {
		if (Long.MAX_VALUE - v > value) {
			value += v;
		} else {
			addSum(value);
			value = v;
		}
	}

	public void run() {
		for(int i = start; i < end; i++) add(list.get(i));
	}
	
	public static void main(String[] args) throws InterruptedException {
		List<Integer> list = new ArrayList<Integer>();
		int cpuCoreSize = 2;
		int len = list.size() / cpuCoreSize;
		int start = 0, end = len;
		for (;;) {
			end = start + len;
			if (end > list.size()) end = list.size();
			new MyWorkThread(list, start, end).start();
			start = end;
			if (start == list.size()) break;
		}
		[color=red]Thread.currentThread().join();[/color]		System.out.println("和为：" + MyWorkThread.getSum());
	}
}

52行Thread.currentThread().join();朋友有个地方不懂，这里Thread.currentThread()是主线程吧，那join（）方法就是是主线程等待主线程执行完成，这不是抛出InterruptedException吗

不会，只是会活锁。你可以在main方法里面试试。

经过验证，不是活锁，证明了我的担心，是个死锁

public static void main(String args[])
{
try {
Thread.currentThread().join();
System.out.println("ok");
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
ok永远打印不出来，主线程等待所有子线程结束的方法是不是酱紫地，前面一个同学说了一个方法
atominit方法才是正解

在Java中，死锁应该是指两个线程在同步互斥中，由于释放锁的顺序不当，造成相互等待。而活锁是指，一个线程等待另外一个线程的答复。在这里，Main Thread等待自身（Main Thread）消亡而造成的永久等待，并没有在同步互斥下。因此，我理解为活锁。

140 楼 mercyblitz 2010-07-16  

hardPass 写道

仔细研究了下Thread.currentThread().join();
当前线程等待当前线程结束？

	    while (isAlive()) {
	       wait(0);
	    }

实际上是当前线程等待自己die:因为一直等待，所以无法die；因为没有die，所以还在wait(0)

如果企图在其他线程Notify，会报java.lang.IllegalMonitorStateException，同时，它还在无限制的等待自己die


所以这个代码非常恶劣霸道！

会导致当前线程永久性地睡眠，并且没有任何办法打断。

final Thread mainThread = Thread.currentThread();
		Thread t = new Thread(new Runnable() {
			
			@Override
			public void run() {
				System.out.println("------");
				try {
					Thread.sleep(2000);
				} catch (InterruptedException e) {
					e.printStackTrace();
				}
				System.out.println("------");
				mainThread.notify();
			}
		});
		
		t.start();
		try {
			//t.join();
			//Thread.currentThread().join(1000);
			Thread.currentThread().join();
			System.out.println("++");
		} catch (InterruptedException e) {
			e.printStackTrace();
		}

join和wait是两码事。join不存在线程之间的唤醒，比如Object#notify操作。并且notify和wait操作，必须在Thread的同步下。而join的意义是wait to die。

join还是有办法打断的，在Thread运行时，报出一个异常就可以把当前线程搞死。


比如：

		Thread t =new Thread (new Runnable(){
			public void run(){
				throw new RuntimeException("On purpose!");
			}
		});
		
		t.start();
		
		try {
			t.join();
		} catch (InterruptedException e) {

		}
		System.out.println("+++");

139 楼 xkorey 2010-07-16  

我的思路：有一个处理数值相加的类：smallBasic 每个线程会有单独的smallBasic。
线程类RunnableBasic来处理smallBasic的值。Sumcenter来存放每个线程里smallBasic相加的值。最后把每个线程运行求和的结果相加就是整个集合的值。
  while(!end){
            int m = 0;
            for(int q=0;q<obj.size();q++){
                if(obj.get(q).end.equals("end")){
                    m++;
                }
            }
            if(m == obj.size()){end = true;}
            try {
                Thread.sleep(100);
            } catch (InterruptedException e) {
                e.printStackTrace(); 
            }
        }
这段代码我是想等待所用的线程都运行完、然后在去处理每个线程相加的结果。
也不知道还有没有更合适的判断方法。

代码烂、所以时间才会差好多。

138 楼 mercyblitz 2010-07-16  

hardPass 写道

kakaluyi 写道

mercyblitz 写道

kakaluyi 写道

skzr.org 写道

使用Gedit编辑的，难免有语法错误，呵呵
我的一个解法：

public class MyWorkThread extends Thread {
	private static BigDecimal sum;
	private List<Integer> list;
	private int start, end;
	private long value;

	public static BigDecimal getSum() {
		return sum;
	}

	public static synchronized void addSum(long v) {
		if (sum == null) {
			sum = new BigDecimal(v);
		} else {
			sum.add(BigDecimal.valueOf(v));
		}
	}

	
	public MyWorkThread(List<Integer> list, Integer start, Integer end) {
		this.list = list;
		this.start = start;
		this.end = end;
	}


	private void add(int v) {
		if (Long.MAX_VALUE - v > value) {
			value += v;
		} else {
			addSum(value);
			value = v;
		}
	}

	public void run() {
		for(int i = start; i < end; i++) add(list.get(i));
	}
	
	public static void main(String[] args) throws InterruptedException {
		List<Integer> list = new ArrayList<Integer>();
		int cpuCoreSize = 2;
		int len = list.size() / cpuCoreSize;
		int start = 0, end = len;
		for (;;) {
			end = start + len;
			if (end > list.size()) end = list.size();
			new MyWorkThread(list, start, end).start();
			start = end;
			if (start == list.size()) break;
		}
		[color=red]Thread.currentThread().join();[/color]		System.out.println("和为：" + MyWorkThread.getSum());
	}
}

52行Thread.currentThread().join();朋友有个地方不懂，这里Thread.currentThread()是主线程吧，那join（）方法就是是主线程等待主线程执行完成，这不是抛出InterruptedException吗

不会，只是会活锁。你可以在main方法里面试试。

经过验证，不是活锁，证明了我的担心，是个死锁

public static void main(String args[])
{
try {
Thread.currentThread().join();
System.out.println("ok");
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
ok永远打印不出来，主线程等待所有子线程结束的方法是不是酱紫地，前面一个同学说了一个方法
atominit方法才是正解

Thread.currentThread().join(); 莫非是传说中的永久sleep，必须等待别人来打断？

它并没有Sleep，而是工作完成之后，在等待。它不能被唤起，传说中的永久sleep应该是Thread#sleep(Long.MAX_VALUE)。

137 楼 linchao198401 2010-07-16  

如果能把整个list放入内存里面，当然是ArrayList内部相加快了。

假设有18个CPU在电脑上面，你直接相加能用到几个CPU？
只有用到一个，因为只有一个线程在运行。那么其他17个CPU就浪费了。

如果分成18个线程相加速度会不会快点。

你写了好多的类，看来看去很复杂。
调用这么多的方法，栈的使用也是很消耗资源的。
不知道你创建了多少个线程。线程也是要资源。所以才导致速度慢。

就说这个代码：
        for(int u=0;u<s.get().size();u++){
           sum += s.get().get(u);
        }
Coding style不好
s我也不知道是什么意思。
s.get()我也不知道返回什么，原来是里面的一个ArrayList。用get做方法名还是很难理解，不能换个名字吗？
然后每次进行u<s.get().size()尽管ArrayList的size()可以马上返回数值，但是你为什么不把size()的值拿到循环外面呢？因为那个值是固定的，没有必要每次比较的时候都去调用一次函数。不知道JIT会不会对你的代码进行了优化，因为那个函数已经访问恩多次的。
然后循环的计数用u？大家都用i j k m等等，没有见过有人用u的。
s.get().get(u)这个也是，相信过1个月之后，你自己看代码也不知道到底拿到的是什么东西了。

我在想为什么你没有同步的代码，原来你是不断的轮询。轮询是很费CPU的时间的。而且你这里面也没有Thread.sleep，这个线程会不断的抢其他线程的计算时间。

    while(!end){
            int m = 0;
            for(int q=0;q<obj.size();q++){
                if(obj.get(q).end.equals("end")){
                    m++;
                }
            }
            if(m == obj.size()){end = true;}
        }

计算开多线程，只要内存够多，尽管多线程之间切换需要一些资源和时间，但是也没有15到141的差距的。

136 楼 xkorey 2010-07-16  

经过测试我发现我写的这个实现还不如java ArrayList 直接遍历相加求和快呢。
数据量大了更是如此吧。
import java.util.ArrayList;
import java.util.Random;


public class countBasic {

    public static void main(String[]a){

      int index = 100000;
      ArrayList<Integer> numbers = new ArrayList<Integer>();

      ArrayList<RunnableBasic> obj = new ArrayList<RunnableBasic>();
      System.out.println("开始生成数组"+System.currentTimeMillis());
        for(int i=0;i<1000*100*10;i++){
          Random rd = new Random();
          int t = rd.nextInt();
          numbers.add(t>0?t:0-t);      
         }

        System.out.println("生成完毕"+System.currentTimeMillis());

        ArrayList<Integer> arr = new ArrayList<Integer>();

        for(int j =0;j<numbers.size();j++){

           arr.add(numbers.get(j));

           if((j %  index== 0 && j != 0 )|| (j == numbers.size()-1)){
              
              RunnableBasic rb = new RunnableBasic();

              rb.vt = new smallBasic();

              rb.Numbers = arr;

              obj.add(rb);

              arr = new ArrayList<Integer>();

           }

        }

        ArrayList<Thread> th  = new ArrayList<Thread>();
        System.out.println("分组完毕"+System.currentTimeMillis());
        for(int k = 0 ; k<obj.size();k++){
            new Thread(obj.get(k)).start();
        }
       
        boolean end = false;

        while(!end){
            int m = 0;
            for(int q=0;q<obj.size();q++){
                if(obj.get(q).end.equals("end")){
                    m++;
                }
            }
            if(m == obj.size()){end = true;}
        }

        Sumcenter s = Sumcenter.getInistance();

        int sum = 0;

        for(int u=0;u<s.get().size();u++){
           sum += s.get().get(u);
        }

        System.out.println("和是："+sum);
        System.out.println("计算完毕"+System.currentTimeMillis());
        int au = 0;
        for(int aj =0;aj<numbers.size();aj++){
            // System.out.println(numbers.get(aj));
            au += numbers.get(aj);
        }
        System.out.println("和是："+au);
        System.out.println(System.currentTimeMillis());
    }


}


import java.util.ArrayList;

public class Sumcenter {
   
    public ArrayList<Integer> Brain;

    private static Sumcenter c;
   
    private Sumcenter(){
        Brain = new ArrayList<Integer>();
    }

    public static Sumcenter getInistance(){
       if(c == null)
           c = new Sumcenter();
        return c;
    }

    public void add(int i){
        Brain.add(i);
    }

    public ArrayList<Integer> get(){
        return Brain;
    }
}

public class smallBasic {
   
    private int sum=0;

    public void add(int i){
      this.sum += i; 
    }

    public int getSum(){
        return this.sum;
    }
   
}

public class RunnableBasic implements Runnable {

    protected smallBasic vt;
   
    protected ArrayList<Integer> Numbers;

    protected String end ="";

    public void run() {
        for(int i=0;i<Numbers.size();i++){
           vt.add(Numbers.get(i));
        }
        Sumcenter c = Sumcenter.getInistance();
        c.add(vt.getSum());
        end = "end";
    }
   
}

开始生成数组1279266504921
生成完毕1279266505734
分组完毕1279266505843
和是：-1912057435
计算完毕1279266505875
和是：-1912057435
1279266505890

直接遍历相加所用时间：15
分组遍历多线程在求和所用时间：141
希望大家看看我写的代码哪里出问题了。

135 楼 czxiyj 2010-07-16  

实现原理非常清除，顶！

134 楼 飞雪无情 2010-07-16  

linchao198401 写道

lanxiazhi 写道

看过主贴和评论，学习了。
发现的问题：
(1)CyclicBarrier不适合这种并发任务。单个线程完成任务之后完全可以终止了，没必要全部等待着，这可能是很大的资源浪费。使用CountDownLatch也会有这个问题。
(2)楼主使用了线程同步，考虑到同步的代价，这是可能是个很大的时间浪费。
(3)楼主使用CyclicBarrier的唯一用处在于，保证所有的任务都完成了。但是杀鸡焉用牛刀?这可能是...的浪费

  其实实现这样的功能，可以不用那么复杂，而且可以不用加锁。这里需要一个AtomicInteger(设为atom)。每个线程获得自己的sublist求和任务之后，计算一个和，保存到某个成员变量(设为subsum)中(如某楼上所说)，把那个atom加1，然后结束。
  在主方法中，启动所有线程，然后添加一条语句，等待所有线程完成任务：
while(atom.intValue()<threadCounts)
  Thread.yield();
最后从所有死掉的线程对象中，获取subsum并累加即可。

我比较同意lanxianzhi的说法。
使用CountDownLatch，其他所有的计算线程都在计算，最后输出的线程肯定在等所有的线程算好才行。
更进一步的问题是：如果我想知道目前算好的实时总数是多少，以及目前多少个线程已经算好了，那么使用CountDownLatch是没有办法的。
比如，有10000个计算线程，一个输出线程在wait，输出线程只能等10000个计算线程都计算完，wait才会结束，然后才能输出。只有一次输出。

也许你想在计算的线程里面把目前被同步的sum给实时打印出来，这样每个计算线程计算结束之后就把当时的实时的结果打印出来，那么计算线程就不符合单一责任原则了。

对于目前已经完成多少个任务，再加个线程共享的变量(任务完成计数器)来自增也不好。
就算用上AtomicInteger也是一种负担。

所以我不觉得应该使用CountDownLatch

线程同步synchronized是不需要的，用AtomicInteger会快一些。

CyclicBarrier就更不需要了，我没有写代码测试，但是按照我的理解，如果你开启11个线程，10个线程在计算，1个线程等待输出，只有当所有线程都执行到await()才能继续。
如果你开的线程就上千个，那么且不是上千个线程都在那边等待？

我还是推荐使用ExecutorCompleteionService

1. ExecutorCompleteionService可以随时拿到完成计算的线程的结果，然后在这个基础上继续进行加运算，而且不需要创建一个在线程之间共享的变量，每个线程有自己的结果变量，这个变量最终会作为task的结果之一返回。
2. 可以随时知道完成的计算线程的计数，当然需要ExecutorCompleteionService执行够快才行，如果计算线程执行很快就结束的话，完成的线程数会不准

我没有在机子上试
贴个Java核心技术的例子代码
ExecutorCompleteionService service = new ExecutorCompleteionService(executor);
for(Callable<Integer> task : tasks) {
    service.submit(task);
}
for(int i = 0; i < tasks.size(); i++) {
    count += service.take().get();// 如果有线程返回，马上可以得到结果，如果没有任何线程返回，阻塞等待结果
}
这里不需要sum这个所有的线程都共享的变量。因此也不需要同步或者AtomicInteger。

lanxianzhi说的不错，那段代码却是存在这些问题。在这个场景中CyclicBarrier不合适，他应该用在更灵活的控制中。

TO linchao198401。ExecutorCompleteionService我试了，他的优越之处在于实时性，而invokeAll()方法要等待所有的任务全部完成或者超时时才返回。

133 楼 linchao198401 2010-07-15  

lanxiazhi 写道

看过主贴和评论，学习了。
发现的问题：
(1)CyclicBarrier不适合这种并发任务。单个线程完成任务之后完全可以终止了，没必要全部等待着，这可能是很大的资源浪费。使用CountDownLatch也会有这个问题。
(2)楼主使用了线程同步，考虑到同步的代价，这是可能是个很大的时间浪费。
(3)楼主使用CyclicBarrier的唯一用处在于，保证所有的任务都完成了。但是杀鸡焉用牛刀?这可能是...的浪费

  其实实现这样的功能，可以不用那么复杂，而且可以不用加锁。这里需要一个AtomicInteger(设为atom)。每个线程获得自己的sublist求和任务之后，计算一个和，保存到某个成员变量(设为subsum)中(如某楼上所说)，把那个atom加1，然后结束。
  在主方法中，启动所有线程，然后添加一条语句，等待所有线程完成任务：
while(atom.intValue()<threadCounts)
  Thread.yield();
最后从所有死掉的线程对象中，获取subsum并累加即可。

我比较同意lanxianzhi的说法。
使用CountDownLatch，其他所有的计算线程都在计算，最后输出的线程肯定在等所有的线程算好才行。
更进一步的问题是：如果我想知道目前算好的实时总数是多少，以及目前多少个线程已经算好了，那么使用CountDownLatch是没有办法的。
比如，有10000个计算线程，一个输出线程在wait，输出线程只能等10000个计算线程都计算完，wait才会结束，然后才能输出。只有一次输出。

也许你想在计算的线程里面把目前被同步的sum给实时打印出来，这样每个计算线程计算结束之后就把当时的实时的结果打印出来，那么计算线程就不符合单一责任原则了。

对于目前已经完成多少个任务，再加个线程共享的变量(任务完成计数器)来自增也不好。
就算用上AtomicInteger也是一种负担。

所以我不觉得应该使用CountDownLatch

线程同步synchronized是不需要的，用AtomicInteger会快一些。

CyclicBarrier就更不需要了，我没有写代码测试，但是按照我的理解，如果你开启11个线程，10个线程在计算，1个线程等待输出，只有当所有线程都执行到await()才能继续。
如果你开的线程就上千个，那么且不是上千个线程都在那边等待？

我还是推荐使用ExecutorCompleteionService

1. ExecutorCompleteionService可以随时拿到完成计算的线程的结果，然后在这个基础上继续进行加运算，而且不需要创建一个在线程之间共享的变量，每个线程有自己的结果变量，这个变量最终会作为task的结果之一返回。
2. 可以随时知道完成的计算线程的计数，当然需要ExecutorCompleteionService执行够快才行，如果计算线程执行很快就结束的话，完成的线程数会不准

我没有在机子上试
贴个Java核心技术的例子代码
ExecutorCompleteionService service = new ExecutorCompleteionService(executor);
for(Callable<Integer> task : tasks) {
    service.submit(task);
}
for(int i = 0; i < tasks.size(); i++) {
    count += service.take().get();// 如果有线程返回，马上可以得到结果，如果没有任何线程返回，阻塞等待结果
}
这里不需要sum这个所有的线程都共享的变量。因此也不需要同步或者AtomicInteger。

132 楼 linchao198401 2010-07-15  

使用ExecutorService.invokeAll的缺点是，如果第一个任务需要花很多时间，可能不得不等待
使用这个会一个一个的遍历，如果某个任务还没有完成就会等待

应该使用ExecutorCompleteionService，会直接获取下一个已经完成的task，如果没有任何一个task是完成的话，再等待。

131 楼 cqu903 2010-07-15  

本质上是一个分治思想，google的map/reduce也是这么个意思。但是有个问题，以前我们在实际运用中使用类似的方案时，发现服务器的CPU并不是都在忙碌状态中，也就是说Java的多线程技术并不是一定能够充分利用到服务器的所有CPU资源。具体原因还不得而知，我怀疑是jvm的底层实现造成的。毕竟UNIX系统根本就没有线程的概念。还望有大牛能够解释一下，谢谢

130 楼 飞雪无情 2010-07-15  

hardPass 写道

仔细研究了下Thread.currentThread().join();
当前线程等待当前线程结束？

	    while (isAlive()) {
	       wait(0);
	    }

实际上是当前线程等待自己die:因为一直等待，所以无法die；因为没有die，所以还在wait(0)

如果企图在其他线程Notify，会报java.lang.IllegalMonitorStateException，同时，它还在无限制的等待自己die


所以这个代码非常恶劣霸道！

会导致当前线程永久性地睡眠，并且没有任何办法打断。

final Thread mainThread = Thread.currentThread();
		Thread t = new Thread(new Runnable() {
			
			@Override
			public void run() {
				System.out.println("------");
				try {
					Thread.sleep(2000);
				} catch (InterruptedException e) {
					e.printStackTrace();
				}
				System.out.println("------");
				mainThread.notify();
			}
		});
		
		t.start();
		try {
			//t.join();
			//Thread.currentThread().join(1000);
			Thread.currentThread().join();
			System.out.println("++");
		} catch (InterruptedException e) {
			e.printStackTrace();
		}

嗯。。相互等待，死锁。。

129 楼 ivin 2010-07-15  

lucky16 写道

hrsvici412 写道

学到好多线程的东西，请问 你的分析的图，是用什么工具画的！

好像是office2007or2010 里面有一个好像就叫流程图的东西~

是指的visio吗？画流程图没问题，就是不太好看，没有楼主的那么艳丽

128 楼 abc130314 2010-07-15  

我觉得还可以优化下

    public static BigInteger g(List<Integer> list, int k) throws InterruptedException {
        int size = list.size();
        if (size == 0 || k < 1) {
            throw new RuntimeException();
        }
        k = k <= size ? k : size;
        int a = (size + k - 1) / k;
        Test[] t = new Test[k - 1];
        for (int i = 0; i < t.length; i++) {
            t[i] = new Test(list.subList(a * i, a * i + a));
            t[i].start();
        }
        Test c = new Test(list.subList(a * (k - 1), size));
        c.run();
        BigInteger sum = c.sum;
        for (int i = 0; i < t.length; i++) {
            t[i].join();
            sum = sum.add(t[i].sum);
        }
        return sum;
    }

    private static class Test extends Thread {

        public Test(List<Integer> list) {
            this.list = list;
            sum = BigInteger.ZERO;
            _sum = 0;
        }

        @Override
        public void run() {
            for (Integer i : list) {
                if (i == 0) {
                    continue;
                }
                if (i > 0 ? (_sum + i < _sum) : (_sum + i > _sum)) {
                    sum = sum.add(BigInteger.valueOf(_sum));
                    _sum = 0;
                }
                _sum += i;
            }
            sum = sum.add(BigInteger.valueOf(_sum));
        }
        private List<Integer> list;
        private BigInteger sum;
        private long _sum;
    }

127 楼 hardPass 2010-07-15  

仔细研究了下Thread.currentThread().join();
当前线程等待当前线程结束？

	    while (isAlive()) {
	       wait(0);
	    }

实际上是当前线程等待自己die:因为一直等待，所以无法die；因为没有die，所以还在wait(0)

如果企图在其他线程Notify，会报java.lang.IllegalMonitorStateException，同时，它还在无限制的等待自己die


所以这个代码非常恶劣霸道！

会导致当前线程永久性地睡眠，并且没有任何办法打断。

final Thread mainThread = Thread.currentThread();
		Thread t = new Thread(new Runnable() {
			
			@Override
			public void run() {
				System.out.println("------");
				try {
					Thread.sleep(2000);
				} catch (InterruptedException e) {
					e.printStackTrace();
				}
				System.out.println("------");
				mainThread.notify();
			}
		});
		
		t.start();
		try {
			//t.join();
			//Thread.currentThread().join(1000);
			Thread.currentThread().join();
			System.out.println("++");
		} catch (InterruptedException e) {
			e.printStackTrace();
		}

126 楼 phenom 2010-07-15  

如果只是考CyclicBarrier的使用,那没接触过的人不就不会了.