遞歸場景中JDK 1.5 CompletionService携龟、Executor等的使用

本文通過一個簡單的編程題，分析了多種不同Level的解題思路宝剖，目的在于啟發(fā)coder新人思考的重要性：始終從用戶的角度去換位思考，從“有解”到“有優(yōu)秀的解”蝶糯，從而達到高質(zhì)交付乐疆。

轉(zhuǎn)載請聯(lián)系作者

引

前段時間看到一道Java筆試題：

有1划乖、2、3诀拭、4四個數(shù)字迁筛，能組成多少個互不相同且無重復數(shù)字的三位數(shù)？都是多少耕挨？

這是一個簡單的排列組合題细卧，大家都知道這題的答案是24個；不過題面是要求用代碼的方式計算出來筒占，并輸出這些數(shù)字贪庙。

別看只是一道簡單的Java題，但我感到這是一個考察答題者思維深度和廣度的好題翰苫，我有意將它用于公司新人的招聘上止邮。子曾經(jīng)曰過：同樣是九陰白骨爪，由周芷若和黃衫女使出來奏窑，那就是一個地下一個天上导披！

解法有幾種呢？我們來按武功修為從淺到深的順序來看一看：

image

第一層：單刀直入

第一種思路非常地直來直去埃唯，一般剛畢業(yè)的學生很大一部分會給出這種解：

1. 先從4個數(shù)字中取百位數(shù)
2. 從剩下的3個數(shù)字中再取十位數(shù)
3. 剩下的2個數(shù)字依次作為個位數(shù)撩匕，并將最終產(chǎn)生的結(jié)果放到結(jié)果集里
4. 循環(huán)2~3，直到剩下的3個數(shù)字都被作為十位數(shù)用過
5. 循環(huán)1~4墨叛，直到所有的4個數(shù)字都被作為百位數(shù)用過
6. 輸出最終結(jié)果

// 代碼略

有什么問題止毕？

至少是沒有考慮擴展性吧？如果不是4取3漠趁，而是5取4扁凛、6取3。闯传。谨朝。呢？所以甥绿，我們需要把候選數(shù)字的個數(shù)（candidateNum)和結(jié)果位數(shù)（numLength）都給參數(shù)化掉吧叠必？

想啥呢？接茬練妹窖！

image

第二層：隔山打牛

為了實現(xiàn)候選數(shù)字個數(shù)（candidateNum)和結(jié)果位數(shù)（numLength）的參數(shù)化，我們應(yīng)該能想到的就是：遞歸收叶；這就猶如隔山打牛的內(nèi)家功夫：將造數(shù)計算一層層遞歸下去骄呼，并完成最終擊倒目標的目的~ 基本邏輯思路其實和上一解法一樣。

1. 初始化一個動態(tài)的非重候選數(shù)字列表
2. 開始遞歸造數(shù)(詳細參見makeNums()遞歸方法，每一步都有詳細的注釋)
3. 輸出最終結(jié)果

Shut up & Show me the CODE!

public class Main {
    // 候選最小數(shù)字
    private static int FROM = 1;
    // 候選最大數(shù)字
    private static int TO = 4;
    // 需要生成的數(shù)字長度
    private static int LENGTH = 3;

    public static void main(String[] args) {
        // 初始化候選數(shù)字
        List<Integer> candidateDigits = initCandidateDigits(FROM, TO);
        if(candidateDigits == null){
            return;
        }
        // 造數(shù)
        Date startTime = new Date();
        Set<Integer> result = new TreeSet<Integer>();
        makeNums(result, "", candidateDigits, LENGTH);
        Date endTime = new Date();
        // 輸出
        System.out.println("Finish! Cost(ms): " + (endTime.getTime() - startTime.getTime()) + "\n" +
                "There're " + result.size() + " diffrent nums, and they are:");
        for(int num : result){
            System.out.println(num);
        }
    }


