ソフトウェア開発とプロジェクト管理
正しく動くことが分かっているファームウェアの版の後に1,000個のコミットがあり、最新のコミットでは不具合が起こる。不具合はある1つのコミットで入り、それ以降のコミットではすべて起こるとする。git bisect のように二分探索で原因のコミットを特定するとき、ビルドしてテストする回数の最大値はどれか。
- A3回
- B10回
- C500回
答えと解説を見る
正解：B. 10回
原因の候補は1,000個のコミットのどれかで、真ん中のコミットを試すたびに候補を半分に絞れます。2¹⁰ = 1,024 ≥ 1,000 なので、最大で10回のテストで1つに特定できます。古い方から1つずつ試すと最悪で999回、平均でも約500回かかるので、二分探索の効果は大きくなります。この方法を使うには、どのコミットでもビルドとテストができるように、壊れた状態のコミットを共有のブランチに入れないことが大切です。
- A. 1,000 = 10³ から、底を10とした対数で考えた値です。1回のテストで候補は半分にしか絞れないので、底は2です。
- B. 正しい。2¹⁰ = 1,024 ≥ 1,000 なので、10回で特定できます。
- C. 古い方から1つずつ試したときの平均に近い回数で、二分探索ではずっと少なくなります。