LoginSignup
0

More than 5 years have passed since last update.

竹内関数をメモ化と並列処理で...

Posted at

「再帰する竹内関数も高速化」( https://qiita.com/nihongi/items/ad3b8fd5382bc9e9cf80 )の続きです。メモ化のためにmemcachedを使います。bashからmemcachedを使う方法は「シェルスクリプトからmemcachedを使う」( https://qiita.com/nihongi/items/b0db5d577825ac870ae7 )に書いた通りです。最新のソースは https://github.com/nihongi/coding-happiness/blob/develop/memcached/memcached.sh にあります。

正しい竹内関数の定義は次の通りです。(表記はいろいろありますが、ここではクヌースの論文に近い表記にしました)

tarai(x, y, z) = if x <= y then y
                 else tarai(tarai(x-1, y, z),
                            tarai(y-1, z, x),
                            tarai(z-1, x, y))

メモの仕様

第一引数~第三引数をカンマでつないだ文字列をKeyとして、taraiの計算結果をValueとしたKey-Valueをmemcachedに登録します。具体的には"4,2,0"がKey、"4"がValueのようになります。

処理概要

関数の再帰呼び出しとcoproc(memcachedにアクセスするために使用)を一緒に使うとうまく動きませんでした。そこで、再帰呼び出しはshコマンドで全く別のスコープで動かすようにしました。

まずはじめに入力されたパラメータのメモがあるかチェックします。

if [ -z $(mc_get "${1},${2},${3}") ]; then

メモが既にあれば何もせずに処理を終了します。メモが空の場合には、taraiの計算に入ります。x<=yであれば結果はyなので、それをメモに追加して終了します。

上記以外の場合に、再帰の計算を行います。まず、内側の3つのtaraiをバックグラウンドのジョブで計算します。

    (sh taraip.sh $(( ${1} - 1 )) ${2} ${3})&
    (sh taraip.sh $(( ${2} - 1 )) ${3} ${1})&
    (sh taraip.sh $(( ${3} - 1 )) ${1} ${2})&

3つのジョブが終わるのをwaitコマンドで待ち、その後に結果をメモから読み出します。

    x=$(mc_get "$(( ${1} - 1 )),${2},${3}")
    y=$(mc_get "$(( ${2} - 1 )),${3},${1}")
    z=$(mc_get "$(( ${3} - 1 )),${1},${2}")

このx,y,zを外側のtaraiに食わせます。

    (sh taraip.sh ${x} ${y} ${z})&

先ほどと同様に、waitでジョブの終了を待ってから、結果を読み出し、これを新しい結果としてメモに書きます。

ソースコード全体

taraip.sh
#!/bin/sh

. ./memcached.sh

echo "${1} ${2} ${3}" >&2
mc_open
if [ -z $(mc_get "${1},${2},${3}") ]; then
  if [ "${1}" -gt "${2}" ]; then
    (sh taraip.sh $(( ${1} - 1 )) ${2} ${3})&
    children=$!
    (sh taraip.sh $(( ${2} - 1 )) ${3} ${1})&
    children="${children} $!"
    (sh taraip.sh $(( ${3} - 1 )) ${1} ${2})&
    children="${children} $!"
    wait ${children}
    x=$(mc_get "$(( ${1} - 1 )),${2},${3}")
    y=$(mc_get "$(( ${2} - 1 )),${3},${1}")
    z=$(mc_get "$(( ${3} - 1 )),${1},${2}")
    (sh taraip.sh ${x} ${y} ${z})&
    wait $!
    r=$(mc_get "${x},${y},${z}")
    mc_set "${1},${2},${3}" 300 ${r}
  else
    mc_set "${1},${2},${3}" 300 ${2}
  fi
fi
mc_close

実行結果

実行します。

$ time sh taraip.sh 8 4 0 2>/dev/null

他の端末からプロセスを見てみると

$ ps u -C sh
USER       PID %CPU %MEM    VSZ   RSS TTY      STAT START   TIME COMMAND
nihongi  27786  0.0  0.0 113180  1520 pts/0    S+   19:34   0:00 sh taraip.sh 8 4 0
nihongi  27787  0.0  0.0 113180   608 pts/0    S+   19:34   0:00 sh taraip.sh 8 4 0
nihongi  27790  0.0  0.0 113180  1516 pts/0    S+   19:34   0:00 sh taraip.sh 7 4 0
nihongi  27791  0.0  0.0 113180  1516 pts/0    S+   19:34   0:00 sh taraip.sh 3 0 8
nihongi  27793  0.0  0.0 113180   604 pts/0    S+   19:34   0:00 sh taraip.sh 7 4 0
nihongi  27794  0.0  0.0 113180   604 pts/0    S+   19:34   0:00 sh taraip.sh 3 0 8
nihongi  27802  0.0  0.0 113180  1516 pts/0    S+   19:34   0:00 sh taraip.sh 6 4 0
nihongi  27803  0.0  0.0 113180  1520 pts/0    S+   19:34   0:00 sh taraip.sh 2 0 8
nihongi  27804  0.0  0.0 113180  1520 pts/0    S+   19:34   0:00 sh taraip.sh 3 0 7
nihongi  27807  0.0  0.0 113180  1520 pts/0    S+   19:34   0:00 sh taraip.sh 7 3 0
nihongi  27808  0.0  0.0 113180   604 pts/0    S+   19:34   0:00 sh taraip.sh 6 4 0
nihongi  27809  0.0  0.0 113180   608 pts/0    S+   19:34   0:00 sh taraip.sh 3 0 7
nihongi  27810  0.0  0.0 113180   608 pts/0    S+   19:34   0:00 sh taraip.sh 7 3 0
nihongi  27811  0.0  0.0 113180   608 pts/0    S+   19:34   0:00 sh taraip.sh 2 0 8
(以下省略)

たくさん立ち上がっています。各プロセスがtelnetでmemcachedに接続してるので、ちゃんと動くか心配になります。tarai(8,4,0)では意外と早く終わりました。結果はmemcachedにtelnetして見ます。

real    0m3.089s
user    0m4.829s
sys     0m3.231s
$ telnet localhost 11211
Trying ::1...
Connected to localhost.
Escape character is '^]'.
get 8,4,0
VALUE 8,4,0 0 1
8
END

ちゃんと結果が入っていました。続けてもう一回実行してみると、

$ time sh taraip.sh 8 4 0 2>/dev/null

real    0m0.006s
user    0m0.002s
sys     0m0.002s

爆速です。(これぞキャッシュヒット!!!)

8 4 0くらいが限界みたい

tarai(12, 6, 0)をやってみたらこのざまです。

taraip.sh: fork: retry: Resource temporarily unavailable
taraip.sh: fork: retry: Resource temporarily unavailable
./memcached.sh: fork: retry: No child processes
taraip.sh: fork: retry: Resource temporarily unavailable
./memcached.sh: fork: retry: No child processes
./memcached.sh: fork: retry: No child processes

プロセスをforkできなくなって、ぐだぐだになりました。止めるにはpkill -f "sh taraip.sh"を実行します。1台だとtarai(8, 4, 0)くらいが限界のようです。台数増やして、shコマンドをsshで飛ばせばもっと行けると思いますが、それは今後の課題に取っておきます。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0