    /**
     *  生成指定位長度非重數(shù)
     * @param result    結(jié)果集
     * @param numHead 組成頭幾位的數(shù)字蜓萄，首次調(diào)用時應(yīng)為""
     * @param candidateDigits  候選數(shù)字
     * @param remainLength 要生成的數(shù)字的位數(shù)
     * @return
     */
    public static Set<Integer> makeNums(Set<Integer> result, String numHead, List<Integer> candidateDigits, int remainLength){
        // 如果結(jié)果集為空隅茎，就創(chuàng)建一個
        if(result == null){
            result = new TreeSet<Integer>();
        }
        // 如果已到最后一位數(shù)（即個位數(shù)），則將剩下的數(shù)字依次拼裝給“前綴數(shù)位”嫉沽，并存入最終結(jié)果
        if(remainLength <= 1){
            for(int digit : candidateDigits){
                result.add(Integer.parseInt(numHead + digit));
            }
        }
        // 否則依次選取下一個位數(shù)的數(shù)字辟犀，并遞歸
        else{
            for(int digit : candidateDigits){
                // 新的頭部數(shù)位 = 舊的頭部數(shù)位 + 下一位選定的數(shù)字
                String newNumHead = numHead + digit;
                // 去除已選定的下一位數(shù)字
                List<Integer> tmpDigits = new ArrayList<Integer>();
                tmpDigits.addAll(candidateDigits);
                tmpDigits.remove(new Integer(digit));
                int newRemainLength = remainLength - 1;
                // 將剩下的候選數(shù)字和剩下的位數(shù)進行遞歸
                makeNums(result, newNumHead, tmpDigits, newRemainLength);
            }
        }
        return result;
    }

    /**
     * 初始化候選數(shù)字(這里只考慮1~9為合法數(shù)字）
     * @param from 候選最小數(shù)字，應(yīng)小于等于to
     * @param to   候選最大數(shù)字绸硕，應(yīng)大于等于from
     * @return
     */
    public static List<Integer> initCandidateDigits(int from, int to){
        List<Integer> result = new ArrayList<Integer>();
        if(from >= to || 1 > from || 9 < from || 1 > to || 9 < to){
            return null;
        }
        for(;from <= to; from++){
            result.add(from);
        }
        return result;
    }
}

通常實現(xiàn)到這一步就可以了堂竟，不過，子又曰過：為了成就絕世武功玻佩，男人就應(yīng)該對自己狠一點出嘹！

第三層：葵花寶典

天賦異稟而又追（xin)求(li)極(bian)致(tai)的東方不敗又想到：如果是大位數(shù)怎么辦呢？比如是從63個64進制的數(shù)字中挑選58個數(shù)之類的咬崔？（確實夠變態(tài)）而且税稼，現(xiàn)在只是拼個數(shù)，萬一在某些情況下垮斯，拼好了之后郎仆，要求根據(jù)這個數(shù)進行一個實時的復雜業(yè)務(wù)計算怎么辦？——好的兜蠕，這時候我們應(yīng)該想到的是——多線程異步

東方不敗練就了這一層武功后扰肌，能將萬千銀針同時急速射出，目標將瞬間斃命牺氨！天下武功狡耻，唯快不破！用了插上多線程翅膀的遞歸模式猴凹，就連以快打快的獨孤九劍也不是敵手夷狰！

但是，葵花寶典不是人人都能練的郊霎，在練之前有很多艱難險阻需要跨越（淫笑的那個去面壁）：

1. 第一個問題就是：在層層的遞歸嵌套面前沼头，用什么方式來進行優(yōu)雅的多線程異步？
2. 需要有一個機制书劝，能知曉所有這些遞歸的異步線程（并不是簡單的并列異步的線程）什么時候結(jié)束进倍？基于業(yè)務(wù)的需要，可能還要獲取遞歸的中間數(shù)據(jù)進行業(yè)務(wù)操作购对。猾昆。。

下面我們來一個個解（zi）決（gong）：

遞歸排列中的多線程邏輯

1. 初始化一個動態(tài)的非重候選數(shù)字列表
2. 初始化一個異步線程池及異步服務(wù)
3. 用異步服務(wù)執(zhí)行排列遞歸
4. 在遞歸方法中骡苞，需要用到遞歸調(diào)用的時候垂蜗，利用第2步中的異步服務(wù)執(zhí)行排列遞歸
5. 在合適的時機獲取最終的排列數(shù)結(jié)果

