コンピュータ科学 深掘り– category –
本線の外側。アルゴリズム、計算機の仕組み、OSの理論。
-
コンピュータ科学 深掘り
自作KVストアで理屈を実測する — CSの到達作品
コンピュータ科学深掘りコースの到達作品です。新しい知識は足しません。これまで別々に書いてきた計算量・線形探索・ハッシュ表・衝突・LRUを、1つの小さなKVストア(キーと値の入れ物)に束ねて、自分の手で作ります。まず配列に持って線形探索する遅い版を書き、10万件で1回引くのに何マイクロ秒かかるかを実測します。次にハッシュ索引を自作して桁違いに速くなることを測り、衝突とリサイズを扱い、最後にLRUで容量を守りながらヒット率を測ります。締めは1枚の表で「計算量の予想と実測の数字が一致する」ことを確かめます。RedisやMapの中で起きているのは、これと同じことです。 -
コンピュータ科学 深掘り
文字コードとUTF-8 — 化けたのは読み方だけ
Windows で作った CSV を VM にコピーして開いたら、全部読めない記号になっていました。ファイルが壊れたのだと思って作り直しましたが、壊れていたのは私の読み方でした。この記事では ASCII の表を実際に出して「文字は数字だった」ところから始め、iconv でわざと化けさせ、xxd でバイト列そのものを見て「中身は1バイトも変わっていない」ことを確かめます。そのあと Unicode のコードポイントと UTF-8 の関係を Node.js で測り、絵文字の文字数が数えられない理由(サロゲートペア・書記素クラスタ・NFC / NFD)まで進みます。最後に BOM で JSON のパースとシェルスクリプトを実際に壊して直し、HTML・HTTP・MySQL・Node.js のどこで文字コードを宣言するのかを1枚の表にします。作業は VM の ~/cslab/enc の中だけで行い、最後に消します。 -
コンピュータ科学 深掘り
2進数と浮動小数点 — 0.1+0.2が0.3にならない
合計金額が1円だけ足りない、という不具合を出したことがあります。原因は割引後の単価が小数だったこと、そして掛けた結果が 434.99999999999994 になっていたことでした。この記事では VM の中の Node.js で、2進数の読み方、ビット演算7種類、そして 0.1 + 0.2 が 0.30000000000000004 になる理由を、64ビットのビット列を実際に取り出して最後まで説明しきります。さらに金額を壊さない持ち方(整数と BigInt)、toFixed が計算を直していないことの実演、エンディアンでバイト順が逆になるところまで手を動かして確かめます。最後に対数・指数・階乗の伸び方を表にして、次の回の計算量へ橋を架けます。 -
コンピュータ科学 深掘り
計算量と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枚の表にまとめます。 -
コンピュータ科学 深掘り
CPUの仕組みを自作する — 足し算しかしていない
CPUを「魔法の箱」で終わらせないために、手元で全部作って動かします。2の補数をJavaScriptで組んで引き算を足し算に置き換え、AND・OR・XOR・NOTの4関数だけから8ビット加算器を作って0〜255の全組み合わせでJavaScriptの + と一致することを確認します。命令が10個だけの極小CPUシミュレータを書いてフェッチ・デコード・実行を1サイクルずつ表示させ、レジスタ版とメモリ版でアクセス回数を数えます。最後に本物のCPUを lscpu と gcc -S で覗き、キャッシュの効き方を実測して、割り込みの回数が増える瞬間を vmstat で見ます。 -
コンピュータ科学 深掘り
スタックとキュー — call stack size exceeded の正体
終わらない再帰を書いて Maximum call stack size exceeded を出したとき、私は「JavaScriptが疲れた」くらいの理解でした。実際は、自分がその日 push と pop で作ったのと同じものが、言語の内側で溢れていただけでした。この記事では VM の中に ~/cslab/sq を作り、スタックとキューを手で書きます。全部 O(1) であることを実測し、わざとエラーを出して積める段数を数え、スタックトレースが下から読める理由を出力で確かめます。キューは配列の shift() で作ってから 10万件で測り、先頭の位置を持つ形に直して同じ測定で速くなることを見ます。最後に setTimeout と Promise の実行順を出して、イベントループもキューだったことを確かめて全部消します。 -
コンピュータ科学 深掘り
バランス木とB木 — 100万件が3段で届く
二分探索木は「毎回半分に絞れるから速い」と習いました。ところが 1,2,3,... と並んだ 10,000件を入れたら、高さが 10,000 になりました。木ではなく連結リストです。この記事では VM の中に ~/cslab/btree を作り、その症状を実測してから AVL木を自分で書きます。回転を図で暗記せず、単回転と二重回転を実装して、同じ 10,000件で高さが 14 に収まることを確かめます。赤黒木は実装せずルールだけ読み、B木がなぜデータベースの索引なのかを段数の計算で出します。最後にトライでオートコンプリートを作り、スキップリストと比べて、全部消します。 -
コンピュータ科学 深掘り
ハッシュテーブル — 10万件のincludesで止まる
10万件の配列に includes を書いたら画面が止まりました。Set の has に変えたら一瞬で終わり、そのとき私は「Setは速い」で納得してしまいました。この記事では VM の中に ~/cslab/hash を作り、その差が何倍あるのかを実測してから、ハッシュ関数とハッシュテーブルを自分の手で書きます。バケットの中身を表示して、どのキーがどこに入ったかを目で見て、わざと衝突させて O(1) が O(n) に落ちる瞬間を表にします。負荷率とリサイズを実装して、リサイズが起きた15回だけ平均の3万倍遅くなることを測ります。最後にハッシュと暗号化とエンコードを sha256sum と base64 で並べて確かめ、Object と Map と Set と WeakMap の使い分けを表にして全部消します。 -
コンピュータ科学 深掘り
ヒープとLRUキャッシュ — 10件欲しいだけで100万件ソート
ランキングの上位10件を出すために、私は100万件を毎回まるごとソートしていました。必要なのは10件なのに、残りの999990件を丁寧に並べ替えていたわけです。この記事では VM の中に ~/cslab/heap を作り、サイズ10のヒープを手で書いて、全部ソートする版と実測で比べます。ヒープが「木なのにポインタを1つも使わず、配列1本で持てる」ことを添字の計算で確かめ、内部配列を表示してヒープがソートされていないことを見ます。後半はLRUキャッシュを素朴な O(n) 版から O(1) 版へ直し、容量を変えながらヒット率を実測します。最後に LRU・LFU・MFU・FIFO・ランダムを同じアクセス列で走らせ、LFU が「昔たくさん使われたもの」に居座られて負ける瞬間を数字で出してから、全部消します。