最後の手段は二分探索

2020年1月18日

開発をしていて、「あの時は確実に動いてたのに、なぜか動かなくなった!」という状況、ありますよね。

本当はデバッガを使って理詰めでバグを追及できればそれに越したことはないのですが、嫌になるほど理不尽なバグというのが、組み込み開発では往々にしてあります。

最終的には、SVN や Git などの履歴をロールバックしながら、どの瞬間にバグが入り込んだのかを実機で延々と追い求める羽目になります。この行為は非効率の極みのように思われがちですが、戦略的にやれば、たかだか数回で済みますよ、というお話です。

戦略

SVN の場合、コミット履歴が連続するリビジョン番号で表現されますので、まずはそれを前提として話を進めます。

今バグが出ているリビジョン番号を仮に 200 とします。そして、100 の時点ではバグがなかったことが確実にわかっている状況だとします。この場合、まずノートなどに次のように書きます。下の余白は広めに取っておくほうがいいでしょう。

この戦略では常に、最も下にある2つの数字の平均を取り、それを次に試すリビジョン番号にする、というサイクルを繰り返します。今、最も下の2つの数字は 100 と 200 ですから、150 が次の試行のリビジョン番号になります。

リビジョン 150 を実機で試した結果に応じて、どちらかの欄の一番下に 150 と記入してください。仮に 150 にバグがなかったとすると、こうです。

ここで、最も下の2つの数字は 150 と 200 になりましたから、次の試行のリビジョン番号は 175 です。仮に 175 にバグがあったとすると、次はこうなります。

ちなみに平均値が小数の場合は、切り捨てと切り上げのどちらを選んでも構いません。そして、このサイクルを「2つの数字が隣接するまで」繰り返します。たとえば次のように。

この瞬間、バグはリビジョン 173 で入り込んでいたことが判明しました。

まとめ

この間、試行回数は7回しかかかっていません。

この例では最初のリビジョンの差が 100 でしたが、これが仮に 1000 だったとしても、試行回数は11回で済みます。直感に比べて少なく済んでいると思いませんか。Git の場合はリビジョン番号という取り扱いではありませんが、本質的には同じことです。

この方法を積極的に実践することはお勧めしませんが、「最悪、ごり押しで試せば1日で突き止められる」という選択肢を心の奥に持っておくことは、精神的安定をもたらしてくれます。ぜひ、覚えておいてください。

注意点

繰り返しの中に誤情報が一つでも含まれていると、誤った結論を導いてしまう点に注意してください! 記憶や先入観に囚われて近道をしようとしてはいけません。予断を差し挟みたくなる誘惑を断ち切って、ルールを貫徹することがポイントです。