これ、現在知られている中で最強のたらい回しアルゴリズムだと思われます。
404 Blog Not Found:Cで強引にたらいを後回し - a-higutiさんのコメント以前、同じことを考えたことがあります。 で、出た結論が → http://ml.tietew.jp/cppll/cppll/article/10669
オリジナルのC版はリンク先をご覧頂くとして、JavaScriptに移植したものが、以下です。
function laziest_tarai(x, y, zx, zy, zz){
return x <= y ? y
: laziest_tarai(tarai(x - 1, y, z),
tarai(y - 1, z, x),
tarai(zx, zy, zz) - 1, x, y)
}
function tarai(x, y, z){
return x <= y ? y
: laziest_tarai(tarai(x - 1, y, z),
tarai(y - 1, z, x),
z - 1, x, y)
}
クリックして
tarai(100,50,0) =
time: seconds
tarai(100,50,0) =
time: seconds
相変わらずSafariは再帰の深さにやかましいのでerrorが出ますが、Firefoxだと私のMacBook Proでわずか0.005秒、Operaでも0.015秒でした。
単に最速というだけではなく、コードがエレガントなので他にも移植しやすい。その意味でも最強です。単純再帰を相互再帰にして速くするというのもすばらしい。
実は、私もこの方法は知っていました。が、今まで書いていなかったのは、たらいネタでどこまで引っ張れるかなという興味もあったから。いつかは書くつもりでしたが、ご本人降臨とあってはもう「がめて」おくわけにも行きません。
それにしても、この役立たずなはずの関数の芳醇さときたら!単純再帰に始まって、メモ化や遅延評価を経て、相互再帰に至る。たらい回しというのは悪いことの代表のように思われますが、最も偉大な例外がこれでしょう。竹内先生ありがとうございました。
竹内先生への感謝ついでに。このたらい回し、実はバージョンが二つあります。最後にzを返すかyを返すか。このあたりのことは、以下で言及されています。
オリジナルの方がy、John McCarthy版がzを返すのですが、奥行きの深さはyを返すオリジナル版の方が上です。でも、tak()といった場合はzを返す方がよく知られているようで、Wikipedia(en)のバージョンもそうでした。気になったので追補しておきましたが、どなたか日本語版作ってきぼんぬ。
Dan the Yet Another Tarai Mawasser
これだって立派なアルゴリズムですがな。
>「non-strictな関数をユーザが定義できない
>言語でどうやってそれに近いことを実現するか」といった今回
>の話題
今回の話題は「最強のたらいまわし」でしょ。