CodeIQ｜ITエンジニアのための実務スキル評価サービスで挑戦した問題、@nkawagashira 川頭 信之さんからの言語不問の問題、
アッカーマンの再帰関数で計算爆発を体験してみよう
の解答の解説、設問6の解説：アッカーマンの呪い - スピード冒険野郎のブログ
設問6の解説：アッカーマンの呪い http://t.co/QhK1VVumPx
— 川頭信之 スピード冒険野郎 (@nkawagashira) June 25, 2013
CodeIQに投稿した問題6の解答を解説します。
問題
昔、アッカーマンという人（残念ながらミカサという妙齢の女性ではありません）がいました。
その人の手帳には以下のような式が書かれていました。
が出てたので、挑戦した時を思い出しながら書いてみた。
アッカーマン関数の(3, 4)、(4, 1)、(4, 2)の場合をpython3.3とJavaScriptで求めてみることに。(ただしpythonは10秒以内で、JavaScriptは指定した秒数で。)
pythonの場合。
コード(BBEdit)
sample.py
#!/usr/bin/env python3.3
#-*- coding: utf-8
import time
def timer(s):
global start
if time.time() - start > s:
raise Exception("時間かかり過ぎ！({0}秒)".format(s))
def ack(m, n):
timer(10)
if m == 0:
return n + 1
if n == 0:
return ack(m - 1, 1)
return ack(m - 1, ack(m, n - 1))
for m, n in [(3, 4), (4, 1), (4, 2)]:
print("ack({0}, {1}) = ".format(m, n), end="")
start = time.time()
try:
print("{0} ({1:.5f}秒)".format(ack(m, n), time.time() - start))
except Exception as err:
print("\n{0}: {1}".format(err.__class__.__name__, err))
入出力結果(Terminal)
$ ./sample.py ack(3, 4) = 125 (0.00883秒) ack(4, 1) = RuntimeError: maximum recursion depth exceeded in comparison ack(4, 2) = RuntimeError: maximum recursion depth exceeded in comparison $
(3, 4)は求めることができたけど、(4, 1)、(4, 2)では再帰関数が深すぎという例外で求めることができず。
ということで、sysモジュールのsetrecursionlimitメソッドを使い、sys.setrecursionlimit( 10000000 )で上限を引き上げてから求めてみる。
コード(BBEdit)
sample.py
#!/usr/bin/env python3.3
#-*- coding: utf-8
import time, sys
sys.setrecursionlimit( 10000000 )
def timer(s):
global start
if time.time() - start > s:
raise Exception("時間かかり過ぎ！({0}秒)".format(s))
def ack(m, n):
timer(10)
if m == 0:
return n + 1
if n == 0:
return ack(m - 1, 1)
return ack(m - 1, ack(m, n - 1))
for m, n in [(3, 4), (4, 1), (4, 2)]:
print("ack({0}, {1}) = ".format(m, n), end="")
start = time.time()
try:
print("{0} ({1:.5f}秒)".format(ack(m, n), time.time() - start))
except Exception as err:
print("\n{0}: {1}".format(err.__class__.__name__, err))
入出力結果(Terminal)
$ ./sample.py ack(3, 4) = 125 (0.00900秒) ack(4, 1) = Exception: 時間かかり過ぎ！(10秒) ack(4, 2) = Exception: 時間かかり過ぎ！(10秒) $
上限を引き上げても、10秒以内には求めることができず。でも、再帰が深すぎる例外はなくなったし、時間をかければ、あるいはもっと高性能のマシンなら10秒以内に求まるのかも。
ということで、10秒以内に求めるためにメモ化を使って高速化を試みることに。
コード(BBEdit)
sample.py
#!/usr/bin/env python3.3
#-*- coding: utf-8
import time, sys
sys.setrecursionlimit( 10000000 )
def timer(s):
global start
if time.time() - start > s:
raise Exception("時間かかり過ぎ！({0}秒)".format(s))
memo = []
for m in range(5):
memo.append([None for x in range(1000000)])
def ack(m, n):
timer(10)
if memo[m][n]:
return memo[m][n]
if m == 0:
memo[m][n] = n + 1
return memo[m][n]
if n == 0:
memo[m][n] = ack(m - 1, 1)
return memo[m][n]
memo[m][n] = ack(m - 1, ack(m, n - 1))
return memo[m][n]
for m, n in [(3, 4), (4, 1), (4, 2)]:
print("ack({0}, {1}) = ".format(m, n), end="")
start = time.time()
try:
print("{0} ({1:.5f}秒)".format(ack(m, n), time.time() - start))
except Exception as err:
print("\n{0}: {1}".format(err.__class__.__name__, err))
入出力結果(Terminal)
$ ./sample.py ack(3, 4) = 125 (0.00050秒) ack(4, 1) = 65533 (0.40701秒) Segmentation fault: 11 $
(4, 1)の場合を求めることができた。けど、(4, 2)の場合はpythonごと落ちた。>_< (Segmentation fault: 11)
リスト(memo)が大きくなりすぎて、メモリー確保で何らかの問題があるからかなぁ。
ということで、(4, 2)を素早く計算して、あるいは普通じゃない方法で求める方法は分からず。時間がかかってもいいなら上記の再帰の上限を引き上げてメモ化を使わない方法で求めることができるのかも。
JavaScriptの場合。
(Firefoxだと、メモ化の場合にブラウザが固まる可能性があるので注意！(Firefoxのメモ化の場合に速度が遅い原因は分からず><動作確認したのはSafari、Firefox、Chrome(いずれもMac版)。WindowsのIEだとどうなるか気になってたり。。)
秒数:
コード(BBEdit)
var s = parseFloat($('#t0').val()),
timer = function (s) {
if ((new Date() - start) / 1000 > s) {
s = (new Date() - start) / 1000;
throw {
type: "エラー",
message: "時間かかり過ぎ！(" + s + "秒)"
};
}
},
ack = function (m, n) {
timer(s);
if (m === 0) {
return n + 1;
}
if (n === 0) {
return ack(m - 1, 1);
}
return ack(m - 1, ack(m, n - 1));
},
args = [[3, 4], [4, 1], [4, 2]],
arg,
result = "",
start,
i,
max,
m,
n;
for (i = 0, max = args.length; i < max; i += 1) {
arg = args[i];
m = arg[0];
n = arg[1];
result += "ack(" + m + ", " + n + ") = ";
start = new Date();
try {
result += ack(m, n) + "(" + ((new Date() - start) / 1000) + "秒)\n";
} catch (e) {
result += e.type + ": " + e.message + "\n";
}
}
$('#pre0').text(result);
メモ化。
コード(BBEdit)
var s = parseFloat($('#t0').val()),
timer = function (s) {
if ((new Date() - start) / 1000 > s) {
s = (new Date() - start) / 1000;
throw {
type: "エラー",
message: "時間かかり過ぎ!(" + s + "秒)"
};
}
},
memo = [],
ack = function (m, n) {
timer(5);
if (memo[m][n]) {
return memo[m][n];
}
if (m === 0) {
memo[m][n] = n + 1;
return memo[m][n];
}
if (n === 0) {
memo[m][n] = ack(m - 1, 1);
return memo[m][n];
}
memo[m][n] = ack(m - 1, ack(m, n - 1));
return memo[m][n];
},
args = [[3, 4], [4, 1], [4, 2]],
arg,
result = "",
start,
i,
max,
m,
n;
for (i = 0; i < 5; i += 1) {
memo.push([]);
}
for (i = 0, max = args.length; i < max; i += 1) {
arg = args[i];
m = arg[0];
n = arg[1];
result += "ack(" + m + ", " + n + ") = ";
start = new Date();
try {
result += ack(m, n) + "(" + ((new Date() - start) / 1000) + "秒)\n";
} catch (e) {
result += e.type + ": " + e.message + "\n";
}
}
$('#pre1').text(result);
SafariとChromeでスタックのサイズの上限設定違うみたい。JavaScriptでもPythonのsys.setrecursionlimit( 10000000 )みたいに最大値引き上げる方法あるのかなぁ。あるなら、Chromeでもメモ化でアッカーマン関数の引数が(4, 1)の場合を求めることが出来るのかも。
0 コメント:
コメントを投稿