一道美团的面试题

大概是两年前吧，朋友去美团面试，考了他一道纯工程的题目：

使用多线程实现 1 + 2 + 3 + ..... + 1000

确实是很好的一道面试题，这两年面试别人，我也经常会用这道题。相比于烂俗的链表反转，二分查找。这道题要有趣的多。

多线程解决问题，首先的思路是把任务拆分。在这个题中，很容易想到两种拆分方式(我们以拆成10份为例)：
1 按范围把1000个数分成10份，分别为
[1, 100]
[101, 200]
.....
[901, 1000]

2 每个数对10取模，分为10组
{1, 11, 21, 31.....991}
{2, 12, 22, .... 992}
....
{10, 20, 30, ..... 1000}

由于两种方式没有本质的区别，为了简便，本文中使用第一种方式作为拆分方式实现。

1 最简单版本的实现

    public static void main(String[] args) throws InterruptedException {
        AtomicInteger sum = new AtomicInteger();
        List<Thread> threadList = new ArrayList<>();

        for (int i = 0; i < 10; i++) {
            final int cur = i;

            Thread thread = new Thread(new Runnable() {
                @Override
                public void run() {
                    for (int j = cur * 100 + 1; j <= cur * 100 + 100; j++) {
                        sum.addAndGet(j);
                    }
                }
            });
            thread.start();
            threadList.add(thread);
        }

        for (Thread thread : threadList) {
            thread.join();
        }

        System.out.println(sum.get());
    }

代码没啥亮点，但也没什么漏洞。
改进点是可以使用线程池代替线程数组，使用CountDownLatch来判定结束。
改进版的实现如下：

2 线程池版

    public static void main(String[] args) throws InterruptedException {
        AtomicInteger sum = new AtomicInteger();
        ExecutorService pool = Executors.newCachedThreadPool();
        final CountDownLatch latch = new CountDownLatch(10);

        for (int i = 0; i < 10; i++) {
            final int cur = i;

            pool.execute(new Runnable() {
                @Override
                public void run() {
                    for (int j = cur * 100 + 1; j <= cur * 100 + 100; j++) {
                        sum.addAndGet(j);
                    }

                    latch.countDown();
                }
            });
        }

        latch.await();
        System.out.println(sum.get());
    }

用到了线程池，一定会想到java的future类和callable，正好适合解决这种问题。

3 future版

    public static void main(String[] args) throws ExecutionException, InterruptedException {
        ExecutorService pool = Executors.newCachedThreadPool();
        List<Future<Integer>> futureList = new ArrayList<>();
        int sum = 0;

        for (int i = 0; i < 10; i++) {
            final int cur = i;

            futureList.add(pool.submit(new Callable<Integer>() {
                @Override
                public Integer call() {
                    int segSum = 0;

                    for (int j = cur * 100 + 1; j <= cur * 100 + 100; j++) {
                        segSum += j;
                    }

                    return segSum;
                }
            }));
        }

        for (int i = 0; i < 10; i++) {
            sum += futureList.get(i).get();
        }

        System.out.println(sum);
    }

上面的这几种方式，都能正确得到答案，在工程上也基本没有漏洞。扩展性来说，也还算不错。
但总觉得中规中矩，没有什么亮点。
不够有趣。

前几天看一篇分享，讲stream.parallel的应用场景。突然灵光一闪，发现用在这个问题上简直是量身定做一般。
代码如下：

    public static void main(String[] args) {
        System.out.println(IntStream.range(0, 10)
                .boxed()
                .parallel()
                .mapToInt(i -> IntStream.rangeClosed(i * 100 + 1, i * 100 + 100).sum())
                .sum());
    }

其实还可以更简化的：

    public static void main(String[] args) {
        System.out.println(IntStream.rangeClosed(0, 1000)
                .parallel()
                .sum());
    }

have fun