但是楷扬，如何獲取遞歸結(jié)果？什么才是“合適的時機”贴见？

這個問題可以用JDK1.5的java.util.concurrent包解決烘苹。

利用JDK1.5并發(fā)工具包實現(xiàn)異步機制的原理

java.util.concurrent包是1.5新增的并發(fā)工具包。具體邏輯是：

1. 將要異步的邏輯（本例中即排列遞歸的邏輯）封裝在一個實現(xiàn)了Callable接口的類的call()方法中片部，使其可以被第2步中的Executor托管起來異步執(zhí)行镣衡；
2. 依賴java.util.concurrent.Executor的實現(xiàn)類初始化一個java.util.concurrent.CompletionService接口的實現(xiàn)類；其中前者負責將托管的業(yè)務(wù)邏輯按照某種線程機制（如線程池）異步地執(zhí)行档悠；后者負責將業(yè)務(wù)邏輯的執(zhí)行和執(zhí)行的結(jié)果分離開來廊鸥，并提供一個訪問執(zhí)行結(jié)果的能力；
3. 利用completionService的submit()方法進行執(zhí)行異步邏輯
4. 利用completionService.take()阻塞式得獲取執(zhí)行結(jié)果站粟；得知是否異步操作已完成黍图；

（該包的其他具體用法請參考Java API）

太抽象？好吧奴烙，假想一下這樣一個場景：

你和你老婆/老公很恩愛助被，結(jié)果沒控制住，生了一打baby（業(yè)務(wù)邏輯）切诀。孩子長大后要上學吧揩环？于是你給他們每個人都辦了入學證（實現(xiàn)Callable接口），使得他們能夠同時入學（被托管異步執(zhí)行）幅虑。

你帶著他們來到學校（CompletionService）找到了校長（Executor),說：我孩子這么多丰滑，都要上學，你看咋整倒庵？

校長（Executor)說：放心交給我吧褒墨！我會安排N個老師（多個線程）、按照我們定制的教學大綱擎宝、在我們的多個多功能教室（線程使用的細節(jié)郁妈、調(diào)度等）進行系統(tǒng)化教學的！當然了，以上我所說的一切，你都不需要關(guān)心寇甸！你要做的就是：孩子想上學的時候，你可以隨時送到學校來（completionService.submit()）,然后孩子上完課了（業(yè)務(wù)邏輯完成）你來學校門口跟看門老大爺說一聲：“我要接孩子放學”（completionService.take()）就是了胃碾！當然，接了孩子回去后你可以問問他們今天都教了啥呀（completionService.take().get()）筋搏？

如何跟蹤遞歸的異步多線程執(zhí)行情況

不過這里有一個坑仆百，是校長沒告訴你的：學校是不知道孩子幾點下課的！如果你到了學校門口跟看門老大爺說：下課了吧奔脐？俺想接俺娃回家~（completionService.take()）

也許這時看門老大爺會甩給你一句：我也沒看到你家娃出來儒旬，肯定是還沒下課呢（業(yè)務(wù)邏輯執(zhí)行中）栏账！等著吧！（阻塞）

這時栈源，你也只能干等著。竖般。甚垦。

解決這種尷尬的辦法有兩個：

1 . 根據(jù)經(jīng)驗預估一個孩子上課的時長，然后到點了去接（completionService.poll(long timeout, TimeUnit unit)）涣雕；這種方法的優(yōu)點就是：夠簡單艰亮！缺點則是：不夠穩(wěn)定！： 到了規(guī)定的時間點仍沒接到你要怎么辦挣郭？先回去迄埃，然后再等這么長時間再來接？這太過浪費家長的時間兑障！還有些家長則更簡單粗暴：這熊孩子侄非！等這么久都沒下課！這娃俺不要了Ａ饕搿（知道為什么現(xiàn)在人販子這么好就業(yè)了吧逞怨？）

