let x =0;while(true){if(x >2){return x;}else{
x +=1;}}
どうでしょう?条件分岐を組み込んだ式 f を渡すことで 何か実用的な式を組み立てられそうな気がしてきた と思いませんか?
実用的な計算例: 階乗計算
いよいよ不動点コンビネータを使った実用的な例を見ていきましょう。
0以上の自然数 n の階乗 fact(n)を計算してみます。
まず階乗関数 fact を定義するための補助関数 _fact を次のように定義します。
const _fact = next => n => n ===1?1: n *next(n -1);
これを fix に与えて展開してみましょう。
const fix = f =>(g =>g(g))(h =>f(y =>h(h)(y)));// fix(f) = f(y => fix(f)(y))const _fact = next => n => n ===1?1: n *next(n -1);fix(_fact)
→ (f(y =>fix(f)(y)))(_fact)
→ _fact(y =>fix(_fact)(y))
→ (next => n => n ===1?1: n *next(n -1))(y =>fix(_fact)(y))
→ n => n ===1?1: n *(y =>fix(_fact)(y))(n -1)
const fix2 = f =>(g =>g(g))(h =>f((x, y)=>h(h)(x, y)));const _gcd = next =>(m, n)=> n ===0? m :next(n, m % n);const gcd =fix2(_gcd);gcd(1071,1029);// => 21
const fix = f =>(g =>g(g))(h =>f(x =>h(h)(x)));const _gcd = next => m => n => n ===0? m :next(n)(m % n);const gcd =fix(_gcd);gcd(1071)(1029);// カリー化によって呼び出し方が変わるので注意// => 21
const fix = f =>(g =>g(g))(h =>f(x =>h(h)(x)));const _gcd = next =>([m, n])=> n ===0? m :next([n, m % n]);const gcd =fix(_gcd);gcd([1071,1029]);// タプル渡しで呼び出す// => 21
has メソッドは、値が Set 内にあるかどうかをチェックします。
これは、以前に Set に追加された要素のほとんどを確認するよりも平均すると高速なアプローチを使用します。
特に、 Array オブジェクトの length が Set オブジェクトの size と等しい場合、平均して Array.prototype.includes メソッドより速くなります。
$ deno bench example.js
CPU | Apple M2 Pro
Runtime | Deno 2.1.1(aarch64-apple-darwin)
file:///Users/todays_mitsui/works/temp/example.js
benchmark time/iter (avg) iter/s (min … max) p75 p99 p995
-------------------------- ----------------------------------------------------------------------------
Array.prototype.includes 3.9 ms 258.6(3.7 ms … 4.3 ms)3.9 ms 4.3 ms 4.3 ms
するとこのように結果が表示されます。
では具体的に比較してみましょう。
Array.prototype.includes vs in 演算子 vs Set.prototype.has
Array.prototype.includes と in 演算子 と Set.prototype.has の実行にかかる時間を比べます。
計測に使ったコードは ここ にあります。
要素数1,000,000件の Array と Object と Set を作って比較しています。
$ deno bench array_vs_object_vs_set.js
CPU | Apple M2 Pro
Runtime | Deno 2.1.1(aarch64-apple-darwin)
file:///Users/todays_mitsui/works/temp/array_vs_object_vs_set.js
benchmark time/iter (avg) iter/s (min … max) p75 p99 p995
-------------------------- ----------------------------------------------------------------------------
Array.prototype.includes 3.1 ms 317.5(2.9 ms … 3.7 ms)3.4 ms 3.6 ms 3.7 ms
in operator 15.9 ns 62,780,000(15.7 ns … 34.0 ns)15.8 ns 18.5 ns 19.2 ns
Set.prototype.has 13.1 ns 76,210,000(13.0 ns … 15.8 ns)13.1 ns 14.1 ns 14.6 ns
単位を揃えてみると、
time/iter (avg)
iter/s
Array.prototype.includes
3.1 ms
317.5
in operator
0.0000159 ms
62,780,000.0
Set.prototype.has
0.0000131 ms
76,210,000.0
というわけで圧倒的に Set.prototype.has が速いようです。
Object から in 演算子で探すのもかなり速いですね。
Object と Set の初期化を加味した計測
先ほどの計測では Array, Object, Set を作る時間は計測せず、検索にかかる時間のみを対象にしていました。
では任意の Array が与えられたとき、検索のために Object や Set を初期化するところからやらないといけないようなシチュエーションではどうでしょうか。
そのシチュエーションを想定するなら Object や Set の初期化を計測に含めるべきですね。
$ deno bench array_vs_object_vs_set_2.js
CPU | Apple M2 Pro
Runtime | Deno 2.1.1(aarch64-apple-darwin)
file:///Users/todays_mitsui/works/temp/array_vs_object_vs_set_2.js
benchmark time/iter (avg) iter/s (min … max) p75 p99 p995
-------------------------- ----------------------------------------------------------------------------
Array.prototype.includes 4.0 ms 247.4(4.0 ms … 4.2 ms)4.0 ms 4.2 ms 4.2 ms
in operator 109.0 ms 9.2(96.1 ms … 153.1 ms)110.4 ms 153.1 ms 153.1 ms
Set.prototype.has 84.8 ms 11.8(72.4 ms … 146.7 ms)76.8 ms 146.7 ms 146.7 ms
はい、初期化の時間を加味すると in 演算子も Set.prototype.has も遅いという結果になりました。
先ほどの結果と合わせてまとめると、
検索
初期化 + 検索
Array.prototype.includes
3.1 ms
-
in operator
0.0000159 ms
109.0 ms
Set.prototype.has
0.0000131 ms
84.8 ms
このように。
数回だけ検索するだけであれば、Object や Set を作らず愚直に Array.prototype.includes を使ったほうがトータルで速くなりそうです。
数十回以上の検索を繰り返すのであれば初期化のコストを払ってでも Object や Set を作ったほうが有利になります。
Object と Set の初期化のコストを測ってみる
せっかくなので Array から Object や Set を作るのにかかる時間を測ってみます。
要素数が10件~1,000,000件の場合で見てみましょう。
$ deno bench array_from.js
CPU | Apple M2 Pro
Runtime | Deno 2.1.1(aarch64-apple-darwin)
file:///Users/todays_mitsui/works/temp/array_from.js
benchmark time/iter (avg) iter/s (min … max) p75 p99 p995
-------------------- ----------------------------------------------------------------------------
Object.keys 131.1 ms 7.6(122.1 ms … 160.5 ms)135.8 ms 160.5 ms 160.5 ms
Set.prototype.keys 1.5 ms 657.1(1.4 ms … 2.2 ms)1.5 ms 2.1 ms 2.2 ms
要素数
Object -> Array
Set -> Array
1,000,000
131.1 ms
1.5 ms
意外にも Set から Array を作る方が Object から作るのに比べて80倍ほど速いという結果になりました。
まとめ
Set から要素を検索するのは確かに速い、ただし Set を作るのにかなりの時間がかかる。
少し残念な結果でした。