论坛首页 Java企业应用论坛

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

浏览 94286 次
该帖已经被评为良好帖
作者 正文
   发表时间:2010-08-04  
楼主使用CycliBarrier不当
0 请登录后投票
   发表时间:2010-12-20  
看完回帖 用了2小时!!!
LZ 的解答 应该能混过面试。。
后面的回帖,可以给面试加分
0 请登录后投票
   发表时间:2010-12-21   最后修改:2010-12-21
viei 写道
个人觉的你的这些算法啊,线程操作可能都是白忙活,或者说对这种问题处理的很浅,还不深入。算法挺简单的实现起来也有很多办法,多线程调度什么的也都是基本java知识。
我个人觉的的你要抓住问题的重点,要是用多cpu充分发挥多cpu的优势,首先要把任务分发,你只是起多个线程并不一定操作jvm和操作系统就会把任务分发到多cpu上执行,只有可能时间片切的更小,在执行这些任务。
所以这个过程中考虑的重点应该是
1:操作系统(开多个jvm,规定每个jvm进程运行在指定cpu上,肯定比一个进程下的多个线程只占用一个cpu对多cpu的压榨更好)
2:jvm调整(大数据量必然涉及到垃圾回收)
3:程序编写
上面这些弄好了,再深入一点就考虑,同步消耗问题
cpu多了,同步因素也是决定是否能把多cpu和性能转化率提高出来的一个重要环节。

0 请登录后投票
   发表时间:2010-12-21   最后修改:2010-12-21
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;

0 请登录后投票
   发表时间:2010-12-21   最后修改:2010-12-21
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操作),丧失了实时性。



0 请登录后投票
   发表时间:2010-12-21   最后修改:2010-12-21

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;


public class Sum {
	public static void main(String[] args) throws InterruptedException, ExecutionException {
		List<Integer> testList = new ArrayList<Integer>();
		int min = Integer.parseInt(args[0]);
		int max = Integer.parseInt(args[1]);
		int threadNum = Integer.parseInt(args[2]);
		for (int i=min;i<=max;i++) testList.add(i);
		System.out.println(new Sum().countIntegerList(threadNum, testList));
	}
	
	BigInteger countIntegerList(int threadNum,List<Integer> list) throws InterruptedException, ExecutionException
	{
		BigInteger result= new BigInteger("0");
		ExecutorService es =  Executors.newFixedThreadPool(threadNum);
		List<ListTask> sumList= new ArrayList<ListTask>();
		int totalCount = list.size();
		int threadCount=totalCount/(threadNum-1);
		for (int i=0;i<threadNum;i++)
		{
			if (i == threadNum-1) sumList.add(new ListTask(list,i*threadCount,totalCount-1));
			else sumList.add(new ListTask(list,i*threadCount,(i+1)*threadCount-1));
		}
		List<Future<BigInteger>> resList =  es.invokeAll(sumList);
		for (int i=0;i<resList.size();i++) 
		{
			result  =result.add(resList.get(i).get());
		}
		es.shutdown();
		return result;
	}
	
	class ListTask  implements Callable<BigInteger>
	{
		private volatile List<Integer> list;
		private int start;
		private int end;
		
		public ListTask(List<Integer> list,int start,int end) {
			this.list = list;
			this.start= start;
			this.end = end;
		}

		public BigInteger call() throws Exception {
			BigInteger result = new BigInteger("0");
			for(int i=start;i<=end;i++) result = result.add(new BigInteger(String.valueOf(list.get(i))));
			return result;
		}
		
	}
}

0 请登录后投票
   发表时间:2011-02-25  
LZ 我运行了下你的例子, 没有发现有什么提升。 不知道是不是demo不合适

另外 这个好像只是多线程计算吧?和多核cpu有什么关系???????
0 请登录后投票
   发表时间:2011-03-21  
单核也可以开多线程,怎么证明你开的多线程在多核上运行
0 请登录后投票
   发表时间:2011-03-27  
看完所有帖子和代码,我都也晕了。
0 请登录后投票
   发表时间:2011-03-28  
我晕。。。我自己写的代码和你给的那个Callable代码运算结果不一样。。。
0 请登录后投票
论坛首页 Java企业应用版

跳转论坛:
Global site tag (gtag.js) - Google Analytics