かたちを、選ぶ
登場人物が、そろいました
7つのレッスンで、あなたは5つの手順と知り合いました。最終レッスンの前に、一列にならべてみます。
- まっすぐさがす（線形探索）——どんな順番の列でも働く。手間は長さに比例
- 半分に切ってさがす（二分探索）——そろっている列なら、1回くらべるたびに半分を捨てられる
- 差しこみでならべる（挿入ソート）——手札の手つき。最悪は「倍になったら4倍」のかたち
- 分けて、たばねる（マージソート）——控えの紙と引きかえに、大きな列でもおだやかなかたち
- おぼえておく（メモ化）——メモ帳と引きかえに、同じ計算を二度しない
さて、この中で「いちばん良い」手順はどれでしょうか。——実は、この問いのほうが間違っています。手順に優劣の表はなく、状況が選ばせるのです。最終レッスンでは、その選び方を3つのケースで確かめます。
ケース1：1回さがすだけなら
半分に切ってさがす手順は、たしかに速いのでした。でもレッスン3で見たとおり、あの速さは「そろっている」という前提を信頼して買ったものです。列がバラバラなら、まずそろえる代金を払わなければなりません。
バラバラの12個の列で、その代金を実測してみます。差しこみでならべると、何回かかるでしょうか。
ならべる前。左はしの1枚は、それだけで「そろっている」
38回かかりました。そろえた列なら、半分に切ってさがす手順は最悪でも4回で答えを出します。これも確かめておきましょう。
まんなかの 30 は 57 より小さい——右半分にしぼる
では勘定です。そろえてから二分の道は、38回＋さがすたびに最悪4回。まっすぐさがす道は、準備なしで、さがすたびに最悪12回です。
| さがす回数 | そろえてから二分 | まっすぐのまま |
|---|---|---|
| 1回 | 38＋4＝42回 | 12回 |
| 4回 | 38＋16＝54回 | 48回 |
| 5回 | 38＋20＝58回 | 60回 |
| 10回 | 38＋40＝78回 | 120回 |
1回さがすだけなら、素朴なまっすぐさがすの圧勝です。ところが5回目で形勢が入れかわり、あとは差が開く一方になります。そろえる代金は投資で、何回さがすかで元が取れるかどうかが変わるのです。
紙の辞書がそろえて印刷されているのは、何万人が何万回も引くからです。今日の買い物メモをそろえてから読む人がいないのは、1回しか読まないからです。あなたはどちらの判断も、すでに正しくやっています。
ケース2：ほぼそろっている列なら
レッスン6で、ひとつ予告をしました。「倍になったら4倍」のかたちを持つ手順が、おだやかなかたちの手順に勝つことがある——その回収です。
1か所だけ乱れた列を、差しこみとたばねで競走させます。5と4だけが入れかわった、ほぼそろった10個の列です。
ならべる前。左はしの1枚は、それだけで「そろっている」
ならべる前。まず半分に分けることをくりかえす
差しこみは10回、たばねは19回。最悪のかたちでは負けるはずの差しこみが、ほぼ倍の差で勝ちました。
理由は手つきにあります。差しこみは、手に取ったカードがすぐ左で止まるなら、ほとんど何もしません。そろっている部分には手を触れずに通りすぎるので、乱れが少ないほど回数が減るのです。
一方のたばねは、列がどんなにそろっていても、律儀に分けてたばね直します。最悪に強い代わりに、目の前の列の幸運を使えません。試しに上の数列を 10, 9, 8, …, 1 と逆さに打ちかえてみてください——差しこみ45回、たばね15回と、今度は鮮やかに逆転します。
これはレッスン3と同じ構図です。「来る列はほぼそろっている」と知っているなら、その前提を信頼して、最悪のかたちが悪い手順をあえて選べます。毎晩わずかしか順位が動かない名簿の更新のような仕事では、差しこみが勝ち続けるのです。
⟡ よりみち：あなたのスマホの中の、合いの子
PythonやAndroidの標準のならべ替えは、Timsort（ティムソート）という手順です。中身は挿入ソートとマージソートの合いの子で、列の中の「すでにそろっている部分」を見つけては挿入ソートで仕上げ、全体はたばねでまとめます。プロの道具箱でも、答えは「どちらか」ではなく「状況で使い分け」でした。
ケース3：置き場がないなら
もうひとつ、見落としやすい勘定があります。場所です。
たばねる手順は、控えの紙がいるのでした（レッスン5）。おぼえておく手順は、メモ帳がいるのでした（レッスン7）。どちらも「時間を、場所で買う」取り引きです。
ところが、場所がいつでも買えるとは限りません。小さな機械の中で動くプログラムや、置き場と同じくらい巨大な列を相手にするときは、控えの紙の代金が払えないことがあります。そういう状況では、列そのものの上だけで仕事が終わる差しこみや、その場の工夫が選ばれます。
時間と場所は、どちらかを立てればどちらかが引っこむ間柄です。「速いほう」だけを見て選ぶと、置き場の請求書にあとで驚くことになります。
持ち帰りの道具：3つの問い
3つのケースを抽象すると、手順を選ぶ前に聞くべき問いは3つです。
- 量はどれくらい？ ——12個なら、どの手順でも一瞬です。100万個なら、かたちの差が命運を分けます
- 何回やる？ ——1回きりなら、準備の代金は払い損です。毎日くりかえすなら、準備は投資になります
- 置き場はある？ ——控えの紙やメモ帳が買えないなら、その場で済む手順を選びます
この3つに答えてから、最初の一覧表に戻ってください。「いちばん良い手順」は決まりませんが、「この状況でいちばん良い手順」なら、もう指させるはずです。
✎ 最終演習：状況が、選ばせる
次の3つの状況で、あなたならどの手順（または組み合わせ）を選びますか。3つの問いを声に出して当てはめてから、理由つきで答えてください。
- 毎朝届く千件の名簿。順位は昨日からほとんど動かないが、毎日そろえ直す必要がある
- 100万件の会員データ。これから1日に何万回も「この人はいる？」と聞かれる
- 財布の中の12枚のレシートから、今日の1枚をいま1回だけさがす
ヒント1（考え方）
1は「来る列の素性」を、2は「何回やる？」を、3は「量と回数」を見てください。どれも本文のケースのどれかに対応しています。
こたえ（のひとつ）
1はほぼそろった列なので差しこみ（ケース2の実測どおり、たばねより少ない回数で済みます）。2はそろえる代金を払ってでも、そろえてから二分——何万回もさがすなら初日に元が取れます（ケース1の表の延長です）。3はまっすぐさがす——12枚を1回なら最悪12回で、準備の38回を払う理由がありません。
歩いてきた道（コース4の総括）
- 手順——曖昧さがなく、必ず終わる。良し悪しは秒ではなく「くらべた回数」で測る（レッスン1）
- さがす——まっすぐは比例のかたち。半分に切る速さは、「そろっている」という前提への信頼で買う（レッスン2・3）
- ならべる——差しこみは最悪「倍になったら4倍」。分けてたばねる速さは、控えの紙という置き場代で買う（レッスン4・5）
- かたち——回数の伸び方には名前がある。かたちが同じなら、機械を取りかえても運命は同じ（レッスン6）
- おぼえておく——同じ計算を二度しない。時間を空間で買う、もうひとつの取り引き（レッスン7）
- 選ぶ——最強は存在しない。「量は」「何回」「置き場は」の3つを聞けば、状況が選ばせてくれる（このレッスン）
庭の、次の区画へ
このコースの目の使い方は、画面の外でも働きます。引っ越しの段取り、料理の同時進行、本棚の整理——「量は」「何回」「置き場は」と聞いてから手を動かすのは、もうアルゴリズムの思考です。
そして庭には、つづきの区画があります。この8レッスンで、どの手順も「必ず終わる」ことを当たり前のように頼ってきましたが、その当たり前は崖のふちに立っています——どんなプログラムでも終わるかどうかを実行せずに見抜けるか、コース5「計算できる、とはどういうことか」で紙の機械とともに確かめます。コース2で自分の言語を作った人なら、まちがいを実行前に捕まえる目を作るコース6「型のはなし」の扉も開いています。
修了、おめでとうございます！ あなたはもう、手順を「かたち」で見る目を持っています——日常の段取りもプログラムも、その目で見れば同じ風景です。