7

私は本「Crack the Coding Interview」からこの問題を抱えています。

デカルト平面上の 2 つの線が与えられた場合、2 つの線が交差するかどうかを判断します。

解決策は次のとおりです。

public class Line {

    static double epsilon = 0.000001;
    public double slope;
    public double yintercept;

    public Line(double s, double y) {
        slope = s;
        yintercept = y;
    }

    public boolean intersect(Line line2) {
        return Math.abs(slope - line2.slope) > epsilon ||
        Math.abs(yintercept - line2.yintercept) < epsilon;
    }
}

勾配が同じでない場合、それらが交差するという単純な解決策がないのはなぜですか。イプシロンと y が交差する理由。

提案では、それは言う

傾きと y 切片が整数であると想定しないでください。浮動小数点表現の制限を理解する。との等価性を決してチェックしないでください==。

4

4 に答える 4

9

「解決策」が間違っています。

この「解決策」に暗示されているのは、渡された引数が不正確であり、intersectが呼び出される前に、値が丸め誤差のある結果を生成する可能性のある計算の対象になっているという概念です。値には誤差があるため、正確に計算すれば等しくなるはずの数が等しくなくなります。これらを等しいと認識するために、この「ソリューション」は、実際には等しくないいくつかの値を等しいものとして受け入れます。

この推論の欠点の 1 つは、intersectルーチンがエラーの大きさを認識していないため、どの値を使用すべきかを知る根拠がないことepsilonです。理想的な値はゼロかもしれませんし、100 万かもしれません。使用される値 1e-5 は、提供された情報が与えられた工学原理に基づいていません。それ以上に、このコードのように絶対誤差を使用する根拠はありません。状況に応じて、使用する適切な許容誤差は、相対誤差、ULP で指定された誤差、またはその他の手法である可能性があります。true理想的には交差する線を表すが、未知の方法で計算された引数が渡されたときに、このコードが返されると信じる理由はまったくありません。

もう 1 つの欠点は、ルーチンが等しくない値を誤って等しいものとして受け入れることです。ルーチンは、交差する多くの線が交差しないと報告します。このコードは、間違った答えを返すルーチンの問題を解決していません。間違った回答が返されるケースが変わっただけで、間違った回答の数が大幅に増加した可能性があります。

于 2012-11-05T15:00:23.063 に答える
5

まず、勾配が同じでない場合に交差するという単純な解決策は完全ではないためです。それらは同じ勾配と切片を持つ可能性があるため、同一になります。

提案が言うようにイプシロンは、コンピュータの数の表現が正確ではないためです。IEEE標準によると、doubleには約15の正確に計算された桁があるため、傾きと切片には以前の計算による丸め誤差が生じる可能性があります。したがって、==を使用した単純なチェックでは、丸め誤差が異なるだけで、同一ではないことがわかります。 。

于 2012-11-05T14:05:02.687 に答える
4

勾配が同じでない場合、それらが交差するという単純な解決策がないのはなぜですか。イプシロンと y が交差する理由。

このソリューションでは、浮動小数点演算による近似誤差が考慮されます。浮動小数点数はすべての可能な実数を表すわけではありませんが、比較的小さなサブセット ([-1,+1] 間隔でより密集) であるため、浮動小数点演算を処理する必要がある場合は、しきい値を使用して等値を実行するのが一般的です。チェックします。

イプシロン値は、2 つの異なる浮動小数点値が等しいと見なされるしきい値を表します。

于 2012-11-05T14:02:30.730 に答える
1

その下で、数値はすべて処理時に 2 進数に変換されます。ほとんどの浮動小数点数を正確な 2 進数として表現することはできません (1 と 0 の無限の連続になるため)。そのため、2 進数シーケンスを切り捨てて近似値を作成します。たとえば、浮動小数点数 0.1 (つまり、10 分の 1) は正確な 2 進数では表現できず、0.000110011 のような近似値で表されます... この 2 進数の切り捨ては、潜在的な丸め誤差を引き起こすため、実際にはこの丸め誤差が偽の負を与えているのに、正確な等価 "==" は誤った応答を引き起こす可能性があります。イプシロンを導入すると、「この数値を下回るものはすべてゼロと見なす」と言って、これらのエラーを回避しようとします。の「バイナリの分数」セクションを参照してくださいウィキペディアでもっと読む。

于 2012-11-05T14:12:23.810 に答える