竹内関数といえばベンチマークによく使われる関数です。普通に書くと爆発的な回数の関数呼び出しが発生します。
function tarai(x, y, z) {
if (x <= y) {
return y;
} else {
return tarai(
tarai(x - 1, y, z),
tarai(y - 1, z, x),
tarai(z - 1, x, y)
);
}
}
例えばtarai(10,5,1)なら55229回、tarai(15,5,1)だと実に356426301回もの関数コールが発生します。
竹内関数を高速に解くには、メモ化と遅延評価が知られています。メモ化については解説も多いので、ここでは遅延評価での解き方を考えます。
JavaScriptは先行評価の言語ですので、無理やり遅延評価を行うにはクロージャで引数をラップすることになります。
function tarai(x, y, z) {
function _tarai(x, y, z) {
if (x() <= y()) {
return y();
} else {
return _tarai(
function(){ return _tarai(function(){ return x() - 1 }, y, z)},
function(){ return _tarai(function(){ return y() - 1 }, z, x)},
function(){ return _tarai(function(){ return z() - 1 }, x, y)}
);
}
}
return _tarai(
function(){ return x },
function(){ return y },
function(){ return z }
);
}
遅延評価版では、関数コールを抑えることができます。たとえばさっきのtarai(15,5,1)でも356426301回から281回に激減します。おそらく一瞬で答えが返ってくるのではないでしょうか。
CoffeeScriptで読みやすく
しかしJavaScriptでクロージャをこれほど多用すると、読みにくいですね。そこでCoffeeScript版を考えてみました。
tarai = (x, y, z) ->
_tarai = (x, y, z) ->
if x() <= y()
y()
else
_tarai(
->_tarai (->x() - 1), y, z
->_tarai (->y() - 1), z, x
->_tarai (->z() - 1), x, y
)
_tarai (->x), (->y), (->z)
console.log tarai 15,5,1
だいぶすっきりしました。->の優先順位的に、いくつかカッコでくくらなければならない部分があるのが残念なところです。
x()やy()を再利用するように、クロージャをメモ化すれば更に速くなります。
tarai = (x, y, z) ->
memo = {}
_tarai = (x, y, z) ->
xx = x()
yy = y()
if xx <= yy
yy
else
xx--
yy--
memo[xx] = (->xx) unless memo[xx]?
memo[yy] = (->yy) unless memo[yy]?
_tarai(
->_tarai memo[xx], y, z
->_tarai memo[yy], z, x
->_tarai (->z() - 1), x, y
)
_tarai (->x), (->y), (->z)
keyword: CoffeeScript