はじめての並行処理 -８Queensパズルを題材にして-

自己紹介

長らくLispとPrologを好んで使ってきました。この度、Elixirを使ってみてその良さに惚れ込みました。ElixirはS式ではないLispのようです。Ruby風のシンタックスのため、すぐに基本文法に慣れることができました。Elixirの特長である並行処理に挑戦してみました。

題材

Elixirに習熟するために素因数分解や8Queensパズルを書いて基本的な書き方を学んでいました。ある程度、慣れてきましたので、いよいよElixirの魅力である並行処理にとりかかることにしました。題材には練習で書いた8Queensパズルを使うことにしました。マルチCPUの並列を活かして逐次処理より高速にできないか？という課題に取り組みました。

Queens問題

図のようにチェス盤上でクイーンが互いに利き筋にならないような配置を求める問題です。リストを使って位置を表すようにします。図の配置であればリストは次のようになります。

リスト　[2,4,6,8,3,1,7,5]

（出典　Wikipedia）

素朴な方法

当初、Elixirらしいパイプ演算子を用いる方法で逐次的に計算するものを作りました。順列のリストを生成、それを利き筋でないかどうかを確認するsafe/1という関数を作り、フィルターで解を絞り込むという方法です。ここに投稿があります。投稿記事

並行処理のアイディア

上記の素朴な方法をベースにしてElixirの軽量プロセスを活かす方法を考えました。順列を全部生成してからではなく、１つ生成する都度、利き筋でないかを確認するプロセスを起動して渡すというアイディアです。書籍「プログラミングElixir」ではプロセスを1万個程度、生成することはElixirにとっては容易なことであるという記述があったことを思い出しました。上記の素朴に１つ１つの順列に対してプロセスを起動しても動くのではないかと期待しました。

コードは下記の通りです。

defmodule W do
  def judge do
    receive do
      {_,msg} ->
        if safe(msg) do
          :io.write(msg)
        end
    end
  end

  def safe([]) do true end
  def safe([l|ls]) do
    if safe1(ls,l,1) do
      safe(ls)
    else
      false
    end
  end

  def safe1([],_,_) do true end
  def safe1([l|ls],a,n) do
    if a+n == l || a-n == l do
      false
    else
      safe1(ls,a,n+1)
    end
  end
end


defmodule M do
    def queens(n) do
    Enum.to_list(1..n)
    |> perm
  end

  def perm (ls) do
    perm1(ls,[])
  end

  def perm1([],a) do
    ls = Enum.reverse(a)
    pid = spawn(W, :judge, [])
    send pid, {self(),ls}
  end
  def perm1(ls,a) do
    Enum.each(ls,fn(n) ->
                  perm1(ls--[n],[n|a]) end)
  end
end

結果及び考察

驚きました。8Queensを難なく計算します。8!＝40,320のプロセスが起動しているはずです。Elixirは涼しい顔をして計算を終えます。それならばと9Queensではどうか？10Queensではどうか？とやってみました。ちゃんと動作します。たいへん、驚きました。タスクマネージャーでCPUの稼働率を表示しながら10Queensを実行してみるとCPU稼働率が１００％に達します。これはすごい！

しかし、冷静になって計算時間を計測してみると並行処理の方が遅いことがわかりました。解を表示させるとターミナルへの表示速度が影響してしまうため、表示なしで計測してみました。10Queensでは並行処理で8.797秒。逐次処理で3.797秒でした。いくら軽量プロセスとはいえ起動のためのタイムロスが大きいのだろうと思います。それにしてもまずは並行処理が動きました。

改良

上記の結果を踏まえて改良を考えました。

プロセス数

N-queensのN個のプロセスを生成することにしました。8Queensなら8つに分割して８つのプロセスに渡します。順列を生成するときに例えば1..8の順列を生成する場合であれば1を抜き取ります。2..8の順列の先頭に１を加えます。同様に2を抜き取り、1,3..8の順列を生成し、先頭に2を加えます。このようにして生成区間をN個に分割します。

枝刈り

順列を全部生成してからセーフかどうかを判定するのは非効率です。[1,2]まで生成した時点でもう以後はセーフにはなり得ないことが判明しています。生成する時に同時にセーフかどうかを判定しながら生成すると桁違いに速度が向上します。これは有名な教科書のSICPでも書かれていたのですが、無視していました。並列処理をしてもせいぜいコア数分程度しか性能が向上しないのに対し、アルゴリズムの工夫は時に桁違いな性能向上になります。あわせて改良しました。逐次処理版の9Queensは16ミリ秒に改良できました。

リスト化

