速い・遅いには、かたちがある
バラバラの数字が、手もとにある
ここまでのレッスンで、いくつもの回数を数えてきました。まっすぐさがすと10枚で最悪10回。半分に切ってさがすと、同じ10枚でも最悪4回でした。
ならべる方はどうだったでしょう。逆順の12枚を差しこみでならべると66回、分けてたばねると20回。4つの数字は、いまのところただの記録にすぎません。
このレッスンでやることは、ひとつだけです。長さを変えながら、同じ手順を測りなおす。すると、バラバラに見えた数字の奥から法則が浮かび上がります。
長さを倍にしながら、測りなおす
長さを4、8、16、32、64と倍々にして、4つの手順をエンジンで実測しました。さがす2つは「どこにもない数」をさがす最悪の場合、ならべる2つは逆順から出発しています。
| 長さ n | 半分に切る（最悪） | まっすぐさがす（最悪） | 差しこみ（逆順） | 分けてたばねる（逆順） |
|---|---|---|---|---|
| 4 | 3 | 4 | 6 | 4 |
| 8 | 4 | 8 | 28 | 12 |
| 16 | 5 | 16 | 120 | 32 |
| 32 | 6 | 32 | 496 | 80 |
| 64 | 7 | 64 | 2,016 | 192 |
表は、横にながめてもあまり語りません。縦に、「長さが倍になったとき何が起きたか」を読んでください。
- 半分に切る：3、4、5、6、7——倍にしても1回増えるだけ。レッスン3の驚きが、列としてそのまま見えています
- まっすぐさがす：4、8、16、32、64——長さとぴったり同じ。倍にすれば倍、レッスン2の比例です
- 差しこみ（逆順）：6、28、120、496、2,016——倍にするたびほぼ4倍。64枚で2,016回は、もう手作業の世界ではありません
- 分けてたばねる（逆順）：4、12、32、80、192——倍よりは増えるが、4倍にはほど遠い。2倍とちょっとです
同じ「倍にする」という操作に、4つの手順は4通りの増え方で応えました。この増え方のくせこそ、コース名にある「かたち」です。
差しこみと、分けてたばねるを、ならべて再生できる実験室を置いておきます。数を打ちかえて長さを変え、回数の開きが長さとともに広がっていくのをたしかめてください。
ならべる前。左はしの1枚は、それだけで「そろっている」
ならべる前。まず半分に分けることをくりかえす
かたちに、名前を与える
増え方のくせは4種類ありました。それぞれに名前を与え、グラフに描いたらどう見えるかをことばで添えます。横軸が長さ、縦軸が回数です。
- 半分に切るかたち（対数、log n）——倍にしても1回増えるだけ。グラフは右へ行くほど平らに寝ていき、ほとんど水平に見えます
- 比例のかたち（n）——倍にすれば倍。グラフはまっすぐな直線です
- 分けてたばねるかたち（n log n）——倍にすると2倍とちょっと。直線よりわずかにゆるく反り上がる、直線の親戚です
- 総当たりのかたち（n²）——倍にするとほぼ4倍。はじめはおとなしいのに、右へ行くと壁のように立ち上がります
差しこみが「総当たり」と呼ばれるのは、逆順のとき、新しい1枚がそろった部分のぜんぶとくらべることになるからでした。レッスン4で見た「ほぼ4倍」の正体は、このかたちです。
⟡ よりみち：世の中での書き方——オーダー記法
プログラミングの世界では、このかたちを O(log n)、O(n)、O(n log n)、O(n²) と書く流儀があります。読み方は「オーダー」。意味は、いまあなたが読み取ったとおり「かたちの名前」です。本や求人票でこの記号を見かけたら、「増え方のくせの話をしているな」と読みかえてください。
かたちが、すべてを支配する
長さを100万にしてみましょう。表を伸ばすかわりに、かたちから見積もります。
- 半分に切るかたちなら、およそ20回
- 比例のかたちなら、100万回
- 総当たりのかたちなら、1兆のけた
20回と1兆——同じ「さばく」仕事でも、かたちが違えば、けたが12個ずれます。ここで思い出してほしいのが、レッスン1の約束です。手順は秒ではなく、くらべた回数で測る。
機械を10倍速くしても、1兆回は1,000億回ぶんの時間にしかなりません。総当たりを半分に切るかたちに変えれば、回数そのものが20回になります。機械を速くするより、かたちを変える方が効く——物差しを機械から切り離したのは、この一点を見るためでした。
正直な注意——かたちは「大きいとき」の話
ただし、かたちが語るのは長さが大きくなったときのふるまいです。小さい列では、話が逆転することがあります。
表の回数にあらわれない手間も、現実にはあります。分けてたばねるには作業用の場所と書き写しが要り、差しこみは手もとだけで済むのでした（レッスン5）。だから数枚から数十枚の列では、総当たりのかたちのはずの差しこみが、実測では勝つことがめずらしくありません。
もうひとつ、逆順は差しこみへのいちばんの意地悪です。ほぼそろった列なら、差しこみは比例に近い回数で済みます。かたち・場所・列のなりたち——どれを重く見るかは、レッスン8でトレードオフとしてまとめて考えます。
✎ 演習：表の続きを、予言する
表は長さ64で終わっています。長さを128にしたとき、4つの手順がそれぞれ何回くらいになるか、かたちから予言してください。予言できたら、実験室はさておき——増え方のくせ（+1、2倍、ほぼ4倍、2倍とちょっと）だけを頼りに、64の行から計算してみます。
ヒント1（考え方）
64の行は 7、64、2,016、192 でした。半分に切るかたちは+1。比例は2倍。総当たりはほぼ4倍。分けてたばねるは2倍とちょっと、です。
こたえ（エンジンの実測値）
半分に切る：8回（7+1）。まっすぐさがす：128回（64×2）。差しこみ（逆順）：8,128回（2,016のほぼ4倍）。分けてたばねる（逆順）：448回（192の2倍とちょっと）。かたちさえ読めれば、測る前から、けたを言い当てられます。
このレッスンで分かったこと
- 回数は、長さを倍にしながら測りなおすと法則になる——+1ずつ／2倍／ほぼ4倍／2倍とちょっと
- 増え方のくせが手順のかたち：半分に切る（log n）・比例（n）・分けてたばねる（n log n）・総当たり（n²）
- 世の中ではこれを O(n) や O(n²) と書く。読みは「オーダー」、意味は「かたちの名前」
- 長さ100万なら、対数は約20回、総当たりは1兆のけた——機械を速くするより、かたちを変える方が効く
- ただし、かたちは長さが大きいときの話。小さい列や、ほぼそろった列では、逆転もおきる