bashで8 queensを真面目に並列処理 #Bash

bashで8 queensを並列処理( https://qiita.com/nihongi/items/7dd6dd0f36ce5ef73bc8 )の続きです。

前回は、サブシェルに処理を投げっぱなしの並列処理でした。でも、一般的な並列処理では処理を依頼した側が結果を受け取る必要があります。(仕事でも、部下に投げっぱなしで結果を見てないと怒られますし。)

そこで、並列処理の親が子の結果をちゃんと全部受け取ってから終了するように改善します。

サブシェルの結果を受け取るには

サブシェルの標準出力を親プロセスで受け取る方法はあるかと調べたのですが、あまり上手い方法は見つけられませんでした。たとえばRedhat系では /proc の下を見るという方法があるらしいですが、OS依存になるし、root権限が必要なので、イマイチです。

次善策ですが、ファイルによる結果の受け渡しとしました。ファイルの読み書きのオーバヘッドが気になりますが、キャッシュが働くはずなのであまり問題にはなりません。

サブシェル側では/tmp/nq.${BASHPID}という自分のPIDを付与したファイルに結果を書き込みます。

呼び出し側では$!でサブシェルのPIDを取得します。まずwait $!でサブシェルの終了を待ち、サブシェルが終了したらcat /tmp/nq.$!で結果を取得します。実際にはサブシェルが複数あるので、複数の$!を処理するようなコードになります。

修正後のコード

前回のコードにwaitや途中結果(/tmp/nq.xxx)の読み書きを加えただけです。

8queens3.sh

#!/bin/sh

board="0000000000000000000000000000000000000000000000000000000000000000"

put() {
  # ${1}の${2}列目にクイーンを置く
  # 0列目は無条件に置ける
  if [ ${2} -eq 0 ]; then
    children=""
    for i in {0..7}
    do
      tmp=${1:0:$(( ${2} + 8 * ${i} ))}"1"${1:$(( ${2} + 8 * ${i} + 1 ))}
      (put ${tmp} 1)&
      children="${children} $!"
    done
    wait ${children}
    for i in ${children}
    do
      if [ -f /tmp/nq.${i} ]; then
        cat /tmp/nq.${i}
        rm /tmp/nq.${i}
      fi
    done
  else
  # 1列目以降
    # もしi行目にクイーンを置いたら(${2}-1)列目までに衝突があるかを調べる
    # 衝突がなければクイーンを置いて次の列に行く
    children=""
    for i in {0..7}
    do
      for j in `seq 0 $(( ${2} - 1 ))`  # j列目
      do
        # 横方向
        if [ "${1:$(( ${j} + 8 * ${i} )):1}" = "1" ]; then
          continue 2
        fi
        # 斜め上方向
        if [ $(( ${i} + ${j} - ${2} )) -ge 0 ]; then
          if [ "${1:$(( ${j} + 8 * ( ${i} + ${j} - ${2} ) )):1}" = "1" ]; then
            continue 2
          fi
        fi
        # 斜め下方向
        if [ $(( ${i} + ${2} - ${j} )) -le 7 ]; then
          if [ "${1:$(( ${j} + 8 * ( ${i} + ${2} - ${j} ) )):1}" = "1" ]; then
            continue 2
          fi
        fi
      done
      # 衝突なし
      tmp=${1:0:$(( ${2} + 8 * ${i} ))}"1"${1:$(( ${2} + 8 * ${i} + 1 ))}
      if [ ${2} = 7 ]; then
        echo ${tmp} >> /tmp/nq.${BASHPID}
      else
        (put ${tmp} $(( ${2} + 1 )))&
        children="${children} $!"
      fi
    done
    wait ${children}
    for i in ${children}
    do
      if [ -f /tmp/nq.${i} ]; then
        OUT=$(</tmp/nq.${i})
        for o in ${OUT}
        do
          echo ${o} >> /tmp/nq.${BASHPID}
        done
        rm /tmp/nq.${i}
      fi
    done
  fi
}

put ${board} 0

処理速度の比較

$ time sh 8queens1.sh
1000000000000010000010000000000101000000000100000000010000100000
1000000000000010000100000000010000000001010000000000100000100000
(途中省略)
0010000000001000010000000000000100000100000100000000001010000000
0010000000000100000100000100000000000001000010000000001010000000

real    0m20.365s
user    0m12.171s
sys     0m8.454s
$ time sh 8queens3.sh
1000000000000010000010000000000101000000000100000000010000100000
1000000000000010000100000000010000000001010000000000100000100000
(途中省略)
0010000000001000010000000000000100000100000100000000001010000000
0010000000000100000100000100000000000001000010000000001010000000

real    0m5.304s
user    0m11.334s
sys     0m9.823s

前回同様4コアのマシン(VM)で、非並列処理は20秒程度、並列処理は5秒程度です。ちゃんと速くなってます。userモードとsysモードの内訳が大体似ているところが興味深いですね。

結論

bashでもちゃんと並列処理できました。これができると、動的計画法など、もっと高度なこともやってみたくなりますね。