7

我在“Crack the Coding Interview”一书中遇到了这个问题。

给定笛卡尔平面上的两条线，确定两条线是否相交。

这是解决方案：

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;
    }
}

为什么它没有简单的解决方案，如果斜率不同，那么它们将相交。为什么 epsilon 和 y 截距。

在建议中它说

不要假设斜率和 y 截距是整数。了解浮点表示的局限性。永远不要检查与 的相等性==。

4

4 回答 4

9

“解决方案”是错误的。

此“解决方案”中隐含的概念是，已传递的参数不准确，即在intersect调用之前，这些值已经过计算，可能会产生带有舍入误差的结果。因为值中存在错误，所以如果精确计算会相等的数字是不相等的。为了将这些视为相等，此“解决方案”将某些实际上不相等的值视为相等。

这种推理的一个缺陷是intersect例程不知道错误可能有多大，因此没有基础知道epsilon它应该使用什么值。理想值可能为零，也可能是一百万。鉴于所提供的信息，所使用的值 1e-5 在任何工程原理中都没有依据。不仅如此，没有使用绝对错误的基础，就像这段代码一样。根据具体情况，使用的适当容差可能是相对误差、以 ULP 命名的误差或其他一些技术。根本没有理由相信true当传递的参数理想地表示相交线但以某种未知方式计算时，此代码将返回。

另一个缺陷是例程错误地接受不相等的相等值。该例程将报告为不与许多相交的线相交。这段代码并没有解决例程返回错误答案的问题；它只是改变了返回错误答案的情况，并且很可能大大增加了错误答案的数量。

于 2012-11-05T15:00:23.063 回答
5

首先，如果坡度不同，它们将相交的简单解决方案并不完整。它们可以具有相同的斜率和截距，因此是相同的。

建议所说的 epsilon 是因为计算机中的数字表示不准确。根据IEEE 标准，一个 double 具有大约 15 个精确计算的数字，因此斜率和截距可能会由于先前的计算而产生舍入误差，因此使用 == 进行简单检查可能会得出它们不相同，而它们仅相差一个舍入误差.

于 2012-11-05T14:05:02.687 回答
4

为什么它没有简单的解决方案，如果斜率不同，那么它们将相交。为什么 epsilon 和 y 截距。

该解决方案考虑了浮点运算引起的近似误差。由于浮点数并不代表所有可能的实数，而是一个相对较小的子集（在 [-1,+1] 区间中更密集），当您必须处理浮点算术时，通常使用阈值来执行相等检查。

epsilon 值表示一个阈值，在该阈值下 2 个不同的浮点值将被视为相等。

于 2012-11-05T14:02:30.730 回答
1

在这一切之下，数字在处理时都被转换为二进制。不可能将大多数浮点数表示为精确的二进制数（因为它们将是 1 和 0 的无限序列），因此通过截断二进制序列来进行近似。例如，浮点数 0.1（即：十分之一）不能表示为精确的二进制数，而是用看起来像 0.000110011 的近似值表示……截断这个二进制数会导致潜在的舍入错误，因此确切的相等“==”可能会导致错误的响应，而实际上正是这种舍入误差给出了假阴性。引入 epsilon 试图通过说“低于这个数字的任何东西我们认为为零”来避免这些错误。请参阅“二进制分数”部分维基百科阅读更多。

于 2012-11-05T14:12:23.810 回答