在比较浮点数时使用epsilon是否会破坏严格弱排序？

html5 • • 问答

以下课程是否打破了严格的弱排序（与常规相比std::less（因此忽略边缘情况值，例如 Nan））

struct LessWithEpsilon
{
    static constexpr double epsilon = some_value;
    bool operator() (double lhs, double rhs) const
    {
        return lhs + epsilon < rhs;
    }
};

LessWithEpsilon lessEps{};

回答

来自https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings

  1. 不可比性的传递性：对于所有x，y，zin S，如果x与 不可比y（意味着既不是x < y也不y < x是true）并且如果y与 不可比z，则x与 不可比z。

同样，来自https://en.cppreference.com/w/cpp/named_req/Compare

如果equiv(a, b) == true and equiv(b, c) == true，那么equiv(a, c) == true

有了{x, y, z} = {0, epsilon, 2 * epsilon}，这条规则就被打破了：

  • !lessEps(x, y) && !lessEps(y, x) && !lessEps(y, z) && !lessEps(z, y)
    但是lessEps(x, z)。
  • equiv(x, y) == true and equiv(y, z) == true但是equiv(x, z) == false（作为x + epsilon < z）

因此，该类打破了严格弱序。

  • @MarekR: During review, I saw that problem. My coworker asked for reference, and I didn't find direct answer for that, So I create that answer (which I think might help others).
以上是在比较浮点数时使用epsilon是否会破坏严格弱排序？的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>