2 . 相比起來，方法二則顯得更為靠譜：因為要送N個娃去上學福澡，那我就在某個地方記住我一共送了多少個娃進學校叠赦，然后接的時候我就死等，直到接滿了我要接的個數(shù)革砸，我就回家除秀！

for (int i = 0; i < n; ++i) {
    // 接娃，注意：如果沒接到會在這里阻塞
    Future<Child> oneOfMyChildren = completionService.take();
    // 可能的業(yè)務(wù)處理：把娃的作業(yè)本拿出來替他寫作業(yè)（可憐天下父母心）算利。册踩。。
    HomeWork homeWork = oneOfMyChildren.get().getHomeWork();
    doHomeWork(homeWork);
}

3 . 可是問題又來了：因為你是在很多隨意的時間點送了N個孩子去上學笔时，甚至有些孩子是你委托保姆送的棍好，所以導致你根本不記得今天一共送了幾個？

有人說：那我在每送一個孩子上學（completionService.submit()）的時候就累計一下數(shù)目（counter++)允耿，然后我去接的時候每接一個孩子（completionService.take()）就遞減一下數(shù)目（counter- -)借笙，接到counter為0，就說明都接完了较锡，這不就行了业稼？答案是：不行！

因為接蚂蕴、送孩子的時機也許是不固定的（你也許沒法控制保姆接送的時機）低散，所以多個孩子的接和送是可能發(fā)生交織的俯邓，這就導致當你的計數(shù)（counter)為0的時候，也有可能只是把之前送進學校的幾個孩子接走了熔号，這時候還有幾個小孩正在保姆的帶領(lǐng)下去學校呢稽鞭！但這時候你武斷地認為小孩都接完了就回去睡覺了（退出程序片段），那這幾個娃放學后沒人接引镊，他們的家庭作業(yè)誰來做朦蕴？！你還有沒有點做家長的責任心弟头？吩抓！

這時候，你要么依然采用方法1中的辦法設(shè)超時時限赴恨；但另一個可行的辦法是：提前計算好今天一共要送多少小孩上學疹娶，并設(shè)置好counter，然后管他是誰送的伦连、在什么時候送的雨饺；只要在接的時候每接一個就遞減counter，直到counter為0除师。這種辦法很適用于遞歸場景

在本例的遞歸案例中沛膳，按照第二層武功代碼中的遞歸邏輯，遞歸邏輯的異步執(zhí)行次數(shù)是可以計算出來的汛聚。對于一個P(m,n)的遞歸計算（即從m個非重數(shù)字中挑選n個數(shù)字組成n位數(shù)）锹安，它在本例中的遞歸邏輯執(zhí)行次數(shù)（包含首次調(diào)用）是：

Total_Counter of P(m,n)
= p(m,1) + p(m,1)*p(m-1,1)... + p(m,1)*p(m-1,1)...*p(m-n+2),1) + 1           
= m + m*(m-1) + ... + m*(m-1)*...*(m-n+2) + 1【第一次調(diào)用】

這是一個簡單的排列組合題，不理解為什么是這個計算公式的童鞋去溫習一下高中數(shù)學吧倚舀。叹哭。。

Shut up & Show me the CODE!

1. 主函數(shù)

import java.util.*;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

/**
 * Created by Silence on 2016-11-18.
 */
public class Main {

    // 候選最小數(shù)字
    private static int FROM = 1;
    // 候選最大數(shù)字
    private static int TO = 5;
    // 需要生成的數(shù)字長度
    private static int LENGTH = 3;

