竹内関数を遅延評価で高速化してみた(JavaScript/Node.js/ES2015/ES6)

竹内関数(Wikipedia)というのがある。

JavaScript (Node.js) で竹内関数を実装してみた。
遅延評価の技術を使って高速化した。

普通に竹内関数を実装すると遅い

普通に実装した。
もちろん普通に遅かった。使い物にならない。
tarai(14, 7, 0)で2.4秒、
tarai(15, 7, 0)で16秒くらいだ。

普通版の竹内関数

'use strict';

// tarai(x: number, y: number, z: number): number;
const tarai = (x, y, z) => x <= y ? y :
	tarai(tarai(x - 1, y, z),
	      tarai(y - 1, z, x),
	      tarai(z - 1, x, y));

bench('takeuchi tarai', tarai, 10, 5, 0);
bench('takeuchi tarai', tarai, 12, 6, 0);
bench('takeuchi tarai', tarai, 14, 7, 0);
bench('takeuchi tarai', tarai, 15, 5, 0);
bench('takeuchi tarai', tarai, 15, 7, 0);

function bench(nm, f, x, y, z) {
	const s = nm + '(' + [x, y, z].join(', ') + ')';
	for (var i = 0; i < 3; ++i)
		console.time(s), console.log(s, f(x, y, z)), console.timeEnd(s);
}

実行結果。すぐに遅くなってしまう。
大きな数字を引数に渡してみるなどしたら遅過ぎて結果が計算できない。

普通版の実行結果

takeuchi tarai(10, 5, 0) 10
takeuchi tarai(10, 5, 0): 2.941ms
takeuchi tarai(10, 5, 0) 10
takeuchi tarai(10, 5, 0): 1.851ms
takeuchi tarai(10, 5, 0) 10
takeuchi tarai(10, 5, 0): 1.445ms
takeuchi tarai(12, 6, 0) 12
takeuchi tarai(12, 6, 0): 50.904ms
takeuchi tarai(12, 6, 0) 12
takeuchi tarai(12, 6, 0): 49.392ms
takeuchi tarai(12, 6, 0) 12
takeuchi tarai(12, 6, 0): 67.476ms
takeuchi tarai(14, 7, 0) 14
takeuchi tarai(14, 7, 0): 2383.500ms
takeuchi tarai(14, 7, 0) 14
takeuchi tarai(14, 7, 0): 2368.144ms
takeuchi tarai(14, 7, 0) 14
takeuchi tarai(14, 7, 0): 2371.349ms
takeuchi tarai(15, 5, 0) 15
takeuchi tarai(15, 5, 0): 11738.412ms
takeuchi tarai(15, 5, 0) 15
takeuchi tarai(15, 5, 0): 11746.249ms
takeuchi tarai(15, 5, 0) 15
takeuchi tarai(15, 5, 0): 11718.303ms
takeuchi tarai(15, 7, 0) 15
takeuchi tarai(15, 7, 0): 16075.906ms
takeuchi tarai(15, 7, 0) 15
takeuchi tarai(15, 7, 0): 16162.424ms
takeuchi tarai(15, 7, 0) 15
takeuchi tarai(15, 7, 0): 16036.595ms

遅延評価版を実装してみた

簡単に記述するためアロー関数を使った。
竹内関数の場合、最初の2つの引数x, yはすぐに値が必要なので、遅延評価する必要はない。
最後の引数のzだけを遅延評価できる様に値または関数にして、値が必要となった時点で計算することにした。
※竹内関数用に最適化した

tarai(1000, 500, 0)で16ミリ秒、
tarai(10000, 5000, 0)で1.4秒、
tarai(20000, 10000, 0)で6秒くらい。
(2.8GHzのCPU)
2万以上の引数だとRangeError: Maximum call stack size exceededだね。

遅延評価版の竹内関数

'use strict';

// tarai(x: number, y: number, z: number | function): number;
function tarai(x, y, z) {
	if (x <= y) return y;
	if (typeof z === 'function') z = z();
	return tarai(tarai(x - 1, y, z),
	             tarai(y - 1, z, x),
	       () => tarai(z - 1, x, y));
}

bench('takeuchi tarai', tarai, 10, 5, 0);
bench('takeuchi tarai', tarai, 12, 6, 0);
bench('takeuchi tarai', tarai, 14, 7, 0);
bench('takeuchi tarai', tarai, 15, 5, 0);
bench('takeuchi tarai', tarai, 16, 8, 0);
bench('takeuchi tarai', tarai, 100, 50, 0);
bench('takeuchi tarai', tarai, 1000, 500, 0);
bench('takeuchi tarai', tarai, 5000, 2500, 0);
bench('takeuchi tarai', tarai, 10000, 5000, 0);
bench('takeuchi tarai', tarai, 14000, 7000, 0);
bench('takeuchi tarai', tarai, 16000, 8000, 0);
bench('takeuchi tarai', tarai, 18000, 9000, 0);
bench('takeuchi tarai', tarai, 19000, 9500, 0);
bench('takeuchi tarai', tarai, 20000, 10000, 0);

function bench(nm, f, x, y, z) {
	const s = nm + '(' + [x, y, z].join(', ') + ')';
	for (var i = 0; i < 3; ++i)
		console.time(s), console.log(s, f(x, y, z)), console.timeEnd(s);
}

遅延評価版の実行結果

