`

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

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

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

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

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

  • 大小: 95.8 KB
分享到：
| 漫画：客户真正的需求是这样的
评论
85 楼 kakaluyi 2010-07-13  
quote="david.org"]
kakaluyi 写道

   因为比如说list有100个整数对象，平均一次加运算耗费1秒吧（夸张点）。你分成10个线程去计算，每个线程运行10秒钟计算完自己的线程（自己计算的同时cpu时间片是不可能分给其他线程的）那么10个线程需要100秒，一个线程100次相加运算，因为是从内存读出数据，我们可以忽略等待时间，那么也是100秒，但是扣除你新建线程的消耗和最后等待所有线程运行完才能最后求整的时间，其实多线程是比单线程还慢的。
   如果该问题是从10000个文件（更比如说是webservice从别的异构系统读出整数）读出数字相加，我肯定会用lz的方法，因为读取文件需要io时间，这些线程等待的时候，其他线程还可以进行运算，不会像单线程阻塞住，这时候才是多线程应用的场景，个人看法，欢迎拍砖

> 但是扣除你新建线程的消耗和最后等待所有线程运行完才能最后求整的时间，其实多线程是比单线程还慢的
弱问一下, 这句是说多线程其实比单线程还慢的原因吗？
是说lz这个场景下单线程实现不会比多线程实现快的原因，这种场景我觉得用单线程足以.

> 自己计算的同时cpu时间片是不可能分给其他线程的
对于多核CPU，这句怎么解释？
确实多核的cpu要多线程才能发挥优势

> 但是扣除你新建线程的消耗和最后等待所有线程运行完才能最后求整的时间
闭锁(Latch)让控制线程能够等待最后一个线程完成任务, 而不是顺序等待每一个线程结束。
闭锁等待最后一个线程完成任务的实现也需要消耗资源，可能我没有说明白，需要专门去判断所有线程已经结束
wujiazhao88 写道
多线程的时间都浪费在启动线程上面了。做多了很多无用功，当然海量数据还是有用的。10亿以下的就算了


有道理, 创建线程确实是一个很大的开销, 但在海量计算时, 是有优势的. 多少以下, 需按情况来定嗯.

84 楼 david.org 2010-07-13  
kakaluyi 写道

   因为比如说list有100个整数对象，平均一次加运算耗费1秒吧（夸张点）。你分成10个线程去计算，每个线程运行10秒钟计算完自己的线程（自己计算的同时cpu时间片是不可能分给其他线程的）那么10个线程需要100秒，一个线程100次相加运算，因为是从内存读出数据，我们可以忽略等待时间，那么也是100秒，但是扣除你新建线程的消耗和最后等待所有线程运行完才能最后求整的时间，其实多线程是比单线程还慢的。
   如果该问题是从10000个文件（更比如说是webservice从别的异构系统读出整数）读出数字相加，我肯定会用lz的方法，因为读取文件需要io时间，这些线程等待的时候，其他线程还可以进行运算，不会像单线程阻塞住，这时候才是多线程应用的场景，个人看法，欢迎拍砖


> 但是扣除你新建线程的消耗和最后等待所有线程运行完才能最后求整的时间，其实多线程是比单线程还慢的
弱问一下, 这句是说多线程其实比单线程还慢的原因吗？

> 自己计算的同时cpu时间片是不可能分给其他线程的
对于多核CPU，这句怎么解释？

> 但是扣除你新建线程的消耗和最后等待所有线程运行完才能最后求整的时间
闭锁(Latch)让控制线程能够等待最后一个线程完成任务, 而不是顺序等待每一个线程结束。


wujiazhao88 写道
多线程的时间都浪费在启动线程上面了。做多了很多无用功，当然海量数据还是有用的。10亿以下的就算了


有道理, 创建线程确实是一个很大的开销, 但在海量计算时, 是有优势的. 多少以下, 需按情况来定嗯.
83 楼 wujiazhao88 2010-07-13  
多线程的时间都浪费在启动线程上面了。做多了很多无用功，当然海量数据还是有用的。10亿以下的就算了
82 楼 kakaluyi 2010-07-13  
dilantaya 写道
melody3 写道
kakaluyi 写道
amigo 写道
dilantaya 写道
sunwenran 写道
赞一个。

问题是我用你的例子比较直接加
        long noCurrentSum=0L;  
        for(Integer i:list){  
            noCurrentSum+=i;  
        } 
发现时间差不多。而且有时候直接加更快。纠结了。。我的是双核。


可能是你给的数据量还不够大


调整到50000000
for (int i = 1; i <= 50000000; i++) {
list.add(i);
}


单线程时间比并发更快

呵呵其实这种纯粹的算术相加速度单线程和多线程是一样的（因为没有io读写，没有网络等待等等，），新建线程还要消耗资源，如何设计利用多核cpu就涉及到jvm的底层实现了，所以要我回答这个问题，我给出下面答案：
int sum=0;
for(int i=0;i<list.size();i++)
{
sum+=list.get(i);
}
return sum;


这个就是常规的求值啊


同问

   因为比如说list有100个整数对象，平均一次加运算耗费1秒吧（夸张点）。你分成10个线程去计算，每个线程运行10秒钟计算完自己的线程（自己计算的同时cpu时间片是不可能分给其他线程的）那么10个线程需要100秒，一个线程100次相加运算，因为是从内存读出数据，我们可以忽略等待时间，那么也是100秒，但是扣除你新建线程的消耗和最后等待所有线程运行完才能最后求整的时间，其实多线程是比单线程还慢的。
   如果该问题是从10000个文件（更比如说是webservice从别的异构系统读出整数）读出数字相加，我肯定会用lz的方法，因为读取文件需要io时间，这些线程等待的时候，其他线程还可以进行运算，不会像单线程阻塞住，这时候才是多线程应用的场景，个人看法，欢迎拍砖
81 楼 mercyblitz 2010-07-13  
飞雪无情 写道
mercyblitz 写道
pengpeng99bill 写道
这还是 多线程的问题 啊 还是没有解决多CPU处理的问，你的多线程怎么能保证是多个CPU在处理呢 ，可能还是一个CPU在处理啊 。以前看到过报道好像说是 java7 支持多CPU处理任务。 等待中。。。



可能，你误会了。Java 1.2之后，使用的操作系统内核线程，操作系统还是会利用多CPU的，也就是说和Java无关了。
我的《Java内存模型》正在写，其中起到了这些东西，如果有需要的话，可以关注一下。


回帖里有好多说多CPU的，我不清楚说的是多个CPU，还是一个CPU多个核理解成多CPU了，我的题目是多核CPU，是一个CPU多个核，不知道是不是你们所理解的多CPU。

就像上面说的，操作系统内核线程由操作系统负责调配的，会充分的利用多核，CPU自己也会控制。


多个CPU是指那个主板能够插入多个CPU，比如刀片机。
多核CPU是指一个CPU上面有多个处理器，比如PC机。

无论哪种结构，都属于单独的处理器，并发计算的。
80 楼 david.org 2010-07-13  
mercyblitz 写道
viei 写道
个人觉的你的这些算法啊，线程操作可能都是白忙活，或者说对这种问题处理的很浅，还不深入。算法挺简单的实现起来也有很多办法，多线程调度什么的也都是基本java知识。
我个人觉的的你要抓住问题的重点，要是用多cpu充分发挥多cpu的优势，首先要把任务分发，你只是起多个线程并不一定操作jvm和操作系统就会把任务分发到多cpu上执行，只有可能时间片切的更小，在执行这些任务。
所以这个过程中考虑的重点应该是
1：操作系统（开多个jvm，规定每个jvm进程运行在指定cpu上，肯定比一个进程下的多个线程只占用一个cpu对多cpu的压榨更好）
2：jvm调整（大数据量必然涉及到垃圾回收）
3：程序编写
上面这些弄好了，再深入一点就考虑，同步消耗问题
cpu多了，同步因素也是决定是否能把多cpu和性能转化率提高出来的一个重要环节。


你的说法容易误人子弟。

Java1.2之后，Java多线程依赖于操作系统的内核线程调度。操作系统会不会发挥多处理的优势呢？肯定会啊，操作系统作为基础设施，实时性是它最重视之一。
针对于你的观点，我进行反驳：
1.在进程之间，多个JVM的Heap不能相互共享。更谈不上制定那个CPU制定JVM进行，要知道主存是共享的，CPU的处理数据的。多核CPU不是多台机器，那个CPU负责，是由OS调度，用户进程没有办法控制内核进程。

2.List#sublist方法实现，当大List分离出多个小List，小List并没有放弃大的List，而是还是引用的大List。在计算之中，不会被GC掉。之后被GC掉，对计算没有影响。调整JVM需要是对的，但是调整是Java Heap的大小，而不是为了GC。如果要说GC的话，计算中虽然不会被GC，但是GC会停顿（Pause/Stop World操作），丧失了实时性。




两位说的都很有道理。
viei同学的观点是偏向于大规模数据, 高性能并行处理的需求. 可能用在这个算法题上不是太适合, 但关于JVM的调整确实是高性能程序需要注意的.

mercyblitz同学说的也很有道理, 可能viei的意思是把任务分割, 这个任务是通过独力于另外进程，或节点来提交的。之间可能会通过消息机制的方式来建立的.
79 楼 飞雪无情 2010-07-13  
david.org 写道
viei 写道
dilantaya 写道
viei 写道
个人觉的你的这些算法啊，线程操作可能都是白忙活，或者说对这种问题处理的很浅，还不深入。算法挺简单的实现起来也有很多办法，多线程调度什么的也都是基本java知识。
我个人觉的的你要抓住问题的重点，要是用多cpu充分发挥多cpu的优势，首先要把任务分发，你只是起多个线程并不一定操作jvm和操作系统就会把任务分发到多cpu上执行，只有可能时间片切的更小，在执行这些任务。
所以这个过程中考虑的重点应该是
1：操作系统（开多个jvm，规定每个jvm进程运行在指定cpu上，肯定比一个进程下的多个线程只占用一个cpu对多cpu的压榨更好）
2：jvm调整（大数据量必然涉及到垃圾回收）
3：程序编写
上面这些弄好了，再深入一点就考虑，同步消耗问题
cpu多了，同步因素也是决定是否能把多cpu和性能转化率提高出来的一个重要环节。




怎么指定一个jvm对应单个cpu ,高手？



在linux下你看一下cpuinfo获取cpu信息，编号
然后启动的时候和运行的时候都可以通过taskset命令进行cpu绑定
如果开多进程处理，那么进程间数据如何共享，这个还要重新考虑
你现在的程序都是单进程下的


Hey, All:

首先viei同学的回答很深入, 我想这完全是按照大规模数据并行处理的理念来回答的. 正如上面有同学也提到 Map/Reduce的思想, 是的, 上面程序是单进程独力在一台机子上运行. (但对于这样的面试题目，个人觉得足矣.

其次, 只想补充一点, 大伙都在关注算法的优化, 但忽略了一点, 就是任务的控制. 这实际上在Concurrent中是很重要的一点. 原因是, java中我们不可能去控制时间片, 以及比线程更小级别的单元.  上述代码中, 按楼主最开始的实现, 确实有可能存在CPU切片分配不均的情况.

俺觉得需要两个闭锁, 一个“开始阀门”, 另一个是“结束阀门”.
原因是如果我们简单地创建并启动线程, 那么先启动的就比后启动的具有“领先优势”, 并且根据活动线程数量增加减少, 竞争度也在不断改变. 所以使用“开始阀门”让控制线程能够同时释放所有工作者线程.


同意。前面我也说了，这就是很深入的东西了，起码我的机器实现不了。再深入也可以从用分布式，不过这就不是我所能说的啦。。呵呵。。
78 楼 dilantaya 2010-07-13  
mercyblitz 写道
viei 写道
个人觉的你的这些算法啊，线程操作可能都是白忙活，或者说对这种问题处理的很浅，还不深入。算法挺简单的实现起来也有很多办法，多线程调度什么的也都是基本java知识。
我个人觉的的你要抓住问题的重点，要是用多cpu充分发挥多cpu的优势，首先要把任务分发，你只是起多个线程并不一定操作jvm和操作系统就会把任务分发到多cpu上执行，只有可能时间片切的更小，在执行这些任务。
所以这个过程中考虑的重点应该是
1：操作系统（开多个jvm，规定每个jvm进程运行在指定cpu上，肯定比一个进程下的多个线程只占用一个cpu对多cpu的压榨更好）
2：jvm调整（大数据量必然涉及到垃圾回收）
3：程序编写
上面这些弄好了，再深入一点就考虑，同步消耗问题
cpu多了，同步因素也是决定是否能把多cpu和性能转化率提高出来的一个重要环节。


你的说法容易误人子弟。

Java1.2之后，Java多线程依赖于操作系统的内核线程调度。操作系统会不会发挥多处理的优势呢？肯定会啊，操作系统作为基础设施，实时性是它最重视之一。
针对于你的观点，我进行反驳：
1.在进程之间，多个JVM的Heap不能相互共享。更谈不上制定那个CPU制定JVM进行，要知道主存是共享的，CPU的处理数据的。多核CPU不是多台机器，那个CPU负责，是由OS调度，用户进程没有办法控制内核进程。

2.List#sublist方法实现，当大List分离出多个小List，小List并没有放弃大的List，而是还是引用的大List。在计算之中，不会被GC掉。之后被GC掉，对计算没有影响。调整JVM需要是对的，但是调整是Java Heap的大小，而不是为了GC。如果要说GC的话，计算中虽然不会被GC，但是GC会停顿（Pause/Stop World操作），丧失了实时性。




那这个程序跑在windows和linux上会因为操作系统内核的调度不同，执行效率也不同了？
77 楼 dilantaya 2010-07-13  
melody3 写道
kakaluyi 写道
amigo 写道
dilantaya 写道
sunwenran 写道
赞一个。

问题是我用你的例子比较直接加
        long noCurrentSum=0L;  
        for(Integer i:list){  
            noCurrentSum+=i;  
        } 
发现时间差不多。而且有时候直接加更快。纠结了。。我的是双核。


可能是你给的数据量还不够大


调整到50000000
for (int i = 1; i <= 50000000; i++) {
list.add(i);
}


单线程时间比并发更快

呵呵其实这种纯粹的算术相加速度单线程和多线程是一样的（因为没有io读写，没有网络等待等等，），新建线程还要消耗资源，如何设计利用多核cpu就涉及到jvm的底层实现了，所以要我回答这个问题，我给出下面答案：
int sum=0;
for(int i=0;i<list.size();i++)
{
sum+=list.get(i);
}
return sum;


这个就是常规的求值啊


同问
76 楼 mercyblitz 2010-07-13  
viei 写道
个人觉的你的这些算法啊，线程操作可能都是白忙活，或者说对这种问题处理的很浅，还不深入。算法挺简单的实现起来也有很多办法，多线程调度什么的也都是基本java知识。
我个人觉的的你要抓住问题的重点，要是用多cpu充分发挥多cpu的优势，首先要把任务分发，你只是起多个线程并不一定操作jvm和操作系统就会把任务分发到多cpu上执行，只有可能时间片切的更小，在执行这些任务。
所以这个过程中考虑的重点应该是
1：操作系统（开多个jvm，规定每个jvm进程运行在指定cpu上，肯定比一个进程下的多个线程只占用一个cpu对多cpu的压榨更好）
2：jvm调整（大数据量必然涉及到垃圾回收）
3：程序编写
上面这些弄好了，再深入一点就考虑，同步消耗问题
cpu多了，同步因素也是决定是否能把多cpu和性能转化率提高出来的一个重要环节。


你的说法容易误人子弟。

Java1.2之后，Java多线程依赖于操作系统的内核线程调度。操作系统会不会发挥多处理的优势呢？肯定会啊，操作系统作为基础设施，实时性是它最重视之一。
针对于你的观点，我进行反驳：
1.在进程之间，多个JVM的Heap不能相互共享。更谈不上制定那个CPU制定JVM进行，要知道主存是共享的，CPU的处理数据的。多核CPU不是多台机器，那个CPU负责，是由OS调度，用户进程没有办法控制内核进程。

2.List#sublist方法实现，当大List分离出多个小List，小List并没有放弃大的List，而是还是引用的大List。在计算之中，不会被GC掉。之后被GC掉，对计算没有影响。调整JVM需要是对的，但是调整是Java Heap的大小，而不是为了GC。如果要说GC的话，计算中虽然不会被GC，但是GC会停顿（Pause/Stop World操作），丧失了实时性。


75 楼 melody3 2010-07-13  
kakaluyi 写道
amigo 写道
dilantaya 写道
sunwenran 写道
赞一个。

问题是我用你的例子比较直接加
        long noCurrentSum=0L;  
        for(Integer i:list){  
            noCurrentSum+=i;  
        } 
发现时间差不多。而且有时候直接加更快。纠结了。。我的是双核。


可能是你给的数据量还不够大


调整到50000000
for (int i = 1; i <= 50000000; i++) {
list.add(i);
}


单线程时间比并发更快

呵呵其实这种纯粹的算术相加速度单线程和多线程是一样的（因为没有io读写，没有网络等待等等，），新建线程还要消耗资源，如何设计利用多核cpu就涉及到jvm的底层实现了，所以要我回答这个问题，我给出下面答案：
int sum=0;
for(int i=0;i<list.size();i++)
{
sum+=list.get(i);
}
return sum;


这个就是常规的求值啊
74 楼 david.org 2010-07-13  
viei 写道
dilantaya 写道
viei 写道
个人觉的你的这些算法啊，线程操作可能都是白忙活，或者说对这种问题处理的很浅，还不深入。算法挺简单的实现起来也有很多办法，多线程调度什么的也都是基本java知识。
我个人觉的的你要抓住问题的重点，要是用多cpu充分发挥多cpu的优势，首先要把任务分发，你只是起多个线程并不一定操作jvm和操作系统就会把任务分发到多cpu上执行，只有可能时间片切的更小，在执行这些任务。
所以这个过程中考虑的重点应该是
1：操作系统（开多个jvm，规定每个jvm进程运行在指定cpu上，肯定比一个进程下的多个线程只占用一个cpu对多cpu的压榨更好）
2：jvm调整（大数据量必然涉及到垃圾回收）
3：程序编写
上面这些弄好了，再深入一点就考虑，同步消耗问题
cpu多了，同步因素也是决定是否能把多cpu和性能转化率提高出来的一个重要环节。




怎么指定一个jvm对应单个cpu ,高手？



在linux下你看一下cpuinfo获取cpu信息，编号
然后启动的时候和运行的时候都可以通过taskset命令进行cpu绑定
如果开多进程处理，那么进程间数据如何共享，这个还要重新考虑
你现在的程序都是单进程下的


Hey, All:

首先viei同学的回答很深入, 我想这完全是按照大规模数据并行处理的理念来回答的. 正如上面有同学也提到 Map/Reduce的思想, 是的, 上面程序是单进程独力在一台机子上运行. (但对于这样的面试题目，个人觉得足矣.

其次, 只想补充一点, 大伙都在关注算法的优化, 但忽略了一点, 就是任务的控制. 这实际上在Concurrent中是很重要的一点. 原因是, java中我们不可能去控制时间片, 以及比线程更小级别的单元.  上述代码中, 按楼主最开始的实现, 确实有可能存在CPU切片分配不均的情况.

俺觉得需要两个闭锁, 一个“开始阀门”, 另一个是“结束阀门”.
原因是如果我们简单地创建并启动线程, 那么先启动的就比后启动的具有“领先优势”, 并且根据活动线程数量增加减少, 竞争度也在不断改变. 所以使用“开始阀门”让控制线程能够同时释放所有工作者线程.

73 楼 hardPass 2010-07-13  
beneo 写道
hardPass 写道
package com.wl.test.concurrent.semaphore;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicLong;

/**
*
* 乍一看到题目“充分利用多核CPU”，
* 以为会根据CPU的核心数，计算出比较合理的任务线程的数目。
* 就题目的计算目标来说，实际上讲的主线程等待任务线程完成，
* 任务线程之间没有必要互相等待。
* 是不是可以考虑用信号来......
* 每次来看帖，都发现大家图画的很拉风……
*
* 我也帖个代码，虽然来晚了，大家不一定能看到……
*
* @author HardPass
......


java不是有Semaphore，为啥你非要自己写个lock


1、我的SemaphoreLock比较简单，从原理上大家一看就明白，我们注重讨论原理吗
2、咱SemaphoreLock和java.util.concurrent下的还是有点区别的
3、我不太会用那个Semaphore
72 楼 beneo 2010-07-13  
搞个map-reduce就好了
71 楼 飞雪无情 2010-07-13  
mercyblitz 写道
pengpeng99bill 写道
这还是 多线程的问题 啊 还是没有解决多CPU处理的问，你的多线程怎么能保证是多个CPU在处理呢 ，可能还是一个CPU在处理啊 。以前看到过报道好像说是 java7 支持多CPU处理任务。 等待中。。。



可能，你误会了。Java 1.2之后，使用的操作系统内核线程，操作系统还是会利用多CPU的，也就是说和Java无关了。
我的《Java内存模型》正在写，其中起到了这些东西，如果有需要的话，可以关注一下。


回帖里有好多说多CPU的，我不清楚说的是多个CPU，还是一个CPU多个核理解成多CPU了，我的题目是多核CPU，是一个CPU多个核，不知道是不是你们所理解的多CPU。

就像上面说的，操作系统内核线程由操作系统负责调配的，会充分的利用多核，CPU自己也会控制。
70 楼 kakaluyi 2010-07-13  
amigo 写道
dilantaya 写道
sunwenran 写道
赞一个。

问题是我用你的例子比较直接加
        long noCurrentSum=0L;  
        for(Integer i:list){  
            noCurrentSum+=i;  
        } 
发现时间差不多。而且有时候直接加更快。纠结了。。我的是双核。


可能是你给的数据量还不够大


调整到50000000
for (int i = 1; i <= 50000000; i++) {
list.add(i);
}


单线程时间比并发更快

呵呵其实这种纯粹的算术相加速度单线程和多线程是一样的（因为没有io读写，没有网络等待等等，），新建线程还要消耗资源，如何设计利用多核cpu就涉及到jvm的底层实现了，所以要我回答这个问题，我给出下面答案：
int sum=0;
for(int i=0;i<list.size();i++)
{
sum+=list.get(i);
}
return sum;
69 楼 beneo 2010-07-13  
hardPass 写道
package com.wl.test.concurrent.semaphore;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicLong;

/**
*
* 乍一看到题目“充分利用多核CPU”，
* 以为会根据CPU的核心数，计算出比较合理的任务线程的数目。
* 就题目的计算目标来说，实际上讲的主线程等待任务线程完成，
* 任务线程之间没有必要互相等待。
* 是不是可以考虑用信号来......
* 每次来看帖，都发现大家图画的很拉风……
*
* 我也帖个代码，虽然来晚了，大家不一定能看到……
*
* @author HardPass
*
*/
public class BigListSumWithSemaphore {
private List<Integer> list = new ArrayList<Integer>();

private AtomicLong sum = new AtomicLong(0L); // 结果
private int threadCounts = 2 * Runtime.getRuntime().availableProcessors() + 1; // 任务线程数
private List<Runnable> tasks = new ArrayList<Runnable>(); // 任务线程

SemaphoreLock lock = new SemaphoreLock();



public static void main(String[] args) {
new BigListSumWithSemaphore().test();
}

public void test() {
init();
ExecutorService exec = Executors.newFixedThreadPool(threadCounts); //线程池
for(Runnable task : tasks){
exec.execute(task);
}
lock.lockHere();
exec.shutdown();
System.out.println("List中所有整数的和为:" + sum);
}

private void init() {
for (int i = 1; i <= 1000000; i++) {
list.add(i);
}
int len = list.size() / threadCounts;

int i = 0;
for (; i < threadCounts - 1; i++) {
tasks.add(new Task(list.subList(i * len, (i + 1) * len)));
}
tasks.add(new Task(list.subList(i * len, list.size())));
}

private class Task implements Runnable {
private List<Integer> subList;

public Task(List<Integer> subList) {
this.subList = subList;
}

@Override
public void run() {
lock.lockThere();
long subSum = 0L;
for (Integer i : subList) {
subSum += i;
}
sum.addAndGet(subSum);
System.out.println("分配给线程：" + Thread.currentThread().getName()
+ "那一部分List的整数和为：\tSubSum:" + subSum);
lock.release();
}
}

}

/**
*
* 信号量锁
*
* 此Semaphore非java.util.concurrent.Semaphore
*
* @author HardPass
*
*/
class SemaphoreLock {
private int count = 0; // 信号量
/**
* 信号量大于0的时候 wait
* 这是不是传说中的可重入？
*/
public synchronized void lockHere() {
while (count > 0) {
try {
wait();
} catch (InterruptedException e) {
}
}
}

public synchronized void lockThere() {
count++;
}

public synchronized void release() {
count--;
if(count==0){
notify();
}
}
}


java不是有Semaphore，为啥你非要自己写个lock
68 楼 hardPass 2010-07-13   
package com.wl.test.concurrent.semaphore;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicLong;

/**
 * 
 * 有一个很大的整数list，需要求这个list中所有整数的和，写一个可以充分利用多核CPU的代码，来计算结果。
 * 
 * 
 * 乍一看到题目“充分利用多核CPU”，
 * 以为会根据CPU的核心数，计算出比较合理的任务线程的数目。
 * 就题目的计算目标来说，实际上讲的主线程等待任务线程完成，
 * 任务线程之间没有必要互相等待。
 * 是不是可以考虑用信号来......
 * 每次来看帖，都发现大家图画的很拉风……
 * 
 * 我也帖个代码，虽然来晚了，大家不一定能看到……
 * 
 * @author HardPass
 *
 */
public class BigListSumWithSemaphore {
	private List<Integer> list = new ArrayList<Integer>();

	private AtomicLong sum = new AtomicLong(0L); // 结果
	private int threadCounts = 2 * Runtime.getRuntime().availableProcessors() + 1; // 任务线程数
	private List<Runnable> tasks = new ArrayList<Runnable>(); // 任务线程
	
	SemaphoreLock lock = new SemaphoreLock();
	


	public static void main(String[] args) {
		new BigListSumWithSemaphore().test();
	}

	public void test() {
		init();
		ExecutorService exec = Executors.newFixedThreadPool(threadCounts); //线程池
		for(Runnable task : tasks){
			exec.execute(task);
		}
		lock.lockHere(); // 此处尝试wait
		exec.shutdown();
		System.out.println("List中所有整数的和为:" + sum);
	}

	private void init() {
		for (int i = 1; i <= 1000000; i++) {
			list.add(i);
		}
		int len = list.size() / threadCounts;

		int i = 0;
		for (; i < threadCounts - 1; i++) {
			tasks.add(new Task(list.subList(i * len, (i + 1) * len)));
		}
		tasks.add(new Task(list.subList(i * len, list.size())));
	}

	private class Task implements Runnable {
		private List<Integer> subList;

		public Task(List<Integer> subList) {
			this.subList = subList;
		}

		@Override
		public void run() {
			lock.lockThere();  // 增加锁的计数
			long subSum = 0L;
			for (Integer i : subList) {
				subSum += i;
			}
			sum.addAndGet(subSum);
			System.out.println("分配给线程：" + Thread.currentThread().getName()
					+ "那一部分List的整数和为：\tSubSum:" + subSum);
			lock.release(); // 释放一个锁的计数
		}
	}

}

/**
 * 
 * 信号量锁
 * 
 * 此Semaphore非java.util.concurrent.Semaphore
 * 
 * @author HardPass
 *
 */
class SemaphoreLock {
	private int count = 0; // 信号量
	/**
	 * 信号量大于0的时候 wait
	 * 这是不是传说中的可重入？
	 */
	public synchronized void lockHere() {
		while (count > 0) {
			try {
				wait();
			} catch (InterruptedException e) {
			}
		}
	}

	public synchronized void lockThere() {
		count++;
	}

	public synchronized void release() {
		count--;
		if(count==0){
			notify();
		}
	}
}
67 楼 viei 2010-07-13  
dilantaya 写道
viei 写道
个人觉的你的这些算法啊，线程操作可能都是白忙活，或者说对这种问题处理的很浅，还不深入。算法挺简单的实现起来也有很多办法，多线程调度什么的也都是基本java知识。
我个人觉的的你要抓住问题的重点，要是用多cpu充分发挥多cpu的优势，首先要把任务分发，你只是起多个线程并不一定操作jvm和操作系统就会把任务分发到多cpu上执行，只有可能时间片切的更小，在执行这些任务。
所以这个过程中考虑的重点应该是
1：操作系统（开多个jvm，规定每个jvm进程运行在指定cpu上，肯定比一个进程下的多个线程只占用一个cpu对多cpu的压榨更好）
2：jvm调整（大数据量必然涉及到垃圾回收）
3：程序编写
上面这些弄好了，再深入一点就考虑，同步消耗问题
cpu多了，同步因素也是决定是否能把多cpu和性能转化率提高出来的一个重要环节。




怎么指定一个jvm对应单个cpu ,高手？



在linux下你看一下cpuinfo获取cpu信息，编号
然后启动的时候和运行的时候都可以通过taskset命令进行cpu绑定
如果开多进程处理，那么进程间数据如何共享，这个还要重新考虑
你现在的程序都是单进程下的
66 楼 beneo 2010-07-13  
如果我做的话，这就是一个分治合并的思想在里面。

分多少完全看你线程数目

一般来说我们完全可以开2N + 1个线程来做运算

你可以使用CountDownLatch，信号量，或者你提到的栅栏都可以。

有个漏斗理论不知道你看过没有，合并的任务就好像漏斗一样。。
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    若邻网Python工程师面试题

    2. **丰富的库支持**：Python 拥有庞大的标准库和第三方库，几乎涵盖了所有应用领域，如网络编程、图形用户界面、科学计算等。 3. **跨平台性**：Python 可以运行在多种操作系统上，如 Windows、Linux 和 macOS 等。...

    delphi面试题.pdf

    ### Delphi 面试题知识点解析 #### 一、基础知识题解析 1. **Delphi 是什么？它主要应用于什么领域？** - **Delphi** 是一种基于 Object Pascal 的集成开发环境（IDE），主要用于 Windows 平台上的应用程序开发。...

    110道python面试题

    - **作用**: 由于GIL的存在，在多线程环境下，即使CPU有多核也无法充分利用多核的优势，因为同一进程中只有一个线程可以执行Python字节码。 - **影响**: 对于I/O密集型的应用，GIL的影响较小，但对于CPU密集型任务...

    python面试题及答案.txt

    根据给定文件的信息，我们可以总结出一系列与Python相关的面试题及其答案。这些问题涵盖了Python的基本语法、数据类型、高级特性等多个方面。接下来，我们将详细解析这些知识点。 ### 模块和包的区别 在Python中，...

    Python面试常见问题汇总集锦（含爬虫工程师面试考点）

    Python也提供了多线程和多进程支持，以便更好地利用多核处理器。 6. 全局解释器锁（GIL） Python中的全局解释器锁（GIL）是为了简化内存管理而设计的，它限制了同一时刻只有一个线程可以执行Python字节码。这意味着...

    搞定这套Python爬虫面试题(面试会so easy)

    - 利用多进程可以充分利用多核CPU资源。 7. **深拷贝与浅拷贝** - 深拷贝创建一个全新的对象，而浅拷贝仅复制对象的引用。 - 当原对象被修改时，深拷贝的对象不受影响，而浅拷贝的对象可能会受到影响。 8. **is...

    python面试题

    ### Python面试题详解 #### 1. Python的函数参数传递 在Python中，函数参数的传递遵循“传值”而非“传引用”的原则。当传递不可变数据类型（如整数、字符串等）时，实际上是将该数据类型的值复制一份传递给函数；...

    java面试讲题汇总-word可打印版

    51. Java 8的ConcurrentHashMap弃用分段锁是因为分段锁在多核CPU环境下性能瓶颈，改为使用CAS和Node链表实现。 52. ConcurrentHashMap使用synchronized而非ReentrantLock是因为减少锁粒度，提高并发性能。 53. ...

    Redis面试必会的题目

    通过在同一台机器上启动多个Redis实例，可以充分利用多核资源。 3. **Redis的性能优势**： - **速度**：由于数据存储在内存中，Redis的读写速度非常快，接近O(1)的时间复杂度。 - **丰富的数据类型**：支持多种...

    Python面试题

    这限制了多核CPU下的并行计算能力，但在IO密集型任务中，多线程仍然能提高效率。 - 使用`threading`库可以创建线程，但需要注意GIL的存在可能导致多线程不如预期中的并行。 以上是Python面试中常见的知识点，理解...

Magicbox
Global site tag (gtag.js) - Google Analytics