コラム 2 (「AHA! アルゴリズム」) の「プログラミング パール」では、ソートやツリー トラバーサルなどのさまざまなプロセスでバイナリ検索がどのように役立つかについて説明しています。ただし、バイナリ検索は「プログラムのデバッグ」で使用できると述べています。誰かがこれがどのように行われるか説明してもらえますか?
2527 次
7 に答える
8
100 行のプログラムのどの行にバグがあるのかわからない場合は、最初の 50 行を実行して残りを飛ばしてみてください。問題が発生した場合、この最初のセグメントにバグが含まれていることがわかります。次に、これを分割して最初の 25 行を実行し、問題があるかどうかを確認し、十分に短い部分がわかるまで繰り返します。
二分探索の背後にある考え方は、バグのある小さな領域を特定/分離することです。ただし、すべての方法と同様に、これはすべての状況に適用できるわけではありません。例: 再帰関数は、そのようなツールにとって非常に扱いにくくなります。実行パスが多すぎると、コードをセグメント化して実行することが難しくなる場合があります。
于 2009-05-09T19:57:32.510 に答える
6
もう 1 つの可能性は、バグがあり、2 月のリリースにはなかったことがわかっているが、4 月のリリース (または 4 月のリリース候補) にあったということです。実際にユーザーにバグを出荷することはありません。右？）。
リビジョン管理履歴を手動でバイナリ検索して、バグがいつ導入されたかを絞り込むことができます。最初に、2 つのリリースの中間にあるコードをチェックアウトし、ビルドして、バグがあるかどうかを確認します。いつ導入されたかがわかるまで、パーティショニングを続けます。どこからバグを探し始めればよいかわからない場合、これは非常に効果的です。特に、かなり小規模なコミットを行う場合はそうです。
Subversionにはリポジトリ全体のリビジョン番号があるため、これはSubversionで非常にうまく機能します。2 月のリリースがリビジョン 533 で、4 月のリリースがリビジョン 701 の場合、リビジョン 617 に更新してテストし、そこから先に進みます。(実際には、頭の中でそれほど多くの計算を行う必要がないので、通常は 600 に丸めます。) 絞り込み始めると、コミットのコメントを見て、知識に基づいた推測を行います (「私は本当にそうではありません。このコミットはそれを壊したと思います」)、そのため、通常、すべてのログ2 (n) チェックアウトを行う必要はありません。
私はGitを使用したことがありませんが、組み込みの " bisect " コマンドを使用して、これをさらに一歩進めています。開始点 (動作することがわかったのはいつですか?) と終了点 (壊れていることに気付いたのはいつですか?) を指定すると、二分探索で中間点のコードが自動的に取得されます。次に、ビルドしてテストした後、このリビジョンが成功したか失敗したかを伝えます。次に、次の中間点のコードを取得します。revごとにコマンドを実行し、コマンドの終了コードを使用してrevが成功か失敗かを判断するように指示することもできます。その時点で、完全自動で実行できます。
于 2009-05-09T20:43:35.130 に答える
5
二分探索は、次の方法でデバッグに役立つ場合があります。
- コントロールが特定のポイントに到達する必要があり、到達していないと思われるとします。最初と最後のコード行に print ステートメントを入れます。最初のステートメントの結果は表示されるが、2 番目のステートメントの結果は表示されないとします。真ん中に print ステートメントを入れて、やり直してください。このようにして、コード行のスペースに対してバイナリ検索を使用して、バグをゼロにします。
- バージョン管理システムを使用しているとします。バージョン 10 はすべてのテストに合格しました。まもなくリリースされるバージョン 70 は、いくつかのテストに失敗します。バージョン 40 をチェックアウトし、テストを実行します。正常に動作する場合は、バージョン 55 を試してください。バージョン 40 が失敗した場合は、バージョン 25 を試してください。このようにして、バグがプログラムに侵入した最初のバージョンをゼロにするために、プログラム バージョン スペースでバイナリ検索を使用します。
于 2009-05-09T20:02:03.607 に答える
2
バグがあり、それがどこにあるのかわからないとしましょう。ブレーク ポイントをランダムに配置することも、コードをシングル ステップで実行して、各ストップでデータを検証することもできます。ただし、より良い戦略は、見ているコード ブロックの真ん中のスポットを選ぶことです。そこに問題がある場合は、開始地点と現在の地点の中間地点を選択して、もう一度試してください。問題が存在しない場合は、現在のスポットと最後のスポットの中間にあるスポットを選択して、もう一度やり直してください。コードの量を、停止/再起動よりも効率的に 1 ステップ実行するのに十分な大きさのブロックに絞り込むまで、この方法を続けます。これは基本的に、コードに対してバイナリ検索を実行することです。
于 2009-05-09T19:59:28.980 に答える
1
完全なアルゴリズムはDelta Debuggingと呼ばれ、Andreas Zeller によって開発されました。Andreas Zeller は、情報学の教授であり、Why programs failという書籍の著者でもあります。
ただし、これは二分探索だけではありません。二分探索は最初にのみ行われ、二分探索で入力が最小化されなくなると、別のアプローチが取られます。
完全なアルゴリズムを理解するのはそれほど難しくなく、実際には非常に単純です。ただし、バグを再現し、問題が再現されたかどうかの決定を適用することが難しい場合があります。
この本のほかに、Udacityには無料のオンライン コースがあります。短いバージョンを好む場合は、IEEE の論文を読んでください。
于 2015-08-31T20:51:09.430 に答える
0
コードをコメントアウトしたり、ログコメントを追加したり、単にブレークポイントを設定したりできます
エラーはないが機能しない機能のコードに最適で、自己疑いでいっぱいです
最初にブレークポイントをコードの途中に設定します。問題がなければ、そこに問題がないことがわかります。
次に、コード ポイントの 75% に設定します。ここで問題が発生した場合は、コードの 50% と 75% の間にあることがわかります。
次に 57% に設定します
繰り返しますが、問題がある場合は、もう一度半分に分割します
基本的に、コードを再分析するために知的に何時間も費やすのではなく、数分で問題を見つけることができます
その後、それを修正するのはあなた次第です。
于 2015-08-09T00:49:29.883 に答える