takeuchi tarai(10, 5, 0) 10
takeuchi tarai(10, 5, 0): 1.529ms
takeuchi tarai(10, 5, 0) 10
takeuchi tarai(10, 5, 0): 0.115ms
takeuchi tarai(10, 5, 0) 10
takeuchi tarai(10, 5, 0): 0.052ms
takeuchi tarai(12, 6, 0) 12
takeuchi tarai(12, 6, 0): 0.052ms
takeuchi tarai(12, 6, 0) 12
takeuchi tarai(12, 6, 0): 0.236ms
takeuchi tarai(12, 6, 0) 12
takeuchi tarai(12, 6, 0): 0.049ms
takeuchi tarai(14, 7, 0) 14
takeuchi tarai(14, 7, 0): 0.093ms
takeuchi tarai(14, 7, 0) 14
takeuchi tarai(14, 7, 0): 0.031ms
takeuchi tarai(14, 7, 0) 14
takeuchi tarai(14, 7, 0): 0.035ms
takeuchi tarai(15, 5, 0) 15
takeuchi tarai(15, 5, 0): 0.023ms
takeuchi tarai(15, 5, 0) 15
takeuchi tarai(15, 5, 0): 0.024ms
takeuchi tarai(15, 5, 0) 15
takeuchi tarai(15, 5, 0): 0.023ms
takeuchi tarai(16, 8, 0) 16
takeuchi tarai(16, 8, 0): 0.023ms
takeuchi tarai(16, 8, 0) 16
takeuchi tarai(16, 8, 0): 0.025ms
takeuchi tarai(16, 8, 0) 16
takeuchi tarai(16, 8, 0): 0.352ms
takeuchi tarai(100, 50, 0) 100
takeuchi tarai(100, 50, 0): 0.613ms
takeuchi tarai(100, 50, 0) 100
takeuchi tarai(100, 50, 0): 0.290ms
takeuchi tarai(100, 50, 0) 100
takeuchi tarai(100, 50, 0): 0.284ms
takeuchi tarai(1000, 500, 0) 1000
takeuchi tarai(1000, 500, 0): 15.600ms
takeuchi tarai(1000, 500, 0) 1000
takeuchi tarai(1000, 500, 0): 16.155ms
takeuchi tarai(1000, 500, 0) 1000
takeuchi tarai(1000, 500, 0): 14.151ms
takeuchi tarai(5000, 2500, 0) 5000
takeuchi tarai(5000, 2500, 0): 400.499ms
takeuchi tarai(5000, 2500, 0) 5000
takeuchi tarai(5000, 2500, 0): 298.066ms
takeuchi tarai(5000, 2500, 0) 5000
takeuchi tarai(5000, 2500, 0): 305.332ms
takeuchi tarai(10000, 5000, 0) 10000
takeuchi tarai(10000, 5000, 0): 1405.529ms
takeuchi tarai(10000, 5000, 0) 10000
takeuchi tarai(10000, 5000, 0): 1326.405ms
takeuchi tarai(10000, 5000, 0) 10000
takeuchi tarai(10000, 5000, 0): 1316.814ms
takeuchi tarai(14000, 7000, 0) 14000
takeuchi tarai(14000, 7000, 0): 2421.281ms
takeuchi tarai(14000, 7000, 0) 14000
takeuchi tarai(14000, 7000, 0): 2451.464ms
takeuchi tarai(14000, 7000, 0) 14000
takeuchi tarai(14000, 7000, 0): 2416.913ms
takeuchi tarai(16000, 8000, 0) 16000
takeuchi tarai(16000, 8000, 0): 3211.284ms
takeuchi tarai(16000, 8000, 0) 16000
takeuchi tarai(16000, 8000, 0): 3237.209ms
takeuchi tarai(16000, 8000, 0) 16000
takeuchi tarai(16000, 8000, 0): 3219.880ms
takeuchi tarai(18000, 9000, 0) 18000
takeuchi tarai(18000, 9000, 0): 4781.217ms
takeuchi tarai(18000, 9000, 0) 18000
takeuchi tarai(18000, 9000, 0): 4759.622ms
takeuchi tarai(18000, 9000, 0) 18000
takeuchi tarai(18000, 9000, 0): 4780.485ms
takeuchi tarai(19000, 9500, 0) 19000
takeuchi tarai(19000, 9500, 0): 5021.622ms
takeuchi tarai(19000, 9500, 0) 19000
takeuchi tarai(19000, 9500, 0): 5024.893ms
takeuchi tarai(19000, 9500, 0) 19000
takeuchi tarai(19000, 9500, 0): 5046.295ms
takeuchi tarai(20000, 10000, 0) 20000
takeuchi tarai(20000, 10000, 0): 5840.195ms
takeuchi tarai(20000, 10000, 0) 20000
takeuchi tarai(20000, 10000, 0): 6149.193ms
takeuchi tarai(20000, 10000, 0) 20000
takeuchi tarai(20000, 10000, 0): 6021.613ms

※ちなみにメモ化では引数が大きい時にメモリ不足でうまくいかなかった(1万とか2万とかやってみ?)

参考文献

• ハッカーの遺言状──竹内郁雄の徒然苔 第18回：問題児も悪くない - サイボウズ式
• 竹内関数 - Wikipedia
• 竹内関数をメモ化とか遅延で高速化してみた - Qiita
• CoffeeScriptで竹内関数を解く - Architect Note
• たらいを回すならHaskell - 404 Blog Not Found - Dan Kogai (小飼 弾)