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

总之，我已经知道join()的正确用法
就是谁调用join()。
执行这个调用的那个线程就得阻塞，被调用的那个线程执行完成

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

    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()，是很正常的啊。

你还有其他看法吗？

呵呵，不过还是小小的问题，这是等待，而不是阻塞。线程状态是不同的，建议参考一下Thread#State枚举。
其中有BLOCKED，和WAITING之分。

通过上面的分析，join()方法和wait()方法几乎没有区别，除了join调用之前不需要同步。

呵呵，当时只是写下了自己的思路，还有不少问题没有注意，特别是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();
	}
}

嗯。。这个解释是对的。。

嗯。。不错。。。

为啥很大的整数要用List，多个cpu计算。分割任务的粒度要看任务本身难度、通信开销的。有时候用2个cpu比用4个快。

这个题没那么复杂吧，这是我的实现，要点：
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;
		}
	}

}

看看我的实现，不用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);
    }
}