アルゴリズム– tag –
-
コンピュータ科学 深掘り
計算量とO記法 — データが10倍で100倍遅くなる
テストデータ100件では一瞬だった処理が、本番の10万件で固まりました。原因は「遅いコード」ではなく「データが増えると時間が何倍になるか」を見ていなかったことでした。この記事ではVMの中に小さな計測台を作り、O(1)・O(log n)・O(n)・O(n log n)・O(n²)・O(2ⁿ) の6つを実際に走らせて、nを10倍にしたとき時間が何倍になるかを表にします。定数を無視する理由も、nとn²/100が逆転する交差点を実測して確かめます。最後に、同じO(n)でもメモリのアクセス順で数倍変わることを測り、なぜ最後は必ず測るのかまで見ます。 -
コンピュータ科学 深掘り
配列と連結リスト — 先頭への追加が数百倍遅い
配列の末尾に1万件足すのは一瞬なのに、先頭に1万件足したら固まりました。原因は「データの置き方」で、この記事ではそれをVMの中のNode.jsで実測して確かめます。push と unshift を10万回ずつ回して差を測り、動的配列の「2倍に取り直して全部コピー」を自分で実装してコピー回数を数え、単方向・双方向の連結リストを自分の手で書きます。そのうえで、同じ O(n) の全走査を配列と連結リストで比べると教科書どおりにならないことを実測で確認し、CPUキャッシュという理由まで降りていきます。最後に「どの操作にどちらが向くか」を、計算量と実測の両方が入った1枚の表にまとめます。 -
コンピュータ科学 深掘り
ソートアルゴリズム6種 — 並べ替えたら10が2の前に来た
3件の配列を並べ替えただけで 1, 10, 2 が返ってきたとき、私は自分のコードのどこかにバグがあると思って30分探しました。バグはありませんでした。この記事では VM の中に ~/cslab/sort を作り、バブル・選択・挿入・マージ・クイック・ヒープの6つを自分で書きます。同じ4種類のデータで、時間だけでなく比較回数と書き込み回数を数えて1枚の表にします。すでに並んでいるデータで自作クイックソートを走らせて Maximum call stack size exceeded を出し、軸の選び方を変えて直るところまでやります。同点データを並べ替えて「安定」が何のことかを出力で見て、最後に V8 の sort と全部を測り比べて ~/cslab を消します。 -
コンピュータ科学 深掘り
二分探索木と3つの巡回 — 木にしたのに一直線になる
二分探索木は「探索が O(log n) になるデータ構造」だと覚えていました。実際に 1,2,3,... を順に入れてみたら、木の高さが 39999 になり、1件探すのに平均 20000 回比較していました。木ではなく、右に伸びた連結リストになっていたのです。この記事では VM の中に ~/cslab/tree を作り、insert / search / min / max / delete を自分で書き、削除の3パターンを図で確かめます。3つの巡回を並べて in-order だけがソート済みで出てくることを見て、幅優先はキューで書きます。最後に並んだデータを入れて高さと探索時間を実測し、再帰版の巡回を 20000 件で落として、明示的なスタックのループ版に書き換えて全部消します。 -
プログラム
1万件で100倍になる — 計算量とO記法を測る
O記法は見たことがあるけれど説明はできない、という状態を終わらせます。数学は使いません。配列から1件探す処理を1000件から100万件まで測って、時間が件数に比例することを表で見る。Mapに変えると件数を増やしても変わらないことを見る。二重ループの重複検出が1000件から1万件で100倍になるところを実測し、Setで書き換えて桁を戻す。二分探索が100万件を20回で終えることをカウンタで数え、並べ替えのコストと、nが小さいときは二重ループのほうが速いという実測まで。証明はしません。全部、自分のVMで数字を出します。
1