Java7 の Frok/Join Framework を使って、しりとりをしてみました。

Java

この前、「最も長く続くしりとり何か」という問題は再帰で解けることに気づきました。
そして、再帰なら Java7 の Fork/Join Framework です！
というわけで、書いてみました！

しりとりのアルゴリズム

「最も長いしりとりは何か」という問題は、再帰を使って解けます。
例えば、「しりとり、りんご、ごりら、ごーる…」という単語の集合＝A を使ってできる最も長いしりとりは…

  • 「しりとり」→ {集合A から「しりとり」を除いた集合}＝B を使ってできる最も長いしりとり
    • 「しりとり」→「りんご」→ {集合B から「りんご」を除いた集合}＝C を使ってできる最も長いしりとり
      • 「しりとり」→「りんご」→ 「ごりら」→ {集合C から「ごりら」を除いた集合}＝D1 を使ってできる最も長いしりとり
      • 「しりとり」→「りんご」→ 「ごーる」→ {集合C から「ごーる」を除いた集合}＝D2 を使ってできる最も長いしりとり
        • → …

というようになります。


Java7 で書くとこんな感じです。

public List<String> computeLongestShiritori(String prevWord, Collection<String> words){
    Objects.requireNonNull(prevWord, "prevWord");
    Objects.requireNonNull(words, "words");

    // 前回の単語はもう使えないので、単語集から取り除く
    List<String> nextWords = new ArrayList<>(words);
    nextWords.remove(prevWord);
    
    List<String> longest = new ArrayList<>();
    for(String nextWord : nextWords){
        if(!isChain(prevWord, nextWord)){
            // しりとり不成立
            continue;
        }

        // 再帰
        List<String> result = computeLongestShiritori(nextWord, nextWords);
        if(longest.size() < result.size()){
            longest = result;
        }
    }

    // 前回の単語を、先頭に加える
    longest.add(0, prevWord);

    return longest;
}

Fork/Join Framework で書く

これを、Fork/Join Framework を使って書き換えてみました。
違いは RecursiveTask を継承したクラスに実装することと、"処理の実行"と"結果の取得"を分離することぐらいです。

private class ShiritoriTask extends RecursiveTask<List<String>>{
    private static final long serialVersionUID = 1L;
    
        private final String prevWord;
        private final Collection<String> words;
        private final int depth;
                
        public ShiritoriTask(String prevWord, Collection<String> words, int depth){
            this.prevWord = prevWord;
            this.words = words;
            this.depth = depth;
        }
        
        @Override
        protected List<String> compute() {
            // 前回の単語はもう使えないので、単語集から取り除く
            List<String> nextWords = new ArrayList<>(words);
            nextWords.remove(prevWord);
            
            List<ShiritoriTask> taskList = new ArrayList<>();
            for(String nextWord : nextWords){
                if(!isChain(prevWord, nextWord)){
                    // しりとり不成立
                    continue;
                }

                ShiritoriTask task = new ShiritoriTask(nextWord, nextWords, depth + 1);
                if(depth < 2){
                    // 並列処理
                    task.fork();
                }else{
                    // 直列処理 （再帰）
                    task.invoke();
                }
                taskList.add(task);
            }

            // 結果取得
            List<String> longest = new ArrayList<>();
            for(ShiritoriTask task : taskList){
                List<String> result = task.join();
                if(longest.size() < result.size()){
                    longest = result;
                }
            }
            
            // 前回の単語を、先頭に加える
            longest.add(0, prevWord);
    
            return longest;
        }
    }
}

少し補足すると…。

  • 再帰の深さに応じて、並列（フォーク）と直列（再帰）を使い分けています。これは、並列処理の粒度が細かすぎるとオーバーヘッドが大きくなって、逆に遅くなってしまうからです。
  • 代表的なサンプルコード*1だと、直列で処理する際に compute() を直接呼び出すようにしていましたが、今回は invoke() 経由で呼び出しています。これは、並列処理と直列処理をあとで同じように扱えるようするためです。


あとは、これを ForkJoinPool で呼び出すようにすれば出来上がりです。

public List<String> computeLongestShiritori(String start, Collection<String> words) {
    Objects.requireNonNull(start, "start");
    Objects.requireNonNull(words, "words");
    
    ForkJoinPool pool = new ForkJoinPool();
    ShiritoriTask task = new ShiritoriTask(start, words, 0);
		
    return pool.invoke(task);
}

実行結果

今回は実行例として「名前でしりとり」をしてみました。


これを実行してみたところ、手元の環境*2だと、Fork/Joinのほうが再帰よりも2〜2.5倍ぐらい速く解けました。*3
（ちなみに、Core i7 のCPU使用率が100%で張り付くような処理を初めて書きました…）


ソースコード(github:gist) ： https://gist.github.com/1640606
eclipse のプロジェクトファイル ： Shiritori.zip
（こちらは、File → Import → Archive File で取り込めます）

      • -

処理を分割して実行するだけなら、今ままでも Executor があったのでそれを使えばよかったのですが、今回のように分割して分割して…を繰り返すなら Fork/Join が向いています。
思った以上に簡単なので、いろんなところで使えそうです！

*1:RecursiveTask (Java Platform SE 7 ) が、配列処理なら フォーク/ジョイン - Oracle Technology Network

*2:Core i7（論理8コア）上で、VMオプション「-server」をつけて実行

*3:8コアあるのに、2.5倍にしかならないのは一回当たりの処理が軽すぎるからだと思います。もう少し負荷の高い処理だとはっきりと効果が出るんですが…。