アヒルのある日

株式会社AHIRUの社員ブログです。毎週更新!社員が自由に思いついたことを書きます。

二分法で原因を素早く特定しよう!

こんにちは!ダイエットバトルの敗者こと「するどいプランナー」です。

イマニ ミテイロヨ!

 

今回はデータ作成だけではなくバグチェック等の時にも使える「二分法」の考え方についてお話ししようかと思います。

 

二分法は数値解析で解を求める手法の一つで、全体をA/Bの2つのグループに分けて、真ん中の状態を調べることで解がA/Bどっちのグループに入っているかを絞り込んでいく手法です。
この方法の特徴は「1回ごとに範囲が1/2に絞り込まれる」ことです。
この特徴をいろんなところに利用しましょう。

 

 

例えば64個(=2の6乗)のデータから、バグの原因となっているデータを見つけたいとします。

f:id:surudoi_ahiru:20201008172919p:plain

1個ずつ調べるとき

バグの根本原因がわからず、とりあえずデータを特定したいような場合に
id=1を消す⇒動くか確認する
id=2を消す⇒動くか確認する
id=3を消す⇒動くか確認する
...
という手順で調べていくと最大64回繰り返すことになってしまいますが、

 

f:id:surudoi_ahiru:20201008172731p:plain

二分法で調べるとき

id=1~32を消す⇒動くか確認する
id=17~32を消す⇒動くか確認する
id=25~32を消す⇒動くか確認する
id=25~28を消す⇒動くか確認する
...
という手順で調べていくと6回で発見することができます。

 

データが1024個になった場合だと10回で発見できます。データ数が増えるほど効力を発揮するので、二分法も「量の桁が変わる場合、方法を根本的に変える」の一例ですね。
特徴自体はシンプルなので応用範囲は広いと思います。

 

 

まとめ
・範囲を1/2ずつ絞り込む二分法でスピードを上げる


※余談
数値計算には「ニュートン法」というもっと収束が早い手法があります。
これを開発で例えるなら「経験によって予測の範囲を絞り込む」って感じですかね。

 


次回は確率の確認方法の話をしようかと思います。
それではまた!