    public static void main(String[] args) throws Exception {
        // 初始化候選數(shù)字
        List<Integer> candidateDigits = initCandidateDigits(FROM, TO);
        if(candidateDigits == null){
            return;
        }
        // 初始化異步線程池
        Date startTime = new Date();
        Set<Integer> result = Collections.synchronizedSet(new TreeSet<Integer>());
        ExecutorService service = Executors.newCachedThreadPool();
        // 初始化可跟蹤排列遞歸次數(shù)的異步服務(wù)
        TracedRankExecutorCompletionService<Set<Integer>> completion =
                new TracedRankExecutorCompletionService<Set<Integer>>(service, candidateDigits.size(), LENGTH);
        // 造數(shù)
        completion.submit(
                new NumberMaker(result, "", candidateDigits, LENGTH, completion));
        // 確保所有遞歸活動都已結(jié)束
        while (true) {
            // 如果已獲取完所有異步遞歸計算痕貌，則退出循環(huán)
            if(completion.getFutureNum() == 0){
                break;
            }
            // 如果仍有未使用的異步任務(wù)執(zhí)行結(jié)果风罩，則繼續(xù)循環(huán)
            Future<Set<Integer>> future = completion.take();
            if (future != null && future.get() != null &&
                    future.isDone() && !future.isCancelled()) {
                continue;
            }
        }
        // 關(guān)閉異步服務(wù)
        service.shutdown();
        Date endTime = new Date();
        // 輸出
        System.out.println("Finish! Cost(ms): " + (endTime.getTime() - startTime.getTime()) + "\n" +
                "There're " + result.size() + " diffrent nums, and they are:");
//        for(int num : result){
//            System.out.println(num);
//        }
    }

    /**
     * 初始化候選數(shù)字(這里只考慮1~9為合法數(shù)字）
     * @param from 候選最小數(shù)字，應(yīng)小于等于to
     * @param to   候選最大數(shù)字舵稠，應(yīng)大于等于from
     * @return
     */
    public static List<Integer> initCandidateDigits(int from, int to){
        List<Integer> result = new ArrayList<Integer>();
        if(from >= to || 1 > from || 9 < from || 1 > to || 9 < to){
            return null;
        }
        for(;from <= to; from++){
            result.add(from);
        }
        return result;
    }

}

2. 可跟蹤排列遞歸執(zhí)行次數(shù)的CompletionService

import java.util.concurrent.*;

/**
 * 可跟蹤排列遞歸執(zhí)行次數(shù)的CompletionService
 * Created by Silence on 2016-11-22.
 */
public class TracedRankExecutorCompletionService<V> extends ExecutorCompletionService<V> {

    private static Integer futureNum = 1;// 遞歸次數(shù)

    /**
     * Constructor
     * @param executor
     * @param candidateNum  候選非重數(shù)字的個數(shù)
     * @param pickNum   需要挑選的數(shù)字個數(shù)
     * @throws Exception
     */
    public TracedRankExecutorCompletionService(Executor executor, int candidateNum, int pickNum) throws Exception {
        super(executor);
        if(candidateNum <= pickNum){
            throw new Exception("The candidate number must greater than the picked number");
        }
        // p(m,n)的遞歸次數(shù) = p(m,1) + p(m,1)*p(m-1,1)... + p(m,1)*p(m-1,1)...*p(m-n+2),1) + 1
        //                = m + m*(m-1) + ... + m*(m-1)*...*(m-n+2) + 1【第一次調(diào)用】
        // 計算遞歸執(zhí)行次數(shù)
        int factor = 1;
        for(int i = candidateNum; i > candidateNum - pickNum + 1; i--){
            factor *= i;
            futureNum += factor;
        }
    }

    @Override
    public Future<V> take() throws InterruptedException {
        Future<V> future = null;
        try {
            future = super.take();
            // 計數(shù)遞減
            synchronized (futureNum){
                futureNum--;
            }
            return future;
        } catch (InterruptedException e) {
            throw e;
        }
    }

    public static Integer getFutureNum() {
        return futureNum;
    }
}

3. 實現(xiàn)了Callable接口的遞歸邏輯

import java.util.*;
import java.util.concurrent.Callable;
import java.util.concurrent.CompletionService;

/**
 * Created by Silence on 2016-11-20.
 */
public class NumberMaker implements Callable<Set<Integer>> {

    private Set<Integer> result;// 結(jié)果集
    private String numHead;// 組成頭幾位的數(shù)字超升，首次調(diào)用時應(yīng)為""
    private List<Integer> candidateDigits;// 候選數(shù)字
    private int remainLength;// 要生成的數(shù)字的位數(shù)
    private CompletionService<Set<Integer>> completion;// 異步服務(wù)

