`

淘宝面试题：如何充分利用多核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
分享到：
| 漫画：客户真正的需求是这样的
评论
165 楼 kanny87929 2011-03-27  
看完所有帖子和代码，我都也晕了。
164 楼 wengyanjiaji 2011-03-21  
单核也可以开多线程，怎么证明你开的多线程在多核上运行
163 楼 ak121077313 2011-02-25  
LZ 我运行了下你的例子， 没有发现有什么提升。 不知道是不是demo不合适

另外 这个好像只是多线程计算吧？和多核cpu有什么关系？？？？？？？
162 楼 bushuang1983 2010-12-21  
<p>
</p>
<pre name="code" class="java">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&lt;Integer&gt; testList = new ArrayList&lt;Integer&gt;();
int min = Integer.parseInt(args[0]);
int max = Integer.parseInt(args[1]);
int threadNum = Integer.parseInt(args[2]);
for (int i=min;i&lt;=max;i++) testList.add(i);
System.out.println(new Sum().countIntegerList(threadNum, testList));
}

BigInteger countIntegerList(int threadNum,List&lt;Integer&gt; list) throws InterruptedException, ExecutionException
{
BigInteger result= new BigInteger("0");
ExecutorService es =  Executors.newFixedThreadPool(threadNum);
List&lt;ListTask&gt; sumList= new ArrayList&lt;ListTask&gt;();
int totalCount = list.size();
int threadCount=totalCount/(threadNum-1);
for (int i=0;i&lt;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&lt;Future&lt;BigInteger&gt;&gt; resList =  es.invokeAll(sumList);
for (int i=0;i&lt;resList.size();i++)
{
result  =result.add(resList.get(i).get());
}
es.shutdown();
return result;
}

class ListTask  implements Callable&lt;BigInteger&gt;
{
private volatile List&lt;Integer&gt; list;
private int start;
private int end;

public ListTask(List&lt;Integer&gt; 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&lt;=end;i++) result = result.add(new BigInteger(String.valueOf(list.get(i))));
return result;
}

}
}

</pre>
161 楼 chenyongxin 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操作），丧失了实时性。



160 楼 chenyongxin 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;

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

158 楼 dolwenjian 2010-12-20  
看完回帖 用了2小时！！！
LZ 的解答 应该能混过面试。。
后面的回帖，可以给面试加分
157 楼 wenshao 2010-08-04  
楼主使用CycliBarrier不当
156 楼 AQiao 2010-08-04  
看看我的实现，不用CyclicBarrier，不过线程多了确实慢

import java.util.*;

public class Demo {
    private static final int NUM = 100;

    public static void populate(List list, int count) {
        Random r = new Random();

        for (int i = 0; i < count; i++) {
            int e = r.nextInt(10);
            System.out.print(e + ",");
            list.add(e);
        }
        System.out.println();
        int total = 0;
        long start = System.currentTimeMillis();
        for (int i = 0; i < list.size(); i++) {
            total += (Integer) list.get(i);
        }
        System.out.println("Cost time 1:" + (System.currentTimeMillis() - start));
        System.out.println(total);
    }

    private static int caculateSum(List<Integer> list) {
        Vector<Worker> workers = new Vector<Worker>();

        int size = list.size();
        int average = size / NUM;
        int i = 0;

        int lockNumber = average + 1;
        if (size % NUM == 0) {
            lockNumber = average;
        }
        NumberLock lock = new NumberLock(lockNumber);

        while (i <= average) {
            int start = NUM * i;
            int range = NUM;
            if ((size - start) < NUM) {
                range = size - start;
            }

            if (range > 0) {
//                System.out.println(start + ", " + range);
                Worker worker = new Worker(list, start, range, lock);
                workers.add(worker);
                worker.start();
            }
            i++;
        }
        synchronized (lock) {
            while (!lock.isAllReached()) {
                try {
                    lock.wait();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }

        }
        Iterator<Worker> iterator = workers.iterator();
        int total = 0;
        while (iterator.hasNext()) {
            Worker worker = iterator.next();
            total += worker.getSubSum();
        }
        return total;

    }

    private static class NumberLock {
        private int number;

        public NumberLock(int number) {
            this.number = number;
        }

        public synchronized void decrease() {
            number--;
            notifyAll();
        }

        public synchronized boolean isAllReached() {
            return number == 0;
        }
    }

    private static class Worker extends Thread {
        private int subSum;
        private List<Integer> list;
        private int startPos;
        private int range;
        private NumberLock lock;

        public Worker(List<Integer> list, int startPos, int range, NumberLock lock) {
            this.list = list;
            this.startPos = startPos;
            this.range = range;
            this.lock = lock;
        }

        public void run() {
            for (int i = startPos; i < startPos + range; i++) {
                subSum += list.get(i);
            }
            lock.decrease();

        }

        public int getSubSum() {
            return subSum;
        }
    }

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<Integer>();
        populate(list, 3000);
        long start = System.currentTimeMillis();
        int sum = caculateSum(list);
        System.out.println("Total Cost 2:" + (System.currentTimeMillis() - start));
        System.out.println(sum);
    }
}
155 楼 wave-labs 2010-07-30  
这个题没那么复杂吧，这是我的实现，要点：
1、具有返回值的Callable。
2、线程池。
3、收集多个线程返回值。 
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

public class NumSummer {

	public static void main(String[] args) {
		// 数组规模
		int itemNum = 1000000;
		// 线程数目
		int threadNum = 18;

		// 初始化数组
		List<Integer> list = new ArrayList<Integer>(itemNum);
		for (int i = 1; i <= itemNum; i++) {
			list.add(i);
		}

		// 单线程运算
		long startTime = System.currentTimeMillis();
		long sum = 0;
		for (Integer item : list) {
			sum += item;
		}
		long usedTime = System.currentTimeMillis() - startTime;
		System.out.println("[单线程] Sum is : " + sum + " , time is : " + usedTime);

		// 多线程运算
		startTime = System.currentTimeMillis();
		int offset = itemNum / threadNum;
		int remain = itemNum % threadNum;
		List<Callable<Long>> calls = new ArrayList<Callable<Long>>(threadNum);
		int i = 0;
		for (; i < threadNum; i++) {
			calls.add(new SumCallable(list, i * offset, offset));
		}
		if (remain != 0) {
			calls.add(new SumCallable(list, i * offset, remain));
		}
		ExecutorService exeSvc = Executors.newFixedThreadPool(threadNum);
		try {
			List<Future<Long>> futuers = exeSvc.invokeAll(calls);
			sum = 0;
			for (Future<Long> futuer : futuers) {
				sum += futuer.get();
			}
		} catch (Exception e) {
			e.printStackTrace();
		} finally {
			exeSvc.shutdown();
		}
		usedTime = System.currentTimeMillis() - startTime;
		System.out.println("[多线程] Sum is : " + sum + " , time is : " + usedTime);
	}

	private static class SumCallable implements Callable<Long> {
		private List<Integer> items;
		private int start;
		private int offset;

		public SumCallable(List<Integer> items, int start, int offset) {
			this.items = items;
			this.start = start;
			this.offset = offset;
		}

		public Long call() throws Exception {
			long sum = 0;
			for (int i = start; i < start + offset; i++) {
				sum += items.get(i);
			}
			return sum;
		}
	}

}
154 楼 ei0 2010-07-24  
为啥很大的整数要用List，多个cpu计算。分割任务的粒度要看任务本身难度、通信开销的。有时候用2个cpu比用4个快。
153 楼 lz12366 2010-07-18  
绝对好帖子................
152 楼 飞雪无情 2010-07-17  
skzr.org 写道
呵呵，当时只是写下了自己的思路，还有不少问题没有注意，特别是JOIN的用法，确实会无限制等待，我也不知道叫什么锁 ^ ^
下面的代码我测试过的：
其中取核心数，参考了大家的方法获得的 ^ ^
以下为我对题目的理解
  • 充分利用cpu，就是有多少核心开多少线程参与计算
  • 无限大List，无限大说明当前jvm内存可能不太够了，计算中尽量少new对象
  • 无限大List，无限大说明 极有可能产生非常大的 和数 需要考虑精度范围

我的处理：
[/list]
  • 为了保证精度因此使用了BigDecimal存储和数
  • 为了保证尽量少new BigDecimal对象，每一个线程内部使用long进行求和，只有当精度不够时才加入到最终结果中，同时内部和数置为合适数据，线程结束时把内部和数加入最终结果
    • [/list]
    lz的思路是一样，主要是本人对lz提到的一些新的处理线程方式，我都没有用过^ ^ 见笑了阿
    所以以下只是最初级的实现了，楼上提到的问题等待等已经解决了 

    import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;

public class MyWorkThread extends Thread {
	private List<Integer> list;
	private int start, end;
	private long value;
	private Result result;

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


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

	public void run() {
		try {
			for(int i = start; i < end; i++) add(list.get(i));
			result.addSum(value);
		} finally {
			result.finishA();
		}
	}
	
	public static void main(String[] args) throws InterruptedException {
		List<Integer> list = new ArrayList<Integer>();
		for (int i = 0; i < 100000; i++) {
			list.add(i);
		}
		
		Result result = new Result();
		
		int cpuCoreSize = Runtime.getRuntime().availableProcessors(); //Returns the number of processors available to the Java virtual machine.
		int len = list.size() / cpuCoreSize;
		if (len == 0) len = 1;
		int start = 0, end = len;
		
		List<Thread> threads = new ArrayList<Thread>();
		for (;;) {
			end = start + len;
			if (end > list.size()) end = list.size();
			threads.add(new MyWorkThread(list, start, end, result));
			start = end;
			if (start == list.size()) break;
		}
		result.setCountThread(threads.size());
		
		for (Thread thread : threads) {
			thread.start();
		}
		
		synchronized (result) {
			while(!result.isGameOver()) result.wait();
		}
		System.out.println("和为：" + result.getSum());
	}
}

class Result {
	private BigDecimal sum;
	private int countFinish, countThread;
	
	
	public BigDecimal getSum() {
		return sum;
	}
	
	public void setCountThread(int countThread) {
		assert countThread > 0;
		this.countThread = countThread;
	}
	
	
	private void checkGameOver() {
		if (isGameOver()) notifyAll();
	}
	
	public synchronized boolean isGameOver() {
		return countFinish >= countThread;
	}
	
	public synchronized void addSum(long v) {
		sum = sum == null ? new BigDecimal(v) : sum.add(BigDecimal.valueOf(v));
	}
	
	public synchronized void finishA() {
		countFinish++;
		checkGameOver();
	}
}


    嗯。。不错。。。
    151 楼 飞雪无情 2010-07-17  
    linchao198401 写道
    总之，我已经知道join()的正确用法
    就是谁调用join()。
    执行这个调用的那个线程就得阻塞，被调用的那个线程执行完成

    所以说
    在主线程调用currentThread().join()的意思就是
    主线程调用join()。
    执行这个调用的主线程阻塞，直到被调用的那个线程，目前也是主线程执行完成，结果就是永远都不会完成。

    嗯。。这个解释是对的。。
    150 楼 skzr.org 2010-07-17  
    呵呵，当时只是写下了自己的思路，还有不少问题没有注意，特别是JOIN的用法，确实会无限制等待，我也不知道叫什么锁 ^ ^
    下面的代码我测试过的：
    其中取核心数，参考了大家的方法获得的 ^ ^
    以下为我对题目的理解
    • 充分利用cpu，就是有多少核心开多少线程参与计算
    • 无限大List，无限大说明当前jvm内存可能不太够了，计算中尽量少new对象
    • 无限大List，无限大说明 极有可能产生非常大的 和数 需要考虑精度范围

    我的处理：
    [/list]
  • 为了保证精度因此使用了BigDecimal存储和数
  • 为了保证尽量少new BigDecimal对象，每一个线程内部使用long进行求和，只有当精度不够时才加入到最终结果中，同时内部和数置为合适数据，线程结束时把内部和数加入最终结果
    • [/list]
    lz的思路是一样，主要是本人对lz提到的一些新的处理线程方式，我都没有用过^ ^ 见笑了阿
    所以以下只是最初级的实现了，楼上提到的问题等待等已经解决了 

    import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;

public class MyWorkThread extends Thread {
	private List<Integer> list;
	private int start, end;
	private long value;
	private Result result;

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


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

	public void run() {
		try {
			for(int i = start; i < end; i++) add(list.get(i));
			result.addSum(value);
		} finally {
			result.finishA();
		}
	}
	
	public static void main(String[] args) throws InterruptedException {
		List<Integer> list = new ArrayList<Integer>();
		for (int i = 0; i < 100000; i++) {
			list.add(i);
		}
		
		Result result = new Result();
		
		int cpuCoreSize = Runtime.getRuntime().availableProcessors(); //Returns the number of processors available to the Java virtual machine.
		int len = list.size() / cpuCoreSize;
		if (len == 0) len = 1;
		int start = 0, end = len;
		
		List<Thread> threads = new ArrayList<Thread>();
		for (;;) {
			end = start + len;
			if (end > list.size()) end = list.size();
			threads.add(new MyWorkThread(list, start, end, result));
			start = end;
			if (start == list.size()) break;
		}
		result.setCountThread(threads.size());
		
		for (Thread thread : threads) {
			thread.start();
		}
		
		synchronized (result) {
			while(!result.isGameOver()) result.wait();
		}
		System.out.println("和为：" + result.getSum());
	}
}

class Result {
	private BigDecimal sum;
	private int countFinish, countThread;
	
	
	public BigDecimal getSum() {
		return sum;
	}
	
	public void setCountThread(int countThread) {
		assert countThread > 0;
		this.countThread = countThread;
	}
	
	
	private void checkGameOver() {
		if (isGameOver()) notifyAll();
	}
	
	public synchronized boolean isGameOver() {
		return countFinish >= countThread;
	}
	
	public synchronized void addSum(long v) {
		sum = sum == null ? new BigDecimal(v) : sum.add(BigDecimal.valueOf(v));
	}
	
	public synchronized void finishA() {
		countFinish++;
		checkGameOver();
	}
}

    149 楼 mercyblitz 2010-07-16  
    linchao198401 写道
        public final synchronized void join(long l)
            throws InterruptedException
        {
            long l1 = System.currentTimeMillis();
            long l2 = 0L;
            if(l < 0L)
                throw new IllegalArgumentException("timeout value is negative");
            if(l == 0L)
                for(; isAlive(); wait(0L));
            else
                do
                {
                    if(!isAlive())
                        break;
                    long l3 = l - l2;
                    if(l3 <= 0L)
                        break;
                    wait(l3);
                    l2 = System.currentTimeMillis() - l1;
                } while(true);
        }

    反编译的代码如上。
    join()等于join(0)
    所以其实就是执行
    for(; isAlive(); wait(0L));

    isAlive()应该是判断被调用的线程是否活着。
    对于currentThread()来说肯定是true。
    所以马上执行wait(0L)
    wait()就应该是阻塞。

    因为currentThread()根本就不会返回isActive()为false，只有子线程完成才有可能为false。
    所以主线程调用子线程的join()相当于调用子线程的isAlive()，是很正常的啊。

    你还有其他看法吗？


    通过上面的分析，join()方法和wait()方法几乎没有区别，除了join调用之前不需要同步。
    148 楼 mercyblitz 2010-07-16  
    linchao198401 写道
    总之，我已经知道join()的正确用法
    就是谁调用join()。
    执行这个调用的那个线程就得阻塞，被调用的那个线程执行完成

    所以说
    在主线程调用currentThread().join()的意思就是
    主线程调用join()。
    执行这个调用的主线程阻塞，直到被调用的那个线程，目前也是主线程执行完成，结果就是永远都不会完成。



    呵呵，不过还是小小的问题，这是等待，而不是阻塞。线程状态是不同的，建议参考一下Thread#State枚举。
    其中有BLOCKED，和WAITING之分。
    147 楼 linchao198401 2010-07-16  
        public final synchronized void join(long l)
            throws InterruptedException
        {
            long l1 = System.currentTimeMillis();
            long l2 = 0L;
            if(l < 0L)
                throw new IllegalArgumentException("timeout value is negative");
            if(l == 0L)
                for(; isAlive(); wait(0L));
            else
                do
                {
                    if(!isAlive())
                        break;
                    long l3 = l - l2;
                    if(l3 <= 0L)
                        break;
                    wait(l3);
                    l2 = System.currentTimeMillis() - l1;
                } while(true);
        }

    反编译的代码如上。
    join()等于join(0)
    所以其实就是执行
    for(; isAlive(); wait(0L));

    isAlive()应该是判断被调用的线程是否活着。
    对于currentThread()来说肯定是true。
    所以马上执行wait(0L)
    wait()就应该是阻塞。

    因为currentThread()根本就不会返回isActive()为false，只有子线程完成才有可能为false。
    所以主线程调用子线程的join()相当于调用子线程的isAlive()，是很正常的啊。

    你还有其他看法吗？
    146 楼 linchao198401 2010-07-16  
    总之，我已经知道join()的正确用法
    就是谁调用join()。
    执行这个调用的那个线程就得阻塞，被调用的那个线程执行完成

    所以说
    在主线程调用currentThread().join()的意思就是
    主线程调用join()。
    执行这个调用的主线程阻塞，直到被调用的那个线程，目前也是主线程执行完成，结果就是永远都不会完成。
    发表评论

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

    相关推荐

      若邻网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