半分に切れば64版が6回になる
一言でいうと
二分探索はツールではなく手順です。良いと悪いを機械が判定できるようにした瞬間、64個のビルド履歴も4096行のデータも、6回と12回に減ります。
なぜ必要なのか
現場で最もよく聞く文が2つあります。「先週までは動いたんですが」と「昨日届いたファイルでだけ落ちるんです」です。2つはまったく別の話に聞こえますが、構造は同じです。どこかに境界が1つあり、その手前は問題がなく、その先は問題があるのです。探しているのは、その境界です。
境界を探す最も自然な方法は、先頭から1つずつ見ることです。ビルド64個を1つずつ実行すると、最悪の場合は64回で、1回に30秒かかるなら32分です。データ4096行を1行ずつ入れてみると、4096回です。その間、顧客企業の担当者が隣で待っています。
半分ずつに切ると、数字が変わります。候補が63個なら6回、4096個なら12回、100万個でも20回です。候補が2倍になるたびに増える回数は、1回です。この性質が、現場での仕事の性格を変えます。データが大きくなるほど、逐次探索との差は開く一方です。
どう動くのか
二分探索が成立するには、3つのものが必要です。
1つ目は、機械が判定できることです。「少しおかしく見える」は判定ではありません。判定器は、入力を受け取って良い・悪いのどちらかを出すプログラムでなければならず、人が画面を見て首をかしげる手順が混ざると、20回も繰り返せません。git bisectがgit bisect run <스크립트>(プレースホルダーはスクリプトです)という形をしている理由がここにあります。その規約では、終了コード0は良い、1から124までは悪い、125は判定不能(スキップ)です。このラボも、同じ約束を使います。
2つ目は、性質が単調であることです。境界の手前はすべて良く、その先はすべて悪くなければなりません。途中で直ってまた壊れた履歴だと、二分探索は「最初に悪くなったビルド」ではなく「どれかの悪いビルド」を返します。データの側も同じです。1行だけで落とす場合は単調ですが、2行が一緒にあるときだけ落ちる場合は単調ではなく、断片に分けた瞬間に2行が別々になって、両方とも通ってしまいます。
3つ目は、候補に順序があることです。ビルドには時間順があり、ファイルには行順があります。順序のない候補(設定項目20個)は、二分ではなくまとめて半分ずつ切る方式で、同じ原理を使います。
Python標準ライブラリのbisectモジュールは、ソート済みの配列で値の位置を探す関数を提供します。私たちがすることは、配列の代わりに判定器を呼び出す探索で、骨組みは同じです。既知の良い位置をlo、既知の悪い位置をhiとし、間が1つになるまで真ん中を尋ねて、片側を引き寄せます。候補がn個のときに必要な質問の数は、log2(n)を切り上げた値です。1回尋ねるたびに候補が半分になるので、nを1にするには、2を何回掛けるとnになるかを数えればよいのです。
후보 63개 → 6번 후보 4096개 → 12번
후보 100만개 → 20번 후보 10억개 → 30번
判定不能は特別な値です。起動しないビルド、依存モジュールが抜けたビルド、その日だけネットワークが止まっていたビルドが、これに当たります。これを「悪い」と数えると、境界が手前へ押されて、見当違いのビルドを犯人に指名します。そのため3つ目の値を用意し、出会ったら隣へ1つずれて、もう一度尋ねます。区間がまるごと判定不能なら、1つのビルドを指名せず、残った区間をそのまま報告します。範囲を絞ったことも成果です。
現場での姿
1つ目は、判定器を作る前に探索を始めてしまうことです。真ん中のビルドを実行して、「うーん、遅い気もする」と言いながら目で判定すると、10回ほど進んだころには、自分がどちらを良いと言ったのか思い出せません。判定器を先に作れば、探索はただのループです。
2つ目は、境界を見つけて検証しないことです。探索は対数ですが、検証は線形です。境界より後ろのビルドを全数で実行して、すべて悪いことを確認するコストは、最初から逐次探索をしたのと同じです。それでも1回はやるべきです。単調でない履歴では、二分探索は黙って間違った答えを返すからです。時間がなければ、少なくとも境界のビルドが悪いことと、その1つ前のビルドが良いことの、2回は確認します。
3つ目は、データ側の二分でヘッダー行をなくすことです。CSVを半分に切りながらヘッダー行を外すと、後ろの断片は1行目を列名として読んで、見当違いに失敗します。そうなるとすべての断片が悪になり、探索は1行目を指します。断片を作るときは、ヘッダー行を必ず付けます。
4つ目は、回数を数えないことです。報告書に「二分探索で見つけました」とだけ書くと、顧客はその手順の価値がわかりません。「候補4096個を12回で絞りました」と書けば、次回も同じ手順を使おうという話が出ます。数字が方法を売るのです。
実務で本当に大切なこと
- 判定器が先です。良いと悪いを機械が判定できなければ、探索は始められません。
- 判定不能を悪に丸めません。3つ目の値を用意して、隣へずれていきます。
- 単調を疑います。境界を見つけたあと、最低2回、できれば全数で確認します。
- 回数を記録します。逐次探索なら何回だったかを一緒に書いて初めて、手順が売れます。
次のラボですること
顧客企業のビルド64個と新しい入力4096行を手に、良い・悪い・判定不能を判定する判定器をまず作ります。その判定器で履歴を半分ずつ切って最初に悪くなったビルドを探し、起動しないビルドに出会ったときに避けて通る道を付けます。同じ原理をデータに適用して、ローダーを落とす行を12回で見つけ、境界が本当に境界かを全数で検証したうえで、逐次探索なら何回だったかを一緒に書いて、1枚で報告します。