    // 初始構(gòu)造
    public NumberMaker(Set<Integer> result, String numHead, List<Integer> candidateDigits, int remainLength, CompletionService<Set<Integer>> completion) {
        this.result = result;
        this.numHead = numHead;
        this.candidateDigits = candidateDigits;
        this.remainLength = remainLength;
        this.completion = completion;
    }

    /**
     * 生成指定位長度非重數(shù)
     */
    @Override
    public Set<Integer> call() throws Exception {
        // 如果結(jié)果集為空，就創(chuàng)建一個線程安全的set
        if (result == null) {
            result = Collections.synchronizedSet(new TreeSet<Integer>());
        }
        // 如果已到最后一位數(shù)（即個位數(shù)）哺徊，則將剩下的數(shù)字依次拼裝給“前綴數(shù)位”室琢，并存入最終結(jié)果
        if (remainLength <= 1) {
            for (int digit : candidateDigits) {
                synchronized (result) {
                    result.add(Integer.parseInt(numHead + digit));
                }
                // 模擬復雜業(yè)務(wù)計算
                Thread.sleep(300);
            }
        }
        // 否則依次選取下一個位數(shù)的數(shù)字，并異步遞歸
        else {
            for (int digit : candidateDigits) {
                // 新的頭部數(shù)位 = 舊的頭部數(shù)位 + 下一位選定的數(shù)字
                String newNumHead = numHead + digit;
                // 去除已選定的下一位數(shù)字
                List<Integer> tmpDigits = new ArrayList<Integer>();
                tmpDigits.addAll(candidateDigits);
                tmpDigits.remove(new Integer(digit));
                int newRemainLength = remainLength - 1;
                // 將剩下的候選數(shù)字和剩下的位數(shù)進行異步遞歸
                completion.submit(
                        new NumberMaker(result, newNumHead, tmpDigits, newRemainLength, completion));
            }
        }
        return result;
    }
}

運行結(jié)果比對：真的比第二層武功快嗎落追？

注意到：在遞歸邏輯的call()方法中盈滴，我們加入了如下的代碼來模擬一個“微小”的業(yè)務(wù)計算：

    // 模擬復雜業(yè)務(wù)計算
    Thread.sleep(300);

我們在上文第二層武功方法的同樣位置，加入同樣的模擬代碼轿钠，來比較一下：在加入了一個小耗時業(yè)務(wù)運算的情況下兩者的差別有多大巢钓？以下是運行比較結(jié)果（表中P(M,N)表示從M個非重數(shù)字中挑選N個數(shù)字組成互不相同的N位數(shù)病苗；）：

結(jié)果一目了然！再試想一下芽世，我們只是插入了一個300ms的業(yè)務(wù)計算量，而且也只是10進制的10以內(nèi)數(shù)字的排列組合诡壁，如果候選數(shù)再大店济瓢、業(yè)務(wù)運算時間再長點，解二的耗時就會成指數(shù)增長妹卿！此時旺矾，葵花寶典將具有碾壓性的優(yōu)勢！

第四層：還有第四層夺克？

葵花寶典已經(jīng)是武學的最高境界了嗎箕宙？當然不是！只要你善于思考铺纽，永遠會不斷有進步柬帕！子曰：山外青山樓外樓，還有英雄在前頭狡门！

在解三中至少還有很多地方是需要進一步完善的：

• 如何支持從外部輸入待選數(shù)字陷寝？
• 如何考慮排重等容錯？
• 如果采用的是按照設(shè)置經(jīng)驗過期時間的方式來獲取結(jié)果其馏，那如何加入重試機制凤跑？
• 結(jié)果太龐大的情況下，是否應(yīng)該將結(jié)果輸出到日志文件叛复？
• 為了更好的擴展性仔引，是否應(yīng)該將int都改為long？
• ......

這里不再一一舉例實現(xiàn)褐奥，留待大家思考咖耘。。抖僵。

最后總結(jié)一下：只有不停得從用戶角度換位思考鲤看，才能使人不斷進步！只實現(xiàn)功能耍群，是遠遠不夠的义桂！