女性向けエンジニアスクール
コンピューターサイエンス理論の導入スライド
コンピューターサイエンス理論 - 2進数から10進数への変換
0 と 1 の列を数として読む
並んでいるのは 0 と 1 だけですが、桁ごとに決まった重みがあります。ON になっている桁の重みを足し合わせた数が、そのまま10進数の値です。
手で足しても同じ数になることを、次の図解で確かめます。
文字列で持っている2進数は、parseInt の第2引数に 2 を渡すと10進数になります。
parseInt("10101010", 2); // 1701 / 4
コンピューターサイエンス理論 - 2進数から10進数への変換
重みを足して読む
スライダーを動かして、色が付いた桁の重みだけが足し算に並ぶのを見てください。
- 重みは右端の 1 から倍々に増えて、左端が 128。8桁すべてが 1 なら合計は 255 になる
- 式に出てくるのは色が付いた桁だけで、0 の桁は足し算に一切現れない
- 255 に合わせて +1 を入れると、繰り上がった9桁目が枠の外へ消えて 0 に戻る
2 / 4
考えてみよう外しても進めます
2進数 11010000 は10進数でいくつでしょうか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
コンピューターサイエンス理論 - 2進数から10進数への変換
読み替えの早見表
よく出てくる並びを覚えておくと、途中の足し算を省けます。8桁ちょうどで区切られている値は、境目として頭に入れておくと便利です。
8桁で表せるのは 0 から 255 まで。これを越える値には9桁目が要ります。
| 2進数 | 10進数 |
|---|---|
| 00000001 | 1 |
| 00001111 | 15 |
| 00010000 | 16 |
| 10000000 | 128 |
| 11111111 | 255 |
4 / 4
コンピューターサイエンス理論 - 10進数から2進数への変換
2 で割り続けて余りを積む
10進数を 2 で割り、出てきた余りを下の桁から積み上げると2進数になります。割り算を止めるのは、商が 0 になったときです。
余りの列がどう桁に対応するのかを、次の図解で逆から確かめます。
JavaScript は toString(2) で一発ですが、中でやっているのは 2 で割り続ける手続きです。
(13).toString(2); // "1101"1 / 4
コンピューターサイエンス理論 - 10進数から2進数への変換
作りたい数から桁を決める
作りたい10進数にスライダーを合わせて、どの桁が ON になったかを逆から読んでください。
- 128 より小さい数では左端が 0 のまま。上の桁から「入るか入らないか」で決まっていく
- 偶数のあいだ右端は 0。右端の桁は 2 で割った余りそのものになっている
- 1 ずつ上げると右端から順に繰り上がる。2 で割り続ける手順を逆再生した形になる
2 / 4
考えてみよう外しても進めます
10進数 100 を8桁の2進数で書くとどれでしょうか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
割り算の跡をたどる
商が 0 になるまで割り、余りを下から読み上げます。ループを回した記録をそのまま並べると、桁の順番が逆さまに出てくる理由が見えます。
n % 2下の桁から出る余りMath.floor(n / 2)次の桁へ進む割り算の記録
| n | 商 | 余り |
|---|---|---|
| 100 | 50 | 0 |
| 50 | 25 | 0 |
| 25 | 12 | 1 |
| 12 | 6 | 0 |
| 6 | 3 | 0 |
| 3 | 1 | 1 |
| 1 | 0 | 1 |
余りを下から読むと 1100100
unshift で先頭に積んでいるのは、あとから出た余りほど上の桁だからです。
4 / 4
コンピューターサイエンス理論 - ビットAND演算でフラグ判定
設定を1つの整数に押し込める
真偽値をいくつも並べる代わりに、1つの整数の各桁へ設定を押し込められます。ある機能が有効かどうかを調べるのが AND の役目です。
この & がビット列に何をしているのかを、次の図解で8桁ぶん並べて見ます。
perm & WRITE が 0 かどうかだけを見ます。0 以外なら、その桁は立っています。
const READ = 1, WRITE = 2, EXEC = 4;
const perm = 5;
if (perm & WRITE) { /* 書き込める */ }1 / 4
コンピューターサイエンス理論 - ビットAND演算でフラグ判定
AND で桁を取り出す
AND を選んだままマスクのスライダーを動かして、一番下の行に何が残るかを見てください。
- 残るのはマスクが 1 の桁だけ。x が 1 でも、マスクが 0 の桁は必ず落ちる
- マスクを 0 まで下げると結果は 0、逆に 255 まで上げると x がそのまま出てくる
- マスクを 8 や 16 のような1桁だけの値にすると、その桁が立っているかの判定になる
2 / 4
考えてみよう外しても進めます
図の x は 106 です。106 & 16 の結果はいくつでしょうか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
コンピューターサイエンス理論 - ビットAND演算でフラグ判定
AND の使いどころ
AND は「見る」と「削る」に効く演算です。判定に使うときは、結果が 0 以外かどうかだけを見ます。
桁を立てる側の操作は、次のレッスンの OR と XOR で扱います。
| やりたいこと | 書き方 |
|---|---|
| 特定の桁が立っているか調べる | perm & FLAG が 0 以外か |
| 下位4桁だけ取り出す | value & 15 |
| 特定の桁を落とす | perm & ~FLAG |
| 偶数か奇数かを見る | n & 1 |
4 / 4
コンピューターサイエンス理論 - OR / XOR でフラグを操作する
読むだけでなく書き換える
AND で読み出した設定を、今度は書き換えます。OR は桁を立て、XOR は立っている桁と消えている桁を入れ替えます。
2つの演算が同じマスクでどう割れるのかを、次の図解で押し比べます。
OR は何度かけても結果が変わりませんが、XOR は同じ値を2回かけると元へ戻ります。
let perm = 5;
perm = perm | 2; // 書き込みを許可する
perm = perm ^ 4; // 実行の可否を反転する1 / 4
コンピューターサイエンス理論 - OR / XOR でフラグを操作する
立てる演算と裏返す演算
マスクを固定したまま OR と XOR を押し比べて、3段目の変わり方の違いを見てください。
- OR では 1 が減ることがない。x で立っていた桁は、マスクが何であれ残る
- XOR はマスクが 1 の桁を入れ替えるので、もともと立っていた桁は消える
- マスクを 255 にすると、OR は8桁すべてが 1 になり、XOR は8桁すべてが反転する
2 / 4
考えてみよう外しても進めます
図の x は 106 で、8 にあたる桁はすでに立っています。マスク 8 で OR と XOR をかけると結果はどうなるでしょうか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
3つの書き換えを並べる
立てる、反転する、落とすの3つが揃えば、フラグの読み書きはひととおり書けます。落とすときだけ AND と反転を組みます。
| 8すでに 1 なら変わらない^ 81 と 0 が入れ替わる結果
| 式 | 2進数 | 10進数 |
|---|---|---|
| x | 01101010 | 106 |
| x | 8 | 01101010 | 106 |
| x ^ 8 | 01100010 | 98 |
| x & ~8 | 01100010 | 98 |
8 の桁が立っているので、OR は何も起きず XOR だけが動いた
同じマスクでも、対象の桁が立っているかどうかで OR と XOR の結果は割れます。
4 / 4
コンピューターサイエンス理論 - popcount で 1 のビット数を数える
立っている桁を数える
整数の中で 1 になっている桁の個数を求める処理です。集合の要素数や、2つの値がどれだけ違うかを測るハミング距離が、この数え上げ1つで出せます。
この 4 という数は図の一番下にも出ます。次の枚で確かめてください。
n & 1 で右端を見て、n >>= 1 で1桁ずつ右へ寄せます。0 になったら終わりです。
let count = 0;
for (let n = 106; n > 0; n >>= 1) count += n & 1;
// count は 41 / 4
コンピューターサイエンス理論 - popcount で 1 のビット数を数える
1 の個数を追う
演算とマスクを変えながら、図の一番下に出る立っているビットの個数を追ってください。
- x は 01101010 で 1 が4個。AND でマスクを狭めるほど、この数は 4 から減っていく
- OR では個数が減らない。マスクを 255 まで上げると 8 個で頭打ちになる
- XOR はマスクが 1 の桁を入れ替えるので、個数が増えることも減ることもある
2 / 4
考えてみよう外しても進めます
x は 106 で 1 が4個です。106 ^ 255 では 1 が何個になるでしょうか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
数え方で回数が変わる
右へずらしながら数える書き方は、値の大きさに関係なく桁数ぶん回ります。立っている桁だけを追う書き方にすると、1 が少ない値ほど速く終わります。
右へ1桁ずつずらして見る
n &= n - 1 を繰り返す
4桁ごとの対応表を引く
8桁の値を数えたときの反復回数です。棒の長さは回数そのままで、目盛りは加工していません。
n &= n - 1 は一番右の 1 を1個ずつ消す書き方で、Brian Kernighan のテクニックと呼ばれます。
4 / 4
コンピューターサイエンス理論 - シフト演算で 2 倍 / 半分
桁をまるごとずらす
各桁を左右にずらすだけの演算です。左へ1つずらすと 2 倍、右へ1つずらすと切り捨てた半分になります。
8ビットの箱で左へずらし続けるとどうなるかを、次の図解で見ます。
右シフトは割り算と違って小数を切り捨てます。負の数では 0 側ではなく小さい側へ寄る点に注意してください。
25 << 1; // 50
25 >> 1; // 12
-25 >> 1; // -131 / 4
コンピューターサイエンス理論 - シフト演算で 2 倍 / 半分
左へずらすと何が起きるか
左シフト量のスライダーを 1 から順に上げて、左端の桁の行き先を追ってください。
- 1回ずらすごとに値が 2 倍になり、空いた右端には 0 が入ってくる
- x を大きくしてからずらすと、左へ出ていった桁が点線の赤枠になって消える
- シフト量を 8 まで上げると8桁すべてが出ていって、結果は 0 になる
2 / 4
考えてみよう外しても進めます
8ビットで持っている 200 を1桁だけ左へずらすと、結果はいくつになるでしょうか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
左と右で捨てられるものが違う
左シフトは上の桁が箱からあふれ、右シフトは下の桁が切り捨てられます。どちらも消えた情報は戻らないので、桁数の見積もりが要ります。
& 2558ビットに収め直すx >> 38 で割るのと同じ結果
| 式 | 計算の意味 | 結果 |
|---|---|---|
| x << 1 | 2 倍 | 400 だが8ビットでは 144 |
| x >> 1 | 2 で割って切り捨て | 100 |
| x >> 3 | 8 で割って切り捨て | 25 |
左はあふれて消え、右は下の桁が消える
2 のべき乗での掛け算と割り算だけがシフトに置き換わります。3 倍や 10 で割る計算には使えません。
4 / 4
コンピューターサイエンス理論 - 16 進数から 10 進数への変換
1桁で 0 から 15 まで
16 進数は1桁で 0 から 15 までを表します。a から f が 10 から 15 にあたり、2進数のちょうど4桁分が1桁に収まります。
4桁ずつのまとまりが本当に1桁になるのかを、次の図解で確かめます。
色コードやメモリアドレスでよく見かける書き方です。読めるようになると、下の桁だけ切り出す作業が一気に楽になります。
parseInt("2f", 16); // 47
(255).toString(16); // "ff"1 / 4
コンピューターサイエンス理論 - 16 進数から 10 進数への変換
8桁を4桁ずつに割る
スライダーを 171 に合わせて、8桁を左4桁と右4桁に分けて読んでください。
- 171 は 10101011。左4桁の 1010 が a、右4桁の 1011 が b にあたる
- 左4桁の重みは 128, 64, 32, 16 で、合計しても 16 の倍数にしかならない
- 255 まで上げると8桁すべてが 1 になり、16 進では ff の2桁で書ける
2 / 4
考えてみよう外しても進めます
16 進数 2f は10進数でいくつでしょうか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
コンピューターサイエンス理論 - 16 進数から 10 進数への変換
4桁ずつの対応表
この対応さえ入っていれば、2進数と16進数は10進数を経由せずに行き来できます。左から4桁ずつ切って、1文字ずつ置き換えるだけです。
8 以上かどうかで左端の桁が決まるので、まずそこを見ると読み間違えません。
| 16 進1桁 | 2進4桁 |
|---|---|
| 0 | 0000 |
| 7 | 0111 |
| 8 | 1000 |
| a | 1010 |
| f | 1111 |
4 / 4
コンピューターサイエンス理論 - 第 1 章まとめクイズ
第 1 章の振り返り
桁の重みで数を読む話と、その桁を1つずつ操作する話をつなげてきました。どちらも土台にあるのは同じ8桁のビット列です。
クイズに入る前に、3つの演算の効き方をもう一度図で見比べます。
この章の演算は、すべて同じ1本のビット列に対する読み書きです。ばらばらの知識には見えても、見ている場所は同じです。
106; // 01101010
106 & 8; // 立っているかを見る
106 | 16; // 立てる
106 ^ 255; // すべて裏返す
106 << 1; // 2 倍にする1 / 3
コンピューターサイエンス理論 - 第 1 章まとめクイズ
3つの演算を見比べる
AND、OR、XOR を順に押して、同じマスクでも結果がどう割れるかを見比べてください。
- AND では 1 が増えず、OR では 1 が減らない。両方向へ動くのは XOR だけ
- マスクを 255 にすると、AND は x のまま、OR は全部 1、XOR は全部反転になる
- 一番下に出る個数は、popcount のレッスンで数えたものと同じ数
2 / 3
コンピューターサイエンス理論 - 第 1 章まとめクイズ
次の章へ
数と桁の扱いが済んだので、次はその数が何を表しているのかに移ります。文字コードと真偽値のロジックが第 2 章の中心です。
間違えた問題は、対応するレッスンの図解に戻って手を動かすのが一番早い復習です。
| この章で身につけたこと | 次の章でつながる先 |
|---|---|
| 桁の重みで2進数を読む | 文字を番号として読む |
| AND で桁を取り出す | AND を真偽値のかつとして読む |
| XOR で桁を裏返す | XOR をどちらか一方として読む |
| シフトで 2 倍と半分 | UTF-8 が1文字を何バイトに分けるか |
3 / 3
コンピューターサイエンス理論 - 文字 → ASCII コード
画面の文字にも番号が振ってある
画面に出ている文字は、コンピュータの中では 1 文字ごとに決まった番号を持っています。その番号を取り出すと、文字を数字と同じように足したり比べたりできるようになります。
この 65 という数字がどこから来たのかを、次の図解で自分で動かして確かめます。
1 文字を渡すと、その文字に割り当てられた番号が返ってきます。
const code = "A".charCodeAt(0);
console.log(code); // 651 / 4
コンピューターサイエンス理論 - 文字 → ASCII コード
文字と番号を並べて見る
見せ方を「文字」にして、数字のスライダーを動かしてください。
- 上段の 1 文字と、その真下の数字が同じ列にそろう。これが文字の番号
- 隣の列は番号が 1 ずつ増えるだけで、文字も表の並び順どおりに入れ替わる
- 33 より下や 126 より上まで動かすと文字が「—」になり、対応表に無い所に当たる
2 / 4
考えてみよう外しても進めます
大文字の Z の番号は 90 です。小文字の a の番号は 90 からいくつ離れているでしょうか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
コンピューターサイエンス理論 - 文字 → ASCII コード
覚えておくと得をする番号
全部を暗記する必要はありません。区切りになる 3 か所だけ頭に入れておくと、あとは連続していることから計算で出せます。
大文字と小文字はきっちり 32 離れています。この差が次のレッスンで効いてきます。
| 文字 | 番号 |
|---|---|
| 0 (数字のゼロ) | 48 |
| 9 | 57 |
| A | 65 |
| Z | 90 |
| a | 97 |
| z | 122 |
4 / 4
コンピューターサイエンス理論 - コード → 文字
番号から文字を作る
前のレッスンとは逆向きの変換です。番号を渡すと、その番号に割り当てられた文字が返ってきます。計算した結果の番号をそのまま文字に戻せるので、暗号や連番の生成で使います。
番号を自由に動かすと何が起きるのかを、次の図解で端まで振り切って確かめます。
行きも帰りも、間にあるのは同じ 1 枚の対応表です。
const ch = String.fromCharCode(65);
console.log(ch); // "A"1 / 4
コンピューターサイエンス理論 - コード → 文字
番号を動かして文字を作る
見せ方を「文字」にしたまま、数字のスライダーを端まで振り切ってください。
- 数字を動かすと上段の文字だけが差し替わり、下段はいつも 0 から 255 の数字のまま
- 見せ方を色や音にしても下段の形は変わらない。文字だけが特別なわけではない
- 端まで振り切ると「決めた範囲の外は、そもそも表せません」と出る
2 / 4
考えてみよう外しても進めます
大文字の番号から小文字の番号を作りたいとき、いくつ足せばよいでしょうか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
番号を経由して文字を作る
文字そのものを直接いじる関数を探すより、いったん番号にしてから計算し、また文字に戻すほうが素直に書けます。
String.fromCharCode番号から文字へupper.charCodeAt(0)文字から番号へ+ 32番号のまま計算途中経過
| 段階 | 値 |
|---|---|
| 元の文字 | C |
| 番号にする | 67 |
| 32 を足す | 99 |
| 文字に戻す | c |
真ん中の 2 行はただの足し算です。文字の知識はいりません。
行きと帰りの 2 つの関数が対になっている、と覚えておけば十分です。
4 / 4
コンピューターサイエンス理論 - UTF-8 のバイト長を返す
1 文字が 1 バイトとは限らない
文字数とバイト数は別のものです。英字は 1 文字 1 バイトですが、日本語は 1 文字で 3 バイトを使います。この違いを知らないまま長さを数えると、保存や通信の途中で足りなくなります。
この 3 個がどう区切られているのかを、次の図解で区切り線ごと見ます。
見た目は 1 文字でも、中身は 3 個の数字が並んでいます。
const bytes = new TextEncoder().encode("あ");
console.log(bytes.length); // 31 / 4
コンピューターサイエンス理論 - UTF-8 のバイト長を返す
同じバイト列を別の規則で読む
読む規則の 3 つのボタンを順に押して、括り線の切れ目がどこに動くか見てください。
- 真ん中に並ぶ 6 個のバイトは、どのボタンを押しても一切変わらない
- UTF-8 は 3 バイトずつ括るので、6 バイトがちょうど 2 文字に戻る
- Shift_JIS は 2 バイトずつ括るため切れ目がずれ、別の文字が 4 つ並ぶ
2 / 4
考えてみよう外しても進めます
半角英字 3 文字と日本語 2 文字をつなげた文字列を UTF-8 で保存すると、何バイトになるでしょうか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
コンピューターサイエンス理論 - UTF-8 のバイト長を返す
何バイトになるかは番号で決まる
文字の種類を見て判定しているわけではありません。文字に割り当てられた番号がどの範囲に入るかだけで、使うバイト数が決まります。
境目は 128 と 2048 と 65536 です。この 3 つの数字だけ覚えておけば場合分けが書けます。
| 文字の番号の範囲 | UTF-8 でのバイト数 |
|---|---|
| 0 から 127 (英数字と記号) | 1 バイト |
| 128 から 2047 (ラテン文字の拡張など) | 2 バイト |
| 2048 から 65535 (ひらがな、漢字、ハングル) | 3 バイト |
| 65536 以上 (絵文字や一部の漢字) | 4 バイト |
4 / 4
コンピューターサイエンス理論 - AND / OR の真理値表
条件をつなぐ 2 つの向き
AND は「両方そろったら」、OR は「どちらか一方でもあれば」を表します。言葉で読むと似ていますが、通る組み合わせの数がまるで違います。
どのくらい違うのかは、通る組み合わせを数えると一目で分かります。
上は 2 つとも満たす人だけ、下はどちらかに当てはまる人が通ります。
const canEnter = age >= 18 && hasTicket;
const isFree = isChild || isSenior;1 / 4
コンピューターサイエンス理論 - AND / OR の真理値表
AND と OR で通る行を数える
演算のボタンで AND と OR を押し替えて、true の行がどれだけ増えるか見てください。
- A と B の組み合わせは全部で 4 通りしか無い。この表で全部を見尽くせる
- AND は緑になる行が 1 つだけ。OR に切り替えると一気に 3 つに増える
- 表の下に「4 通り中いくつ」が出るので、数え間違いをしなくて済む
2 / 4
考えてみよう外しても進めます
同じ A と B に対して、OR が true になる行数は AND が true になる行数より何行多いでしょうか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
コンピューターサイエンス理論 - AND / OR の真理値表
どちらを使うか迷ったら
条件を日本語に直すと、どちらを使うかはほぼ決まります。「かつ」なら AND、「または」なら OR です。
短絡評価のおかげで、左に安全確認を置けば右で落ちません。この順番は自分で決められます。
| やりたいこと | 書き方 |
|---|---|
| 両方そろったときだけ通す | a && b |
| どちらか一方でも当てはまれば通す | a || b |
| 3 つ以上を全部そろえる | a && b && c |
| 左が false なら右を見ない | && は短絡評価をする |
| 左が true なら右を見ない | || は短絡評価をする |
4 / 4
コンピューターサイエンス理論 - NOT / XOR の真理値表
ひっくり返すのと、食い違いを見るの
NOT は真偽をそのままひっくり返します。XOR は 2 つを見比べて、食い違っているときだけ true になります。値が変わったかどうかの判定は、ほとんどがこの XOR です。
ひっくり返した結果が別の見慣れた式と同じになる、という所を次の図解で見ます。
下の行は、食い違いをひっくり返して「そろっている」を作っています。
const changed = a !== b;
const same = !(a !== b);1 / 4
コンピューターサイエンス理論 - NOT / XOR の真理値表
否定を掛けて列を裏返す
XOR を選んでから「全体を否定する」を入れて、列がどう変わるか見てください。
- XOR は 2 つが食い違う真ん中の 2 行だけが true になる
- 否定を入れると見出しに ! が付き、true と false が総入れ替わりになる
- 同時に右へ A === B の列が出て、否定した XOR とまったく同じ並びになる
2 / 4
考えてみよう外しても進めます
XOR の結果をひっくり返した !(a !== b) は、どの式と同じ意味になるでしょうか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
否定は外に出すと読みにくい
同じ意味でも、書き方によって読みやすさは変わります。否定を外側にかぶせた式は、頭の中で 2 回ひっくり返すことになります。
!(a !== b)2 回ひっくり返すa === bそのまま読める4 通りを並べる
| a | b | !(a !== b) | a === b |
|---|---|---|---|
| false | false | true | true |
| false | true | false | false |
| true | false | false | false |
| true | true | true | true |
右の 2 列は 4 行とも一致します。意味は変わっていません。
意味が同じなら、読んで分かるほうを選びます。この置き換えの元になる法則が次のレッスンのあとに出てきます。
4 / 4
コンピューターサイエンス理論 - 含意 (→) を AND/OR/NOT で表現
「ならば」に専用の演算子は無い
「会員ならばチケットが必要」のような決まりごとは、数学では A → B と書きます。プログラミング言語にこの記号はありませんが、NOT と OR だけで同じものが書けます。
この書き換えが本当に合っているのかを、4 通り全部を並べて確かめます。
会員でなければ、その時点で決まりを破りようがないので true です。
const rule = !isMember || hasTicket;1 / 4
コンピューターサイエンス理論 - 含意 (→) を AND/OR/NOT で表現
含意と !A || B を見比べる
演算のボタンで「含意 →」を押して、右に出てくる列と見比べてください。
- 含意だけは否定を入れなくても、右に !A || B の列が最初から並ぶ
- A が false の上 2 行は B を見ずに true。ここが「空虚な真」と呼ばれる所
- false になるのは A が true で B が false の 1 行だけ。約束を破った行はこれしか無い
2 / 4
考えてみよう外しても進めます
A → B が false になるのは、4 通りのうちどの組み合わせでしょうか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
コンピューターサイエンス理論 - 含意 (→) を AND/OR/NOT で表現
含意の言い換え早見
同じことを言い表す形がいくつもあります。どれか 1 つを起点にすれば、残りは機械的に導けます。
対偶は元の式と真偽が完全に一致します。条件が書きにくいときは、ひっくり返して考えると楽になります。
| 書き方 | 読み方 |
|---|---|
| A → B | A ならば B |
| !A || B | A でないか、または B |
| !(A && !B) | A なのに B でない、ということが無い |
| !B → !A | B でないなら A でもない (対偶) |
4 / 4
コンピューターサイエンス理論 - ド・モルガンの法則
否定を内側に入れると演算が入れ替わる
条件全体を否定したいとき、外側に ! を付けたままでは読みにくくなります。否定を内側に配ると、そのついでに && と || が入れ替わります。これがド・モルガンの法則です。
本当に同じなのかは、4 通り全部の並びがそろうかどうかで判定できます。
上と下は同じ意味です。|| が && に変わっている所に注目してください。
const hidden = !(isDraft || isArchived);
const same = !isDraft && !isArchived;1 / 4
コンピューターサイエンス理論 - ド・モルガンの法則
否定を掛けて 2 列をそろえる
AND か OR を選んでから「全体を否定する」を入れて、左右 2 つの列を見比べてください。
- 否定を入れる前は右の列が畳まれていて、比べる相手がそもそも出てこない
- AND を否定すると右に !A || !B が出て、4 行とも同じ並びになる
- OR を否定すると相方は !A && !B に変わる。否定が内側に入ると演算が入れ替わる
2 / 4
考えてみよう外しても進めます
!(a && b) と同じ意味になるのはどれでしょうか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
4 行そろえば同じ式
式が同じ意味かどうかは、覚えているかではなく 4 行並べれば確かめられます。組み合わせが 4 通りしか無いので、全部試すのが一番速い確認方法です。
!(x && y)否定が外側!x || !y否定が内側、演算は反転4 通りを並べる
| x | y | !(x && y) | !x || !y |
|---|---|---|---|
| false | false | true | true |
| false | true | true | true |
| true | false | true | true |
| true | true | false | false |
右の 2 列が 4 行とも一致しているので、この 2 つは同じ式です。
検索条件の除外や権限の判定など、否定が絡む所で毎日のように使う書き換えです。
4 / 4
コンピューターサイエンス理論 - 第2章まとめクイズ
この章で手に入れた道具
文字を番号として扱う話と、条件を組み立てる話の 2 本立てでした。どちらも「見た目の裏に決まった表がある」という同じ形をしています。
クイズに入る前に、真理値表をもう一度だけ自分の手で一巡させておきます。
| 扱ったこと | 覚えておく所 |
|---|---|
| 文字と番号の行き来 | A は 65、a は 97。差は 32 |
| UTF-8 のバイト数 | 境目は 128 と 2048 と 65536 |
| 文字化けの正体 | バイト列ではなく読む規則が違うだけ |
| AND と OR | 4 通り中、true は 1 行と 3 行 |
| 含意 → | !A || B と書ける。false は 1 行だけ |
| ド・モルガン | 否定を内側に入れると && と || が入れ替わる |
1 / 3
コンピューターサイエンス理論 - 第2章まとめクイズ
4 つの演算を一巡させる
AND から含意まで 4 つのボタンを順に押して、true になる行数を思い出してください。
- true になる行数は AND が 1、OR が 3、XOR が 2、含意が 3。並べると全部違う
- 否定トグルを入れると、AND と OR は相方の列が入れ替わって出てくる
- 含意だけは否定しなくても !A || B が並ぶ。専用の演算子がいらない理由がこれ
2 / 3
コンピューターサイエンス理論 - 第2章まとめクイズ
次の章に持っていくもの
ここまでは「1 回の計算で何が起きるか」を見てきました。次の章では、その計算を何回繰り返すことになるのかを数えます。数え方の道具立ては、この章の 4 通りを数えたのと同じです。
次は繰り返しの回数と計算量の話に入ります。ここでの「全部並べて数える」がそのまま土台になります。
| この章で身についたこと | 次の章での効きどころ |
|---|---|
| 組み合わせを全部並べて数える | 処理が何回走るかを数え上げる |
| 条件式を短く書き換える | ループの中の判定を軽くする |
| 短絡評価で右を見ない | 無駄な繰り返しを途中で打ち切る |
| 文字を番号として扱う | 配列の添字として文字を使う |
3 / 3
コンピューターサイエンス理論 - forループの実行回数を返す
回数を数える
ループが何回まわるかは、書いた本人でも意外と外します。まずは回数そのものを返す関数を作って、条件式と刻み幅から回数がどう決まるのかを手で確かめます。
刻み幅を 1 から変えると、この当たり前が急に当たり前でなくなります。
count は n と同じ値になります。ここが今回の出発点です。
function countIterations(n) {
let count = 0;
for (let i = 0; i < n; i++) count++;
return count;
}1 / 4
コンピューターサイエンス理論 - forループの実行回数を返す
刻み幅で回数が変わる
step を動かして、range が作る値が何個になるか数えてください。
- step を 2 にすると 0, 2, 4 の 3 個。ループの回数は作られた値の個数そのまま
- step をマイナスにすると並びが降順になるが、個数の数え方は変わらない
- step を 0 にすると値が1つも作れず、ループは1回も動かない
2 / 4
考えてみよう外しても進めます
for (let i = 0; i < 100; i += 5) は何回まわりますか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
n と回数の対応
回数が n に正比例して伸びるとき、この処理は O(n) だと言います。n が何であっても回数が変わらないものは O(1) です。
n = 10
n = 1,000
n = 1,000,000
ループを使わない1行
棒の長さは for が回る回数そのままです。目盛りは加工していないので、n = 1,000,000 以外の3本は押されて線にしか見えません。
O(n) は「n を 10 倍にすると時間も 10 倍になる」という約束です。
4 / 4
コンピューターサイエンス理論 - 入れ子ループの実行回数
ループの中にループを置く
ループの内側にもう1つループを置くと、内側の行は外側と内側のかけ算の回数だけ動きます。この掛け算が、あとで効いてくる伸び方の正体です。
まずは 3×3 の小さな例で、どちらのループが速く回るかを目で追います。
count は n + n ではなく n × n になります。足し算だと思うと桁を外します。
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
count++;
}
}1 / 4
コンピューターサイエンス理論 - 入れ子ループの実行回数
内側と外側のどちらが速いか
1マスずつ進めて、内側と外側のどちらが先に進むか目で追ってください。
- 内側の j が 3 周し終えてから、外側の i がやっと1つ進む
- 3×3 のマスが全部埋まると実行回数は 9 回。n × n のかけ算になっている
- 内側を range(1, 1) にすると1マスも埋まらない。外側だけ回っても中の行は動かない
2 / 4
考えてみよう外しても進めます
n = 100 の2重ループで、いちばん内側の行は何回実行されますか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
n を 10 倍にしてみる
O(n) なら n を 10 倍にすると時間も 10 倍ですが、O(n²) では 100 倍になります。手元で 1 秒だったものが本番で 100 秒になる、という事故はここから起きます。
for (let i = 0; i < n; i++)外側 n 周count++;合計 n × n 回count の値
| n | count |
|---|---|
| 10 | 100 |
| 100 | 10,000 |
| 1,000 | 1,000,000 |
n が 10 倍で count は 100 倍
2重ループを書いたら、n がどこまで大きくなりうるかを必ず確かめます。
4 / 4
コンピューターサイエンス理論 - 線形探索 (O(n))
先頭から順に見ていく
並び方に何の前提も置かないなら、目当ての値を見つける方法は先頭から1つずつ見ていくしかありません。素朴ですが、どんな配列にも使える唯一の手です。
この i が動く様子を、箱を並べた図解でそのままなぞります。
見つかれば途中で抜けますが、無い値を探すと最後まで見ることになります。
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i;
}
return -1;
}1 / 4
コンピューターサイエンス理論 - 線形探索 (O(n))
i が動く先を見る
インデックス i を 0 から動かして、探索が見ていく箱を1つずつなぞってください。
- i を1つ増やすごとに見る箱が1つ右へ動く。これが線形探索の1回ぶん
- i = 4 が最後の箱。ここまでで見つからなければ 5 個すべてを見たことになる
- i を 5 以上に伸ばすと箱そのものが無い。ループの終了条件を1つ間違えるとここへ踏み込む
2 / 4
考えてみよう外しても進めます
100万件の配列を線形探索します。目当ての値が入っていないとき、比較は何回になりますか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
同じ 100万件でも手が違う
線形探索が遅いのではなく、何の前提も持たないぶんの正直な回数です。事前に並べておく、目印を作っておく、という手間を払うと回数は桁ごと落ちます。
先頭から順に見る (線形探索)
並んだ配列を半分ずつ削る (二分探索)
先に目印を作っておく (ハッシュ)
n = 1,000,000 のときの最悪の比較回数です。棒の長さは回数そのままで、下の2本は短すぎて線に見えます。
下 2 つには前提があります。次のレッスンで、まず二分探索の前提を確かめます。
4 / 4
コンピューターサイエンス理論 - 二分探索 (O(log n))
半分ずつ捨てる
配列が小さい順に並んでいるなら、真ん中を1回見るだけで候補の半分を丸ごと捨てられます。捨てた側は二度と見ません。
並んでいることが前提です。並んでいない配列に使うと静かに間違えます。
lo と hi が挟む範囲が候補です。すれ違ったら、その値は無いと決まります。
let lo = 0, hi = arr.length - 1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;1 / 4
コンピューターサイエンス理論 - 二分探索 (O(log n))
候補が減るところを数える
探す値を選んでから、ステップを1つずつ進めて残る候補を数えてください。
- 1回比べるたびに候補が 12 → 6 → 3 と半分に減っていく
- 配列に無い 33 を選ぶと、候補が0個になった時点で見つからないと決まる
- 12 個なら 4 回で決着する。n が倍になっても増える比較は 1 回だけ
2 / 4
考えてみよう外しても進めます
1,024 個の並んだ数から二分探索で探すと、最悪で何回比べますか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
回数の伸び方が違う
n が倍になっても比較は1回しか増えません。これが O(log n) で、データが桁ごと増えても回数はほとんど動かない、という珍しい性質です。
Math.floor((lo + hi) / 2)真ん中を見るlo = mid + 1左半分を丸ごと捨てる最悪の比較回数
| 候補の数 n | 比較回数 |
|---|---|
| 16 | 4 |
| 1,024 | 10 |
| 1,000,000 | 20 |
n が 1,000 倍でも回数は 2 倍
そのかわり、並べる手間を先に払う必要があります。次はその並べ替えを見ます。
4 / 4
コンピューターサイエンス理論 - バブルソート
隣どうしを入れ替え続ける
隣り合う2つを比べて、順番が逆なら入れ替える。これを繰り返すだけで配列は並びます。大きい値が泡のように右端へ浮いていくのでバブルソートと呼ばれます。
比較の回数と交換の回数は別物です。図解では 2 つを分けて数えます。
2重ループです。ここまでで見た O(n²) の形が、そのまま出てきました。
for (let i = 0; i < n - 1; i++) {
for (let j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) swap(arr, j, j + 1);
}
}1 / 4
コンピューターサイエンス理論 - バブルソート
比較と交換を別々に数える
比較を1回ずつ進めて、比較の回数と交換の回数を別々に数えてください。
- 1ステップが隣どうし1組の比較。順番が逆のときだけ交換カウンタが動く
- 1周終わるごとに右端が1つ確定し、次の周の比較は1回ずつ減る
- すでに並んだ配列で始めると交換は0回のまま。それでも比較の回数は変わらない
2 / 4
考えてみよう外しても進めます
5 要素のバブルソートを途中で打ち切らずに最後まで回します。すでに並んでいる配列のとき、比較は何回になりますか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
比較回数の伸び方
比較の回数は n(n-1)/2 で決まります。n が 10 倍になると回数はおよそ 100 倍で、要素数が数千を超えたあたりから待てない領域に入ります。
n = 5
n = 10
n = 100
n = 1,000
棒の長さは比較の回数そのままです。n = 1,000 の1本だけで、上の3本が見えなくなります。
1周で交換が0回だったら打ち切る、という工夫を足すと最良の場合だけ O(n) になります。
4 / 4
コンピューターサイエンス理論 - 配列の最大と最小
1周で答えを持ち歩く
最大値を求めるには、いまのところの一番を変数に持ちながら配列を1周します。並べ替える必要はありません。問題は、その変数を何で始めるかです。
どんな入力で壊れるのか、図解で best の変化を1歩ずつ追って見つけます。
best を 0 で始めています。これで困る入力が1つだけあります。
let best = 0;
for (const x of nums) {
if (x > best) best = x;
}
return best;1 / 4
コンピューターサイエンス理論 - 配列の最大と最小
best が書き換わる瞬間
ステップを進めて、best が書き換わる瞬間だけを拾ってください。
- 書き換わるのは x > best が真になったときだけ。1周につき多くても1回
- 1周する間に比較は要素の数だけ起きる。だから配列を1周する処理は O(n)
- 配列を全部マイナスにすると if が一度も真にならず、初期値の 0 がそのまま答えとして残る
2 / 4
考えてみよう外しても進めます
100 要素の配列から最大と最小を 1 回のループでまとめて求めます。比較はおよそ何回起きますか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
初期値を先頭から取る
0 は「どんな配列にも必ずある値」ではありません。配列の先頭を初期値にすれば、中身がマイナスだけでも答えは狂いません。
nums[0]0 ではなく先頭の値で始めるif (x > best)比較は要素の数だけ入力ごとの答え
| 入力 | best = 0 | best = nums[0] |
|---|---|---|
| [3, 9, 4] | 9 | 9 |
| [-3, -9, -4] | 0 | -3 |
| [] | 0 | エラー |
空配列は別に弾く
どちらの書き方でも計算量は O(n) のままです。壊れるのは正しさのほうです。
4 / 4
コンピューターサイエンス理論 - 累積和で範囲合計
先に足しておく
区間の合計を何度も聞かれるなら、聞かれるたびに足すのは無駄です。先頭からの合計を1度だけ作っておけば、あとは引き算1回で答えが出ます。
この l === 0 の分岐を外すと何が起きるか、図解で実際に踏んでみます。
s を作るのに1周ぶん。そのあとは何回聞かれても引き算1回です。
const s = [arr[0]];
for (let i = 1; i < arr.length; i++) {
s[i] = s[i - 1] + arr[i];
}
const sum = s[r] - (l === 0 ? 0 : s[l - 1]);1 / 4
コンピューターサイエンス理論 - 累積和で範囲合計
引き算1回で出す
l と r を動かして、下段の光る 2 か所だけで区間の合計が出ることを確かめてください。
- 上段を l から r まで足した数と、下段の引き算1回の答えが一致する
- 区間をどれだけ広げても引き算は1回のまま。足す回数は増えない
- l を 0 まで下げると S[l-1] が末尾を指し、エラーも出ないまま答えだけが狂う
2 / 4
考えてみよう外しても進めます
長さ 10万 の配列に、区間合計の問い合わせが 10万回 来ます。毎回その場で足すと、足し算は最悪で何回になりますか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
前処理とクエリを分けて数える
計算量は処理ひとまとめでなく、前処理と1回あたりの問い合わせに分けて数えます。前に1回払っておくと、あとが定数回で済む。累積和はその典型です。
s[i - 1] + arr[i]前の合計に足すだけs[r] - (l === 0 ? 0 : s[l - 1])引き算1回で区間合計10万回 問い合わせたとき
| やり方 | 前処理 | 問い合わせ1回 | 合計 |
|---|---|---|---|
| 毎回その場で足す | なし | O(n) | 100億回 |
| 累積和を先に作る | O(n) | O(1) | 20万回 |
前に1回払うと桁が変わる
同じ答えを何度も聞かれるなら、まず前処理で削れないかを疑います。
4 / 4
コンピューターサイエンス理論 - 第3章まとめクイズ
この章で数えてきたもの
この章では、処理の速さを秒ではなく回数で数えてきました。ループが何回まわるか、比較が何回起きるか。それを n の式で表したものが計算量です。
この伸び方の差が、n が大きくなってからどう効くのかを図解で見ます。
どれも「n が増えたときの伸び方」を言っているだけです。絶対の速さではありません。
// 配列を1周する O(n)
// 2重ループ O(n^2)
// 半分ずつ削る O(log n)
// 前処理してから1回引く O(1)1 / 3
コンピューターサイエンス理論 - 第3章まとめクイズ
伸び方を並べて見る
n を動かして、どの棒が先に天井の線を越えるか見てください。
- n が小さいうちは 3 本の高さに大した差が出ない
- n を 20 まで上げると O(n²) だけが天井を突き抜け、O(log n) はほとんど伸びない
- 計算量の差は n が小さいときではなく、n が大きくなってから効いてくる
2 / 3
コンピューターサイエンス理論 - 第3章まとめクイズ
次の章へ
計算量を下げる手は、たいてい「データの持ち方を変える」ことです。並べておくから二分探索が使え、先に合計を作っておくから引き算1回で済みました。次の章では、その持ち方そのものを扱います。
次の章はスタック、キュー、ハッシュです。どれも「速く取り出すための持ち方」の話になります。
| この章でやったこと | 計算量 |
|---|---|
| 配列を1周して数える / 最大最小を取る | O(n) |
| 線形探索で目当ての値を探す | O(n) |
| 2重ループで全組み合わせを見る | O(n²) |
| バブルソートで並べ替える | O(n²) |
| 並んだ配列を二分探索する | O(log n) |
| 累積和で区間合計を出す | 前処理 O(n) と問い合わせ O(1) |
3 / 3
コンピューターサイエンス理論 - スタック (push/pop) を実装する
入れた口から取り出す
スタックは、物を積み上げた山と同じです。入れるのも取り出すのも一番上だけなので、最後に置いたものが最初に戻ってきます。
1, 2, 3 の順に入れたのに 3 が先に返る。この裏返りがスタックの正体です。
配列の末尾だけを使えば、それがもうスタックです。専用のクラスは要りません。
const s = [];
s.push(1);
s.push(2);
s.push(3);
s.pop(); // 31 / 4
コンピューターサイエンス理論 - スタック (push/pop) を実装する
取り出す口を見る
ステップを進めて、上段のスタックの一番上がどこかを追ってください。
- 太枠が付いているセルが次に出る値。積むたびに太枠は上へ移り、取り出すと1段下がる
- 「出た順」の行に 3, 2, 1 と並ぶ。入れた並びをそのまま裏返した形になる
- 「空の状態から取り出す」を入れると1手目で失敗する。空の pop は値ではなくエラーになる
2 / 4
考えてみよう外しても進めます
空のスタックに push(1), push(2), pop(), push(3) を順に流したあと、もう一度 pop() すると返るのはどれでしょう。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
コンピューターサイエンス理論 - スタック (push/pop) を実装する
覚えることは2つだけ
JavaScript なら配列の末尾操作がそのままスタックになります。使う前に空かどうかを確かめる癖だけ付けてください。
push も pop も末尾しか触らないので、どれだけ積んでも1回あたりの手数は変わりません。
| やりたいこと | 書き方 |
|---|---|
| 上に積む | s.push(v) |
| 上から取り出す | s.pop() |
| 取り出さずに覗く | s[s.length - 1] |
| 空かどうか | s.length === 0 |
4 / 4
コンピューターサイエンス理論 - キュー (enqueue / dequeue) を実装する
並んだ順に返す
キューはレジの行列と同じで、入る口と出る口が別々です。先に並んだ人から順に抜けていくので、入れた並びがそのまま出てきます。
同じ 1, 2, 3 を入れても、スタックは 3 から、キューは 1 から返ります。
末尾に足して先頭から抜く。スタックとの違いは、抜く場所が反対側という一点だけです。
const q = [];
q.push(1);
q.push(2);
q.push(3);
q.shift(); // 11 / 4
コンピューターサイエンス理論 - キュー (enqueue / dequeue) を実装する
入れた順が保たれるところを見る
ステップを進めて、下段のキューの左端がどう入れ替わるかを追ってください。
- 右から入って左から出る。太枠は常に一番左に付いたままで、上段のように動かない
- 「出た順」の下の行は 1, 2, 3。入れた並びと同じ順で、上段のスタックと真逆になる
- 同じ操作列を両方に流しているので、違いは出し入れの口だけだと分かる
2 / 4
考えてみよう外しても進めます
空のキューに 1, 2, 3 を入れ、2 回取り出したあとに 4 を入れました。次に取り出すと返るのはどれでしょう。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
shift は先頭を抜く
配列でキューを書くと、取り出すたびに後ろの要素が1つずつ前へ詰められます。件数が少ないうちは問題になりませんが、詰め直しが起きていることは知っておいてください。
q.shift()先頭を抜くq.push(4)末尾に足す配列の中身
| 時点 | 中身 |
|---|---|
| 最初 | [1, 2, 3] |
| shift のあと | [2, 3] |
| push のあと | [2, 3, 4] |
first には 1 が入ります。
大量に出し入れするときは、先頭位置を添字で持つか専用のキュー実装に切り替えます。
4 / 4
コンピューターサイエンス理論 - カッコのバランス判定 (スタック応用)
閉じカッコは直前の開きと組む
カッコの対応は、いつでも一番内側から閉じていきます。開きカッコを積んでおき、閉じカッコが来たら一番上と合うかを見る。それだけで判定できます。
数を数えるだけでは足りません。開き 1 個と閉じ 1 個でも、順番が逆なら不正です。
閉じカッコの相方は、必ず「まだ閉じていない中で最後に開いたもの」です。だからスタックが効きます。
const PAIR = { ")": "(", "]": "[", "}": "{" };
const stack = [];1 / 4
コンピューターサイエンス理論 - カッコのバランス判定 (スタック応用)
積んで、上から片付ける
ステップを進めて、積み上がってから上の箱が順に片付いていく形を見てください。
- 前半は下へ下へと箱が増える。カッコ判定でいえば開きカッコを積んでいる区間にあたる
- 後半は一番上の箱から順に値が確定して降りてくる。閉じカッコが上と組んで消えていくのと同じ形
- 「停止条件を削除する」を入れると積むだけで降りてこない。閉じカッコが足りない文字列と同じ状態になる
2 / 4
考えてみよう外しても進めます
文字列 ([)] を左から見ていきます。バランスが崩れていると判定できるのは何文字目でしょう。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
判定の3条件
正しいと言えるのは、途中で不一致が起きず、閉じ過ぎもせず、最後にスタックが空になったときだけです。3つのうち1つでも欠けると不正になります。
stack.push(ch)開きは積むstack.pop() !== PAIR[ch]上と組めるかstack.length === 0積み残しゼロ判定結果
| 入力 | 結果 |
|---|---|
| ([{}]) | true |
| ([)] | false |
| (() | false |
| )( | false |
(() は不一致ゼロですが、最後に積み残しが 1 個あるので false です。
空のスタックに pop すると undefined が返るので、閉じ過ぎのケースも同じ 1 行で弾けます。
4 / 4
コンピューターサイエンス理論 - set で重複を除去する
同じ値は1個しか持てない
set は「もう持っているか」をすぐ答えられる入れ物です。同じ値を何度入れても中身は 1 個のままなので、重複除去がそのまま1行で書けます。
set が速いのは、値そのものから入れ場所を決めているからです。その仕組みを次の図解で見ます。
配列で includes を回すと毎回先頭から探し直しますが、set は探さずに置き場所を計算します。
const nums = [3, 1, 3, 2, 1];
const uniq = [...new Set(nums)]; // [3, 1, 2]1 / 4
コンピューターサイエンス理論 - set で重複を除去する
同じ値は同じ場所に落ちる
「入れるキーの数」を増やして、それぞれの値がどの列に入るかを見てください。
- 上の式のとおり、値から番号を計算して入れる列を決めている。だから探さずに置き場所が分かる
- 同じ値をもう一度入れれば計算結果も同じ番号になり、必ず同じ列へ落ちる。これが重複を見つけられる理由
- 「バケット数」を 1 まで下げると全員が同じ列に積み上がり、下の行が最悪ケースの個数を教えてくれる
2 / 4
考えてみよう外しても進めます
配列 [3, 1, 3, 2, 1] を Set に入れて配列へ戻すと、要素の並びはどうなるでしょう。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
コンピューターサイエンス理論 - set で重複を除去する
set でできること
重複除去だけでなく、含まれるかの判定や集合演算も set の得意分野です。書き方を並べておきます。
順序が要らない、重複が要らない、含むか知りたい。この3つが揃ったら set を選びます。
| やりたいこと | 書き方 |
|---|---|
| 重複を消す | [...new Set(arr)] |
| 含むか調べる | s.has(v) |
| 件数を数える | s.size |
| 積集合を作る | [...a].filter((v) => b.has(v)) |
4 / 4
コンピューターサイエンス理論 - map で出現回数を数える
キーごとにカウンタを持つ
出現回数を数えるときは、値そのものをキーにして数を貯めます。並べ替えも比較も要らず、1回なめるだけで全部の件数が揃います。
この「まだ無いキーを引いたらどうなるか」が、言語ごとに一番差が出るところです。
初回のキーはまだ存在しないので、そのまま足すと壊れます。0 を補ってから足すのが定石です。
const counts = {};
for (const ch of "banana") {
counts[ch] = (counts[ch] ?? 0) + 1;
}1 / 4
コンピューターサイエンス理論 - map で出現回数を数える
無いキーを引いてみる
キーを email に切り替えて、辞書に無いキーを引いたときの結果を見てください。
- name や age を選ぶと矢印が該当の行に曲がり、値がそのまま返る。辞書は並び順ではなくキーで引くのが分かる
- email を選ぶと矢印はどの行にも当たらず素通りする。下に出るのは値ではなく KeyError
- 一番下の行に .get を使った場合が出る。0 を補って足すのは、この逃げ道を自分で用意していることにあたる
2 / 4
考えてみよう外しても進めます
counts = {} のまま counts[ch] = counts[ch] + 1 と書くと、JavaScript では最初の1文字目で何が起きるでしょう。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
初期値の埋め方
数え上げのコードは短いぶん、初期値の扱いだけで結果が変わります。書き方と結果を並べて見てください。
counts[ch] ?? 0無ければ 0 を補う+ 1そのうえで加算counts の中身
| キー | 件数 |
|---|---|
| b | 1 |
| a | 3 |
| n | 2 |
文字列を1回なめただけで全部の件数が揃います。
キーの順序が要るなら Map を使います。オブジェクトのキーは文字列に変換されるので、数値キーを扱うときは注意してください。
4 / 4
コンピューターサイエンス理論 - 二数の和 (map で O(n))
相方を探さずに引く
合計が target になる2つを探すとき、素直に二重ループを書くと全組み合わせを見ることになります。map に見た値を控えておけば、相方は探さずに引けます。
二重ループの O(n^2) が、1 回の走査 O(n) に変わります。効くのは map の検索が一発で終わるからです。
いま見ている値が決まれば相方の値も決まります。あとは、それを持っているかどうかだけの問題です。
const seen = new Map();
for (let i = 0; i < nums.length; i++) {
const need = target - nums[i];
if (seen.has(need)) return [seen.get(need), i];
seen.set(nums[i], i);
}1 / 4
コンピューターサイエンス理論 - 二数の和 (map で O(n))
一発で引けるのはなぜか
「バケット数」を大きい方から 1 まで下げて、下に出る手数の変化を見てください。
- 列が十分あるうちは 1 列に 1 個で、下の行は最悪ケース 1 個。これが seen.has が一発で返る状態
- 列を減らすほど同じ列に積み上がり、たどる個数が増える。この状態では 1 回の走査でも中で探し直しが起きる
- 1 まで下げると先頭から探すのと同じになる。map の O(1) はタダではなく、散らばりが保たれている前提だと分かる
2 / 4
考えてみよう外しても進めます
nums = [3, 3] で target = 6 のとき、seen.set を if の前に書いてしまうと何が起きるでしょう。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
順番が答えを決める
登録と検索の順番だけで結果が変わります。必ず「先に引いてから登録する」の順で書いてください。
先に登録して、あとで引く
nums = [3, 3], target = 6 の結果は [0, 0] で、自分自身と組んでしまう
先に引いて、あとで登録
nums = [3, 3], target = 6 の結果は [0, 1] で正しい
二重ループで全組み合わせを見ても [0, 1] は出ますが、手数は n の2乗になります。同じ値が複数あるときは、あとから来たほうで上書きされます。最初の添字を残したいなら has で確かめてから登録します。
4 / 4
コンピューターサイエンス理論 - アナグラム判定
並べ替えて同じなら同じ
アナグラムは、文字の並びを入れ替えると相手になる関係です。判定は「使っている文字の顔ぶれと個数が一致するか」に置き換えられます。
どちらの方法でも、長さが違う時点で答えは決まります。まずそこを見ます。
並べ替えて比べるのが一番短い書き方です。数え上げで比べれば並べ替えのぶんが省けます。
const key = (s) => [...s].sort().join("");
key("listen") === key("silent"); // true1 / 4
コンピューターサイエンス理論 - アナグラム判定
長さが違うと組めない
「scores を2個に減らす」を入れてから、ステップを最後まで進めてください。
- 長さが揃っているときは 3 組すべて線でつながり、出力に 3 行そろう
- 片方を 2 個にすると、相方のいない田中は薄く落ちて出力にも出ない。短い方で黙って止まる
- アナグラム判定も同じで、長さが違えば必ず余る文字が出る。数え上げに入る前にここで false を返せる
2 / 4
考えてみよう外しても進めます
文字数を数えて比べる方法と、両方を並べ替えて比べる方法があります。長さ n の文字列で手数が少ないのはどちらでしょう。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
数えて引き算する
1つ目で足し、2つ目で引く。最後に全部が 0 なら顔ぶれも個数も一致しています。表を2つ作って比べる必要はありません。
a.length !== b.lengthまず長さで弾く+ 11つ目で足す- 12つ目で引くlisten と silent の残り
| 文字 | 残り |
|---|---|
| l | 0 |
| i | 0 |
| s | 0 |
| e / n / t | すべて 0 |
全部 0 なのでアナグラムです。
大文字小文字や空白を無視したいなら、数える前に小文字化と除去を済ませておきます。
4 / 4
コンピューターサイエンス理論 - 第 4 章クイズ — データ構造 (基本)
4つの入れ物を選び分ける
この章では、取り出す順を決める2つと、値から引く2つを扱いました。どれも「何が速いか」が違うだけで、優劣はありません。
スタックとキューは順序の話、set と map は検索の話。この2軸で整理すると迷いません。
問題を見たら、まず順序が要るのか、それとも値で引きたいのかを決めてください。そこで入れ物が決まります。
stack.pop(); // 最後に入れたもの
queue.shift(); // 最初に入れたもの
set.has(v); // 持っているか
map.get(k); // キーで引く1 / 3
コンピューターサイエンス理論 - 第 4 章クイズ — データ構造 (基本)
得意は入れ替わる
「先頭に挿入」と「3番目を読む」を切り替えて、下に出る手数を見比べてください。
- 先頭に挿入では配列が後ろを全部ずらして 4 手、連結リストは矢印のつなぎ替えで 1 手
- 3番目を読むでは逆転する。配列は添字で 1 手、連結リストは先頭から 3 歩あるく
- 同じ2つを比べているのに勝ち負けが入れ替わる。万能な入れ物は無く、操作を決めてから選ぶことになる
2 / 3
コンピューターサイエンス理論 - 第 4 章クイズ — データ構造 (基本)
次の章へ
ここまでは入れ物の使い分けでした。次の章では、そのデータが実際にどこに置かれているのかを見にいきます。
入れ物の速さは、最後は置き場所の速さに行き着きます。次の章がその答え合わせになります。
| この章で見たもの | 次の章で見るもの |
|---|---|
| スタックとキューの取り出す順 | メモリとディスクの容量の単位 |
| set と map の一発検索 | キャッシュが効くとき、効かないとき |
| 計算量が落ちる条件 | アドレスとバイトの並び順 |
3 / 3
コンピューターサイエンス理論 - バイト → KB 変換
1024 で割るだけ、のはずが割れない
ファイルの大きさはバイトで数えますが、人に見せるときは KB や MB に直します。直し方は割り算ひとつです。ただし何で割るかが 2 通りあります。
その前に、そのバイト数がどこに置かれている数字なのかを先に見ておきます。
1 KB を 1024 バイトとする流儀と、1000 バイトとする流儀があります。ディスクの容量表示が広告より小さく見えるのはこれが理由です。
const toKB = (bytes) => bytes / 1024;
console.log(toKB(2048)); // 2
console.log(toKB(1000)); // 0.97656251 / 4
コンピューターサイエンス理論 - バイト → KB 変換
そのバイト数はどこにある数字か
単位換算そのものは出てきません。バイト数が置かれる場所が 2 つあることだけ見てください。
- 机の上 (RAM) と引き出しの中 (ストレージ) は別物で、同じ 1 KB でも意味する場所が違う
- 電源が落ちると机の上の分だけが消える。ファイルサイズとして残るのは引き出しの中の数字
2 / 4
考えてみよう外しても進めます
10,000,000 バイトのファイルを、1 MB = 1024 KB として MB に直すといくつになりますか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
コンピューターサイエンス理論 - バイト → KB 変換
2 つの流儀を並べる
同じバイト数でも、1024 で割るか 1000 で割るかで見た目の数字がずれます。ずれは単位が上がるほど大きくなります。
OS は 1024、ディスクメーカーは 1000 を使うことが多く、この差がそのまま容量の食い違いに見えます。
| バイト数 | 1024 で割った値 / 1000 で割った値 |
|---|---|
| 1,000 バイト | 0.98 KB / 1.00 KB |
| 1,024 バイト | 1.00 KB / 1.02 KB |
| 1,000,000 バイト | 0.95 MB / 1.00 MB |
| 1,000,000,000 バイト | 0.93 GB / 1.00 GB |
4 / 4
コンピューターサイエンス理論 - ディスクサイズフォーマット
単位の階段を自動で登る
1234567 バイトと出されても大きさが分かりません。1024 で割れるあいだ割り続けて、単位を 1 段ずつ上げると読める数字になります。
丸めた数字は元に戻せません。表示用の値と計算用の値を分ける癖をつけます。
割った回数がそのまま単位の段数になります。最後に小数第1位まで丸めるのは、人が読むための都合です。
function format(bytes) {
const units = ["B", "KB", "MB", "GB"];
let i = 0;
while (bytes >= 1024 && i < units.length - 1) {
bytes /= 1024;
i++;
}
return bytes.toFixed(1) + " " + units[i];
}1 / 4
コンピューターサイエンス理論 - ディスクサイズフォーマット
表示の粒度を粗くするということ
整形の話とは直接つながりませんが、図の中の数字がどれくらい粗いかに注目してください。
- 自動保存を選ぶと、失う量が 35 分ぶんから 3 分ぶんへ変わる。同じ状態でも表示に出す数字の粒度で印象が変わる
- 保存する を選ぶと引き出し側に写しの量が出る。表示用にまるめた数字と、実際に残っている中身は別ものだと分かる
2 / 4
考えてみよう外しても進めます
3,145,728 バイトを、この関数に通すとどう表示されますか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
境目のあたりを試す
1024 ちょうどの前後で単位が切り替わります。while の条件が 1024 より大きい だと 1024 バイトが 1024.0 B のまま出てしまいます。
1023まだ B のまま1024ここで KB へ上がる出力
| 入力 | 表示 |
|---|---|
| 0 | 0.0 B |
| 1023 | 1023.0 B |
| 1024 | 1.0 KB |
| 1048575 | 1024.0 KB |
| 1048576 | 1.0 MB |
1048575 が 1024.0 KB と出るのは丸めのせいで、バグではありません。
0 と境目の値は必ず手で試します。ここを外すと表示だけがおかしくなり、気づくのが遅れます。
4 / 4
コンピューターサイエンス理論 - キャッシュヒット率
当たった割合を出す
キャッシュに欲しいものがあった回数がヒット、無かった回数がミスです。ヒット率はヒットを全アクセスで割った値になります。
ヒット率が数 % 変わるだけで体感がどれだけ変わるのか、次の図解で確かめます。
アクセスが 1 回も無いときに割ると 0 除算になります。先に total を見て逃がしておきます。
function hitRate(hits, misses) {
const total = hits + misses;
if (total === 0) return 0;
return hits / total;
}
console.log(hitRate(960, 40)); // 0.961 / 4
コンピューターサイエンス理論 - キャッシュヒット率
1 段下がると桁が変わる
扱うデータの大きさのスライダーを右へ動かし、置き場が下の段へ落ちる様子を見てください。
- レジスタからディスクまで 1 段下がるたび、読み出し時間の目盛りが桁で増える
- メモリが足りない状態にする を ON にすると、メモリと SSD の往復が始まり時間が跳ね上がる。ミスが数 % 増えただけで平均が壊れるのはこの往復のせい
2 / 4
考えてみよう外しても進めます
1000 回のアクセスのうち 40 回がミスでした。ヒット率はいくつですか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
ヒット率と平均時間
キャッシュが 10 ns、その下の層が 100 ns だとして、平均の読み出し時間を並べます。ヒット率の伸びの割に、時間の縮み方が大きいことに注目します。
ヒット率 50 %
ヒット率 90 %
ヒット率 96 %
ヒット率 99 %
ヒット率 100 %
棒の長さは平均の読み出し時間そのままです。目盛りは加工していません。
90 % を 96 % に上げる手間は、50 % を 90 % に上げる手間よりずっと小さい割に効きます。
4 / 4
コンピューターサイエンス理論 - LRU 簡易シミュレーション
入りきらないとき、何を追い出すか
枠が 3 つしかないキャッシュに 4 つ目が来たら、どれかを捨てるしかありません。LRU は一番長く使われていないものを捨てる決め方です。
追い出す順番を間違えると、必要なものばかり捨てて何度も取りに行くことになります。
使ったものを末尾へ動かすのが要点です。先頭が自動的に一番古いものになるので、あふれたら先頭を捨てます。
function access(cache, key, capacity) {
const i = cache.indexOf(key);
if (i !== -1) cache.splice(i, 1);
cache.push(key);
if (cache.length > capacity) cache.shift();
return cache;
}1 / 4
コンピューターサイエンス理論 - LRU 簡易シミュレーション
古いものを持ち続けると何が起きるか
追い出しの順番そのものは出てきません。捨てそこねたものが返ってくると何が起きるかを見てください。
- ふつうに再読込 のままだと、手前の棚に残った古い v1 が返り、矢印はサーバまで届かない
- キャッシュを消す を押すとサーバまで矢印が伸びて v2 になる。LRU で捨てる判断を誤ると、この 古いまま が延々続く
2 / 4
考えてみよう外しても進めます
枠が 3 つのキャッシュに A, B, C, A, D の順にアクセスしました。D を入れるとき追い出されるのはどれですか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
1 手ずつ追う
アクセスのたびに、使ったキーを末尾へ動かします。左が古い側、右が新しい側です。
"A", "B", "C", "A", "D"参照の並び3枠の数1 手ごとの中身
| アクセス | 古い ← 中身 → 新しい | 追い出し |
|---|---|---|
| A | A | なし |
| B | A, B | なし |
| C | A, B, C | なし |
| A | B, C, A | なし |
| D | C, A, D | B |
4 手目で A が末尾へ動いたので、5 手目で捨てられるのは B になります。
この配列版は毎回 indexOf で探すので遅く、本物の LRU は連結リストとハッシュを組み合わせて 1 手を一定時間で終わらせます。
4 / 4
コンピューターサイエンス理論 - エンディアンの入れ替え (uint32)
同じ 4 バイトを逆から読む
32 ビットの数は 4 バイトに分かれて番地に並びます。どちらの端から並べるかが機械によって違うので、受け渡しのときに並べ直しが要ります。
並べ直しの前に、そもそも値が番地のどこに置かれているのかを見ておきます。
1 バイトは 8 ビットなので、動かす量は必ず 8 の倍数です。最後の >>> 0 は符号なしに戻すためのおまじないです。
function swap32(n) {
return (
((n >>> 24) & 0xff) |
((n >>> 8) & 0xff00) |
((n << 8) & 0xff0000) |
((n << 24) >>> 0)
) >>> 0;
}1 / 4
コンピューターサイエンス理論 - エンディアンの入れ替え (uint32)
値は番地に並んでいる
操作を切り替えて、札の指す番地の数字がどう変わるかを見てください。
- 変数は中身そのものではなく番地を書いた札で、番地は 16 進で 4 ずつ増えていく
- b から中身を読む を ON にすると、札 から 番地 から 中身 の順にたどる筋道が出る。バイトの並び替えはこの中身側の話
2 / 4
考えてみよう外しても進めます
0x12345678 のバイト順を入れ替えるとどうなりますか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
コンピューターサイエンス理論 - エンディアンの入れ替え (uint32)
バイトの並びを動かして見る
区切る単位を切り替えて、同じ 12 34 56 78 がどう入れ替わるかを追ってください。
- バイト (16 進 2 桁) で区切ると 12 / 34 / 56 / 78 の 4 組が丸ごと逆になり、0x78563412 になる
- 4 ビット (16 進 1 桁) で区切ると 0x87654321 になる。これはバイト順の入れ替えではない
- 違いは計算ではなく、何を 1 つの塊として扱ったかだけ。ネットワーク上の数値は上位バイトが先に来る決まりなので、受け取った側が自分の機械の並びに直してから読む
4 / 4
コンピューターサイエンス理論 - バッファ範囲チェック
書ける場所と書けない場所の境目
長さ 8 のバッファに書き込めるのは添字 0 から 7 までです。8 は 1 つ外側で、そこへ書くと隣の領域を壊します。
この 1 つのずれは、エラーが出ないまま静かに壊れることがあるので厄介です。
小なりイコールにすると 1 つはみ出します。負の添字も忘れず塞いでおきます。
function canWrite(size, index) {
return index >= 0 && index < size;
}
console.log(canWrite(8, 7)); // true
console.log(canWrite(8, 8)); // false1 / 4
コンピューターサイエンス理論 - バッファ範囲チェック
1 つずれても気づけない
3 つの書き方を押し比べて、合計が同じでも中身が違うことを見てください。
- 初期の range(1, 5) は 5 が入らず、エラーも出ないまま合計が 5 足りない
- range(5) に直すと合計は同じ 10 に戻るが、並んだ数字には 0 が混ざっている。合計だけ見て直った と判断すると外す
2 / 4
考えてみよう外しても進めます
長さ 8 のバッファに書き込める添字の最大はいくつですか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
境目だけを並べて確かめる
テストするのは真ん中の値ではなく境目です。マイナス 1、0、size マイナス 1、size の 4 点を通せば、条件の書き間違いはほぼ見つかります。
-1下側の外8上側の外7上側の内判定
| 添字 | 判定 | 意味 |
|---|---|---|
| -1 | false | 下にはみ出す |
| 0 | true | 先頭 |
| 7 | true | 末尾 |
| 8 | false | 上にはみ出す |
小なりイコールに書き換えると、8 だけが true に変わってしまいます。
はみ出した書き込みが隣のデータや戻り先の情報を壊すのが、古典的な脆弱性の正体です。
4 / 4
コンピューターサイエンス理論 - 第5章まとめクイズ
6 本を通して見えたこと
単位換算から始まり、キャッシュ、追い出し、バイトの並び、境目のチェックまで来ました。どれも計算そのものは易しく、外すのはいつも境目と単位です。
最後にもう 1 つ、メモリのあふれ方には 2 種類あることを見ておきます。
この 5 行が第 5 章の骨です。どれがどのレッスンだったか言えれば、クイズは通ります。
1024 で割る / 1000 で割る
hits / (hits + misses)
cache.shift()
(n >>> 24) & 0xff
index >= 0 && index < size1 / 3
コンピューターサイエンス理論 - 第5章まとめクイズ
あふれ方は 2 種類ある
2 本のスライダーを片方ずつ上げて、どちら側から埋まるかを見てください。
- 関数を呼ぶ深さ を上げると上から埋まり、RecursionError の側に寄る
- 大きなデータの数 を上げると下から埋まり、MemoryError の側に寄る。同じ メモリが足りない でも原因は逆
- 両方を上げると真ん中でぶつかる。空き段数が 0 になる瞬間が境目
2 / 3
コンピューターサイエンス理論 - 第5章まとめクイズ
第 6 章へ
第 5 章は 1 台の機械の中の話でした。次の章は、その値を別の機械へ送るときに何が要るのかを見ます。バイトの並びの話は、そのまま次章につながります。
単位と境目を外さない癖は、ネットワークの章でもそのまま効きます。
| 第 5 章で見たこと | 第 6 章での続き |
|---|---|
| バイトと単位の換算 | Base64 で長さが 4/3 倍に膨らむ理由 |
| バイトの並び替え | ネットワーク上の数値の並びの決まり |
| キャッシュの当たり外れ | パケットの分割と再送 |
| 境目のチェック | チェックサムでの壊れの検出 |
3 / 3
コンピューターサイエンス理論 - Base64 エンコード後の長さ計算
バイト列を文字に詰め替える
画像でも ZIP でもメール本文に貼れるように、中身のバイト列を 64 種類の文字だけで表し直すのが Base64 です。詰め替えたあとの文字数は、元のバイト数だけで決まります。
元が何のファイルでも、Base64 が見ているのは 0 から 255 の数字の列だけです。
3 バイトをまとめて 4 文字にするので、結果は必ず 4 の倍数になります。
const bytes = 7;
const len = Math.ceil(bytes / 3) * 4; // 121 / 4
コンピューターサイエンス理論 - Base64 エンコード後の長さ計算
中身はどれも数字の列
見せ方を文字・色・音と切り替えて、下段の数字がどう変わるか見てください。
- 上段の見た目は 3 つとも別物なのに、下段はどれも 0 から 255 の数字が並ぶ
- Base64 が詰め替えるのはこの下段だけ。上段が文字か画像かは関係ない
- スライダーを端まで動かすと、決めた範囲の外は表せないと出る。1 バイトの上限が 255 だから
2 / 4
考えてみよう外しても進めます
7 バイトのデータを Base64 にすると、何文字になりますか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
式にすると 1 行
組の数を切り上げで数えて 4 倍するだけです。割り切れない端数も 1 組として数えるところが要点になります。
Math.ceil(bytes / 3)3 バイトずつで何組か* 41 組が 4 文字長さの対応
| 元のバイト数 | 組数 | Base64 の文字数 |
|---|---|---|
| 3 | 1 | 4 |
| 6 | 2 | 8 |
| 7 | 3 | 12 |
| 10 | 4 | 16 |
元より約 1.33 倍に膨らむので、大きいファイルをそのまま貼るのには向きません。
4 / 4
コンピューターサイエンス理論 - URL エンコード対象文字数
URL に書けない文字がある
URL にそのまま書けるのは英数字と一部の記号だけです。それ以外は % と 16 進 2 桁の 3 文字に置き換えないと、区切り記号と読み違えられます。
置き換えを忘れると、値の中の & がパラメータの区切りとして読まれて壊れます。
空白は %20、& は %26 になります。1 文字が 3 文字に増えるのがポイントです。
encodeURIComponent('a b&c') // 'a%20b%26c'1 / 4
コンピューターサイエンス理論 - URL エンコード対象文字数
どこに自由な文字が入るのか
4 つの部位ボタンを順に押して、どこが毎回変わる場所なのか見てください。
- スキームとホストは決まった形。値が入り込むのはパスから後ろのクエリ側
- クエリは検索語や並び順が直接載る場所。日本語や記号が来るのはここ
- http にすると中身がそのまま読まれる。エンコードは形を整えるだけで、隠す働きは無い
2 / 4
考えてみよう外しても進めます
空白 1 個と & 1 個を含む 10 文字の文字列をエンコードすると、全体で何文字になりますか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
コンピューターサイエンス理論 - URL エンコード対象文字数
そのまま書ける文字と、置き換わる文字
数えるときは、置き換わる 1 文字が 3 文字に増えると考えます。日本語はまずバイト数に直してから数えるので、増え方が桁違いになります。
数える対象を先に決めてから 1 文字ずつ判定すると、数え違いが起きません。
| 文字 | URL での扱い |
|---|---|
| A-Z a-z 0-9 | そのまま書ける |
| - . _ ~ | 非予約文字。そのまま書ける |
| 半角スペース | %20 の 3 文字になる |
| & = ? # | 区切り記号。値に入るなら %26 などにする |
| 日本語 1 文字 | UTF-8 で 3 バイトなので %E3%81%82 の 9 文字になる |
4 / 4
コンピューターサイエンス理論 - IPv4 アドレスを 32bit 整数に変換
4 つの数字を 1 つにまとめる
ドット区切りの 4 つの数字は、それぞれ 0 から 255 までの 1 バイトです。並べて 1 個の整数として見ると、範囲の判定も並べ替えも足し算と引き算だけで済みます。
ドットは人が読むための区切りで、機械にとっては 4 バイトが並んでいるだけです。
左から順に 256 倍ずつ重い桁として扱い、足し合わせるだけです。
const [a, b, c, d] = '192.168.1.10'.split('.').map(Number);
const n = a * 16777216 + b * 65536 + c * 256 + d;1 / 4
コンピューターサイエンス理論 - IPv4 アドレスを 32bit 整数に変換
住所が指しているもの
ポートを切り替えながら、建物のラベルに書かれた住所そのものを見てください。
- 建物に書かれた 192.168.1.10 は、0 から 255 の数字が 4 つ並んでいるだけ
- どのポートを選んでも建物のラベルは変わらない。住所の部分だけを 1 つの整数にまとめられる
- 行き先は建物 (IP) と部屋 (ポート) の 2 段構え。整数にまとめるのは前半の建物の側だけ
2 / 4
考えてみよう外しても進めます
1.0.0.0 を 32bit 整数にすると、いくつになりますか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
変換した結果
左から 1 バイトずつ取り込み、そのたびに 256 倍して桁をずらします。ループ 1 本で 4 回まわせば終わりです。
n * 2561 バイトぶん桁をずらすNumber(o)0 から 255 の 1 バイト変換の対応
| IPv4 アドレス | 32bit 整数 |
|---|---|
| 0.0.0.1 | 1 |
| 0.0.1.0 | 256 |
| 1.0.0.0 | 16777216 |
| 192.168.1.10 | 3232235786 |
| 255.255.255.255 | 4294967295 |
上限が 4,294,967,295 なので、IPv4 の住所は全部で約 43 億個しかありません。
4 / 4
コンピューターサイエンス理論 - 32bit 整数を IPv4 アドレスに変換
整数を人が読める形に戻す
整数のままではどの機器を指しているのか読めません。上位から 8 ビットずつ 4 回切り出して、ドットでつなぎ直すと元の表記に戻ります。
取り出した 4 つはどれも 0 から 255 に収まります。256 以上が出たら計算のどこかが違います。
右に寄せてから下位 1 バイトだけを取り出す、を 4 回くり返します。
const n = 3232235786;
const ip = [24, 16, 8, 0].map((s) => (n >>> s) & 255).join('.');1 / 4
コンピューターサイエンス理論 - 32bit 整数を IPv4 アドレスに変換
切り出した数字が指す場所
ポートを 80、3306、9999 と押して、上の 1 行がどう書き換わるか見てください。
- 上の connect の行は住所の部分がそのままで、番号の部分だけが差し替わる。数字は場所ごとに切り出して読むもの
- 9999 を選ぶと該当する部屋が無く、建物の壁で止まる。切り出した数字が範囲の外だと成り立たないのと同じ
- 建物のラベルは常にドット 4 区切りのまま。人が読むときは必ずこの形に戻して見る
2 / 4
考えてみよう外しても進めます
整数 256 を IPv4 アドレスに戻すと、どれになりますか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
コンピューターサイエンス理論 - 32bit 整数を IPv4 アドレスに変換
4 回の切り出し
ずらす幅を 24、16、8、0 と変えながら、毎回 255 との AND で下位 1 バイトだけを残します。やっていることは 4 回とも同じです。
JavaScript のビット演算は符号付き 32bit なので、符号なしで扱う >>> を使わないと負の数が出ます。
| 取り出す位置 | 計算 |
|---|---|
| 第 1 オクテット | 24 ビット右にずらして 255 と AND |
| 第 2 オクテット | 16 ビット右にずらして 255 と AND |
| 第 3 オクテット | 8 ビット右にずらして 255 と AND |
| 第 4 オクテット | ずらさずに 255 と AND |
4 / 4
コンピューターサイエンス理論 - CIDR プレフィックスからネットマスクを作る
どこまでが同じネットワークか
住所のうち上位の何ビットぶんを共通とみなすかを決めるのがネットマスクです。スラッシュの後ろの数字が、先頭に並べる 1 の個数になります。
できあがるのは、先頭が 1 の並び、その後ろが 0 の並び、という 2 つに分かれた形だけです。
全部 1 の 32bit を左にずらすと、はみ出た下位が 0 で埋まってマスクになります。
const prefix = 24;
const mask = (0xffffffff << (32 - prefix)) >>> 0; // 42949670401 / 4
コンピューターサイエンス理論 - CIDR プレフィックスからネットマスクを作る
マスクの 1 が並んだ桁だけ残る
AND を選んだまま、マスクのスライダーを 0 から 255 まで動かしてください。
- マスクが 1 の桁だけ結果に残り、0 の桁は必ず 0 に落ちる。これがネットワーク部を取り出す動きそのもの
- 255 まで上げると 8 桁すべてが残り、0 まで下げると何も残らない。/32 と /0 の両端がこれにあたる
- 下に出る立っているビットの数が、CIDR のスラッシュの後ろの数字と同じ意味を持つ
2 / 4
考えてみよう外しても進めます
/26 のネットマスクは、最後のオクテットがいくつになりますか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
コンピューターサイエンス理論 - CIDR プレフィックスからネットマスクを作る
プレフィックスと入るアドレスの数
1 の個数が 1 つ増えるたびに、そのネットワークに入るアドレスの数はちょうど半分になります。設計のときはこの表を逆に引きます。
アドレスとマスクを AND した結果が同じなら、その 2 台は同じネットワークにいます。
| CIDR | ネットマスクと入るアドレス数 |
|---|---|
| /8 | 255.0.0.0 で約 1677 万個 |
| /16 | 255.255.0.0 で 65,536 個 |
| /24 | 255.255.255.0 で 256 個 |
| /26 | 255.255.255.192 で 64 個 |
| /32 | 255.255.255.255 で 1 個。1 台だけを指す |
4 / 4
コンピューターサイエンス理論 - 単純チェックサム
届いた中身が正しいか確かめる
小包が届かなかったことは番号で分かりますが、中身の 1 ビットが化けたことは番号では分かりません。そこで送る側が全バイトの合計を添え、受け取る側が同じ計算をして突き合わせます。
欠けを見つけるのは番号の役目、化けを見つけるのがチェックサムの役目です。
全部足して 256 で割った余りを取るだけです。結果は 1 バイトに収まります。
const sum = [72, 101, 108].reduce((a, b) => a + b, 0) % 256; // 251 / 4
コンピューターサイエンス理論 - 単純チェックサム
欠けは番号で分かる
4 番の小包が届かないをオンにして、ステップを最後まで進めてください。
- 6 つに切られた小包には番号が付き、届く順がバラバラでも並べ直せる
- 4 番が消えると右側に穴が空いたまま残る。受け取った側は中身を自分で作れない
- 足りないのが 4 番だけだと分かるから、その 1 つを送り直すだけで直る
2 / 4
考えてみよう外しても進めます
バイト列 [200, 100, 56] のチェックサムを 256 の余りで求めるといくつですか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
突き合わせた結果
受け取った側が同じ式で計算し、添えられた値と比べます。1 バイトでも違えば合計がずれるので、化けに気づけます。
reduce((a, b) => a + b, 0)全バイトの合計% 2561 バイトに収める受け取った側の判定
| 受け取ったバイト列 | 計算した値 | 判定 |
|---|---|---|
| 72 101 108 | 25 | 添えられた 25 と一致 |
| 72 101 109 | 26 | 25 と食い違う。化けている |
| 72 108 101 | 25 | 並びが違うのに気づけない |
並びの入れ替わりや、打ち消し合う 2 か所の化けは単純な合計では見抜けません。実務では CRC を使います。
4 / 4
コンピューターサイエンス理論 - 第6章まとめクイズ
この章でやったこと
バイト列の詰め替え、住所の計算、届いた中身の確かめ方までを扱いました。どれも人が読む形と機械が計算する形を行き来する話です。
上から順に Base64 の文字数、/24 のネットマスク、単純チェックサムです。
この章で書いた式を 3 行だけ並べました。どれが何の計算だったか思い出せますか。
Math.ceil(7 / 3) * 4
(0xffffffff << 8) >>> 0
bytes.reduce((a, b) => a + b, 0) % 2561 / 3
コンピューターサイエンス理論 - 第6章まとめクイズ
確実さと速さは取り替えっこ
ファイル転送とビデオ通話を切り替えて、同じ失われ方で正解が入れ替わるのを確かめてください。
- TCP は完全さが常に 100% になる代わりに、失う割合を上げるほど遅れの棒が伸びる
- UDP は遅れが 1.0 秒のまま変わらず、そのぶん完全さが欠ける
- ファイルは欠けが致命的、通話は止まる方が致命的。場面によってどちらが赤くなるかが入れ替わる
2 / 3
コンピューターサイエンス理論 - 第6章まとめクイズ
次の章へ持っていくもの
この章で身についた数え方と確かめ方は、そのまま設計と DB の話に繋がります。形が同じなので、名前が変わっても迷いません。
次の章は設計と DB の基礎です。数えて確かめる癖はそのまま使えます。
| この章で覚えた形 | 次の章でどう効くか |
|---|---|
| 端数を切り上げて組を数える | レコードを固定長のページに詰めるときも同じ計算になる |
| 上位ビットだけを残すマスク | 権限フラグや状態の持ち方でも同じ形が出てくる |
| 整数と人が読む表記の往復 | DB には整数で入れ、画面に出すときは表記に戻す |
| 合計で食い違いを見つける | 振り込みの前後で残高が合うかを確かめる考え方に繋がる |
3 / 3
コンピューターサイエンス理論 - 重複データを 1NF に変換 (フラットなリスト化)
1つのセルに複数の値を入れた表
紙の伝票をそのまま写すと、1件の注文に商品が2つ3つとぶら下がった形になります。人には読めますが、この形のままでは商品名で検索することも、1商品だけ消すこともできません。
ほどく前に、ほどけていない表が DBMS からどう見えているかを図解で確かめます。
items の中に配列が入っています。ここを1行ずつにほどくのが 1NF です。
const raw = [
{ date: "2025/1/13", from: "YYY", items: ["商品A", "商品B"] },
];1 / 4
コンピューターサイエンス理論 - 重複データを 1NF に変換 (フラットなリスト化)
空欄は何を意味するのか
トグルを入れる前に、注文日が空いている3行目をよく見てください。
- 空欄を「上の行と同じ」と読んでいるのは人の目だけで、DBMS には値の無い行としてしか届かない
- トグルを入れると空欄が埋まり、同じ日付が2回並ぶ。冗長に見えても、1行だけで意味が決まるようになる
2 / 4
考えてみよう外しても進めます
商品が 2個 / 1個 / 3個 ぶら下がった注文3件を、1商品1行にほどくと何行になりますか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
ほどいた結果
flatMap で、1件の注文を商品の数だけの行に展開します。左のコードを流すと、右の表のように 1セル1値 の形になります。
flatMap1行を複数行に開くo.items.map中の配列を回すflat
| date | from | item |
|---|---|---|
| 2025/1/12 | XXX | 商品A |
| 2025/1/13 | YYY | 商品A |
| 2025/1/13 | YYY | 商品B |
| 2025/1/15 | ZZZ | 商品C |
緑の2行は、もとは1件の注文だったもの
日付が2回並ぶのは無駄ではありません。1行だけ見れば意味が決まる、という保険です。
4 / 4
コンピューターサイエンス理論 - キーで join (map 利用)
分けた表をもとに戻す
正規化で分けた表は、外部キーをたどって組み直します。素直に二重ループで探すと注文の数だけ全ユーザーを走査してしまうので、先に id をキーにした map を作ります。
その前に、そもそも JOIN が何行を返すのかを図解で数えます。
map を先に作ると、1件あたりの照合が1回で済みます。
const byId = new Map(users.map((u) => [u.id, u]));
const joined = orders.map((o) => ({
...o,
user: byId.get(o.uid),
}));1 / 4
コンピューターサイエンス理論 - キーで join (map 利用)
つなぎ方で結果が変わる
つなぎ方を INNER と LEFT で切り替え、結ばれる線と結果の行数を数えてください。
- INNER では注文の無いユーザーが結果から消える。LEFT では残り、注文側が NULL で埋まる
- カンマでつなぐトグルを入れると、そろえる条件が無いので全部と全部が結ばれて行数が跳ね上がる
2 / 4
考えてみよう外しても進めます
ユーザー3人 (うち1人は注文が無い) と注文4件を、ユーザーIDで INNER JOIN すると何行になりますか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
つないだ結果
map を引きながら注文を回すと、注文4件がそのまま4行になります。注文の無い田中さんは、この形では結果に現れません。
new Map(先に索引を作るbyId.get(o.uid)外部キーで引く出力
| name | item |
|---|---|
| 佐藤 | 本 |
| 佐藤 | ペン |
| 鈴木 | ノート |
| 鈴木 | 付箋 |
| 田中 | (注文なし) |
取り消し線の行が、INNER JOIN で落ちる側
落ちた行も見たいときが LEFT JOIN です。落ちるのが正しい場面もあるので、どちらが偉いという話ではありません。
4 / 4
コンピューターサイエンス理論 - 残高転送のトランザクション風処理
途中で止まると困る処理
口座の振替は、引く処理と足す処理が両方そろって初めて意味を持ちます。片方だけ済んだところで止まると、世界からお金が消えます。
止まるだけが事故ではありません。2人が同時に触ったときに何が起きるかを図解で見ます。
2行を「まとめて全部か、まとめて無かったことに」するのがトランザクションです。
from.balance -= amount;
// ここで落ちたら?
to.balance += amount;1 / 4
コンピューターサイエンス理論 - 残高転送のトランザクション風処理
2人が同時に直すとどうなるか
保管先をファイルにしたまま、手順を最後まで送ってください。
- 2人とも正しく読んで正しく書いているのに、ファイルでは後から書いた側が先の変更を上書きして消す
- 保管先を DBMS に切り替えて同じ手順を送ると、片方が待たされたぶん両方の変更が残る
2 / 4
考えてみよう外しても進めます
残高1000円の口座を2人が同時に読み、それぞれ500円引いて書き戻しました。最後に保存されている残高はいくつですか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
コンピューターサイエンス理論 - 残高転送のトランザクション風処理
ACID が守っているもの
トランザクションが約束する4つは、それぞれ別の事故に対応しています。名前を覚えるより、どの事故を防ぐ役かで押さえてください。
図解で見た「消えた500円」は Isolation の担当です。1人で使うぶんには表に出てきません。
| 約束 | これが無いと起きること |
|---|---|
| Atomicity (原子性) | 引いた側だけ処理が済んで、お金が消える |
| Consistency (一貫性) | 残高がマイナスの口座が生まれる |
| Isolation (独立性) | 同時に直した片方の変更が黙って消える |
| Durability (永続性) | 完了と言われた振替が再起動で無かったことになる |
4 / 4
コンピューターサイエンス理論 - CAP の availability 模擬
1台落ちても答えを返す
同じデータを3台に持たせておくと、1台が返事をしなくても残り2台で読み取りを続けられます。この「落ちていても answer を返せる」性質が availability です。
待つのをやめると何が縮むのか。待ち合わせの形そのものを、次の図解で見比べます。
全員そろうのを待たず、過半数の返事だけで値を決めています。
const replies = replicas
.map((r) => r.read())
.filter((v) => v !== null);
const value = majority(replies);1 / 4
コンピューターサイエンス理論 - CAP の availability 模擬
待ち合わせの形を見比べる
この図はレストランの注文が題材ですが、見るのは「全部そろうまで待つか、待たずに進むか」の差です。
- 上の同期は所要時間が足し算で伸び、下の非同期はいちばん長い1本でほぼ決まる。全員の返事を待つ設計が高くつく理由がここに出る
- 依存のトグルを入れると非同期でも棒がずれて並び、合計が同期に近づく。待たない設計にしても、待ちが必要な相手がいれば速くならない
- レプリカの話にそのまま置き換えるなら、遅い1台に合わせるか、過半数で先に進むかの選択に当たる
2 / 4
考えてみよう外しても進めます
3台のレプリカのうち1台が落ちています。多数決で値を決めるには、何台の返事がそろえばよいですか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
多数決で決める
3台に問い合わせ、返ってきたぶんだけで最頻値を採ります。落ちた1台は null として捨てられ、残り2台が一致したので値が決まります。
value: null返事が来ないfilter落ちた台を捨てる読み取り
| node | value | 扱い |
|---|---|---|
| A | 120 | 採用 |
| B | 120 | 採用 |
| C | - | 無視 |
2票そろったので 120 を返す
返せたのは「最新かどうかは保証しない」と割り切ったからです。availability を取ると、その代わりに一貫性が緩みます。
4 / 4
コンピューターサイエンス理論 - URL ルーティング
URL から処理を選ぶ
Web アプリの入口は、届いた URL を上から順に照らし合わせて、最初に当たった1つの処理へ渡すだけの仕組みです。当たらなければ 404 を返します。
「上から順に、最初に当たった1つだけ」という性質を、次の図解で目で追います。
括弧で囲んだ部分が、URL から取り出した id になります。
const path = "/users/42";
const m = path.match(/^\/users\/(\d+)$/);
if (m) showUser(m[1]);1 / 4
コンピューターサイエンス理論 - URL ルーティング
上から順に1つだけ通る
この図の条件分岐を、ルーターの照合表だと思って読んでください。
- 値を動かすと、上の判定から順に見て、最初に当てはまった枝だけが光る。下の枝は条件を満たしていても通らない
- else を消すトグルを入れると、どの枝にも当たらない値が出てくる。ルーターでこれが起きた状態が 404
2 / 4
考えてみよう外しても進めます
上から /users/:id、/users/new の順で登録したルーターに /users/new が届きました。どれが動きますか。
選ぶと、この枚の中で答えと理由を確かめられます。
3 / 4
登録の順番が効く
同じ4本のルートでも、書く順番で行き先が変わります。上に置くほど強いので、動きの決まっているパスから先に並べます。
/users/new
文字列が固定。先に置かないと :id に飲まれる
/users/:id
数字でも文字でも当たる。固定のパスより後ろへ
/users
一覧。上の2本とは長さが違うので順番の影響は小さい
(どれにも当たらない)
最後の受け皿として 404 を返す
ルーティングのバグの多くは、書いた場所が悪いだけです。動かないときはまず順番を疑ってください。
4 / 4
自分で相手を作ってしまうクラス
中で new してしまうと、その相手なしでは1行も動かせなくなります。テストのときだけ差し替えたい、という要求がここで通らなくなります。
new SmtpMailer()相手を中で決めているできること
| やりたいこと | この設計だと |
|---|---|
| テストでメール送信を止める | できない |
| 送信先を SMTP から API に替える | 本体を書き換える |
| そのまま本番で動かす | できる |
動くけれど、動かし方が1つしかない
外から渡す形にするだけで、この表がどう変わるかを最後に見ます。
1 / 3
コンピューターサイエンス理論 - 疎結合と密結合 — 依存性注入で設計を変える
下が壊れると上まで倒れる
この図は言語や機械の階層が題材ですが、見てほしいのは依存が一方向に積み上がっているところです。
- 立つ層を変えると、その下の中身が見えなくなる。上の層は下の詳しい事情を知らずに使えている、という状態がここで見える
- 壊すトグルを入れると、壊れた層より上が全部倒れる。依存先の具体的な都合に寄りかかった設計が密結合で、巻き込まれるのはいつも上の側
- 疎結合はこの積み上がりを無くす話ではない。倒れる範囲を、間に挟んだ約束ごとで区切る話になる
2 / 3
外から渡す形にする
相手を引数で受け取るようにすると、本体は「send できる何か」しか知らなくなります。差し替えの自由と引き換えに、誰が何を渡すのかを追う手間が増えます。
密結合
相手は中で new する。 テストには本物が要る。 差し替えるには本体を書き換える。 追う場所は少なく、小さいコードではこちらのほうが素直
疎結合
相手は呼ぶ側が渡す。 テストは偽物を渡して閉じられる。 差し替えは渡すものを変えるだけ。 そのかわり追う場所が増える
疎結合は無料ではありません。差し替える予定が本当にあるかで決めてください。
3 / 3
コンピューターサイエンス理論 - コース総まとめクイズ
7章ぶんを1つにつなぐ
ビットから始めて、文字コード、計算量、データ構造、メモリ、ネットワーク、そして設計まで来ました。どの章も「同じものを別の見方で数え直す」話でつながっています。
総まとめの前に、設計の章でいちばん効く判断を図解で1つだけ確かめます。
3行とも、コンピュータの側では最後は数の並びとして扱われています。
const bits = 0b1010;
const text = "あ";
const rows = users.map((u) => u.id);1 / 3
コンピューターサイエンス理論 - コース総まとめクイズ
詰め込むか、分けるか
トグルを入れる前に、同じメールアドレスが表の中に何か所出てくるか数えてください。
- 混ぜたままの表では、顧客が注文するたびに同じメールが増える。1文字直すのに何行さわるかがそのまま事故の起きやすさになる
- 分けた側では顧客の表に1か所だけ残り、注文の表には顧客IDが立つ。この列が外部キーで、JOIN でもとに戻すときの手がかりになる
2 / 3
コンピューターサイエンス理論 - コース総まとめクイズ
ここまでで手に入ったもの
このコースで身についたのは、個別の知識より「なぜそうなっているか」を自分で説明できる状態です。読んだだけでは残らないので、どこで効くかとセットで持ち帰ってください。
次は、この見方を持ったまま実際のアプリを作る側へ進んでください。土台があると、フレームワークの作法が丸暗記でなくなります。
| 説明できるようになったこと | どこで効くか |
|---|---|
| 数と文字が最後はビットになること | 文字化けやサイズ計算の原因を切り分けられる |
| 計算量で処理を見積もること | データが増えたときに詰まる場所を先に見つけられる |
| 用途でデータ構造を選ぶこと | 総当たりの探索を map や set で置き換えられる |
| 同時に触られる前提で設計すること | 1人で試すと出ない不具合を、設計の段階で潰せる |
| 依存の向きを自分で決めること | 差し替えたい部分だけを差し替えられる形に保てる |
3 / 3