再帰– tag –
-
コンピュータ科学 深掘り
スタックとキュー — call stack size exceeded の正体
終わらない再帰を書いて Maximum call stack size exceeded を出したとき、私は「JavaScriptが疲れた」くらいの理解でした。実際は、自分がその日 push と pop で作ったのと同じものが、言語の内側で溢れていただけでした。この記事では VM の中に ~/cslab/sq を作り、スタックとキューを手で書きます。全部 O(1) であることを実測し、わざとエラーを出して積める段数を数え、スタックトレースが下から読める理由を出力で確かめます。キューは配列の shift() で作ってから 10万件で測り、先頭の位置を持つ形に直して同じ測定で速くなることを見ます。最後に setTimeout と Promise の実行順を出して、イベントループもキューだったことを確かめて全部消します。 -
コンピュータ科学 深掘り
二分探索木と3つの巡回 — 木にしたのに一直線になる
二分探索木は「探索が O(log n) になるデータ構造」だと覚えていました。実際に 1,2,3,... を順に入れてみたら、木の高さが 39999 になり、1件探すのに平均 20000 回比較していました。木ではなく、右に伸びた連結リストになっていたのです。この記事では VM の中に ~/cslab/tree を作り、insert / search / min / max / delete を自分で書き、削除の3パターンを図で確かめます。3つの巡回を並べて in-order だけがソート済みで出てくることを見て、幅優先はキューで書きます。最後に並んだデータを入れて高さと探索時間を実測し、再帰版の巡回を 20000 件で落として、明示的なスタックのループ版に書き換えて全部消します。 -
コンピュータ科学 深掘り
再帰とメモ化 — メモを1行足したら一瞬で終わった
フィボナッチを素直に書いたら fib(45) が返ってきませんでした。原因はアルゴリズムではなく、同じ引数を何千万回も計算し直していたことです。呼び出し回数を実際に数え、Map に覚えさせる1行を足して fib(90) が 0.04ms で返るところまでを実測します。あわせて末尾再帰が JavaScript では救いにならないことをスタックを溢れさせて確認し、N-Queen とナイトの巡回で「置く・進む・戻る」を書き、ナップサックを総当たり・メモ化再帰・動的計画法の3通りで測って並べます。最後に順列と組み合わせを列挙し、誕生日のパラドックスをシミュレーションしてハッシュの衝突に繋げます。
1