並行処理で生成した解が正しいかどうかを検証するのに既に知られている解の数との比較、確認することにしました。そうすると結果を表示するのではなく、リストにしておいてlength/1でリストの要素数を確認できた方が便利です。リストを返すように改良しました。

改良後のコード

上記の改良を織り込んだコードは下記の通りです。

M.pqueens/1 並行処理のN-Queens
M.queens/1　逐次処理のN-Queens　（比較用）
pqueens1/2　pqueens/1の下請け関数　順列生成をn個に分割してn個のプロセスに割り振る。
pqueens2/2　n個のプロセスから解を受け取りリストにまとめる。
W.part/0　pqueens1/2から生成されるプロセス。N-QueensのNとその部分xを受け取り、part_perm_list/2に渡す。
part_parm_list/2　n*nの盤面でのx列でのQueensの部分解を得る。

defmodule M do
  def pqueens(n) do
    pqueens1(n,1)
    pqueens2(n,[])
  end

  def queens(n) do
    ls = Enum.to_list(1..n)
    W.perm_list(ls)
  end

  def pqueens1(n,x) do
    if x>n do
      true
    else
      pid = spawn(W,:part,[])
      send pid, {self(),{n,x}}
      pqueens1(n,x+1)
    end
  end

  def pqueens2(0,ans) do ans end
  def pqueens2(n,ans) do
    receive do
      {:answer, msg } ->
        pqueens2(n-1,msg++ans)
    end
  end
end

defmodule W do

  def part do
    receive do
      {sender,{n,x}} -> send sender,{:answer, W.part_perm_list(n,x) }
    end
  end

  def part_perm_list(n,x) do
    ls = Enum.to_list(1..n) -- [x]
    perm_list1(ls,[x],[])
  end

  def perm_list(ls) do
    perm_list1(ls,[],[])
  end

  def perm_list1([],a,b) do
    if safe(a) && a != [] do
      [Enum.reverse(a)|b]
    else
      b
    end
  end

  def perm_list1(ls,a,b) do
    if safe(a) do
      List.foldr(ls,
                b,
                fn(x,y) -> perm_list1(ls--[x],[x|a],y) end)
    else
      List.foldr(ls,
                b,
                fn(x,y) -> perm_list1([],[],y) end)
    end
  end

  def safe([]) do true end
  def safe([l|ls]) do
    if safe1(ls,l,1) do
      safe(ls)
    else
      false
    end
  end

  def safe1([],_,_) do true end
  def safe1([l|ls],a,n) do
    if a+n == l || a-n == l do
      false
    else
      safe1(ls,a,n+1)
    end
  end
end

結果

逐次処理のものと並行処理のものと２つを用意しました。1Queensから15Queensまでにつき解の個数が既に知られている個数と一致することを確認しました。

9queensで逐次処理ですと16ミリ秒です。驚いたことに並行処理をする方は計測不能、0秒となっています。10Queensでようやく数値が計測できました。結果は下記の通りです。計測にあたっては自作したtimeマクロを利用しました。（使用マシンのCPU　インテル　core　i5　3.20GHz）

#並行処理版
iex(11)> T.time(M.pqueens(9))
"time: 0 micro second"
"-------------"
[
  [3, 1, 4, 7, 9, 2, 5, 8, 6],...]

iex(7)> T.time(M.pqueens(10))
"time: 16000 micro second"
"-------------"
[
  [8, 1, 3, 6, 9, 7, 10, 4, 2, 5],...]

#逐次処理版
iex(9)> T.time(M.queens(9))
"time: 16000 micro second"
"-------------"
[
  [1, 3, 6, 8, 2, 4, 9, 7, 5],...]



iex(8)> T.time(M.queens(10))
"time: 63000 micro second"
"-------------"
[
  [1, 3, 6, 8, 10, 5, 9, 2, 4, 7],...]

並行処理をした方がおよそ4倍高速になっていました。core　i5　なので台数効果がそのくらいなのだと思います。

並行処理版では15Queensくらいまでなら実用時間内に計算が終わります。15Queensで数分かかりました。

終わりに

いよいよ並列の時代が到来したのだと実感しました。Elixirの土台となっているErlangはアクターモデル、軽量プロセスを採用しています。現在はインテル　core　i5　i7　が通常ですが、将来　i100、i1000　といったマルチコアCPUが出現する可能性もあります。Elixirはこうした技術の恩恵を余すところなく享受できます。ますます複雑化し、高速化が要求されるWEBプログラムに応えられる最有力候補はElixirであろうと思います。

参考文献、資料

「プログラミングElixir」　Dave　Thomas　著　笹田耕一、鳥井雪　共訳

timeマクロ
https://qiita.com/sym_num/items/4fc0dcfd101d0ae61987