2

对于浮点精度的问题，我为浮点数定义了我的自定义比较函数：

bool cmp(double a, double b)
{
    if(abs(a - b) <= eps) return false;
    return a < b;
}

然后我对一些浮点数数组调用排序。我听说一些不好的比较功能会导致排序分段错误。我只是想知道cmp排序是否可以正常工作？一方面，cmp满足关联规则。但另一方面，cmp(x - eps, x) == false&&cmp(x, x + eps) == false并不意味着cmp(x - eps, x + eps) == false.

我没有直接对浮点数使用排序，因为我想要排序的是pair<double, double>. 例如：

(1,2), (2,1), (2.000000001, 0)

我想将 2 和 2.000000001 视为相同，并期望结果为：

(1,2), (2.000000001, 0), (2,1)
4

3 回答 3

5

std::sort需要一个定义严格弱排序的比较器。这意味着，除其他外，必须满足以下条件：

  • 我们定义两个项目a和等价b于( ) 如果a === b!cmp(a, b) && !cmp(b, a)
  • 等价是传递的：a === b&& b === c=>a === c

正如您在问题中已经说过的那样，您的功能cmp()不符合这些条件，因此您不能在std::sort(). 不仅算法的结果将是不可预测的，这很糟糕，除非您实际上正在寻找这种不可预测性（参见randomize）：如果您有一些彼此非常接近的值，以便它们中的任何一个true与一些进行比较，但false对于其他一些，算法可能会进入无限循环。

所以答案是否定的，除非你想冒险冻结你的程序cmp()，否则你不能使用你的函数。std::sort()

于 2012-10-05T11:34:43.157 回答
4

你为什么要费心做一个近似的小于比较？这是没有意义的。

只需严格按实际值对数组进行排序。

然后使用您的近似比较函数来确定您希望哪些元素相等。

（英语中的等价物是臭名昭著的“几乎更好”。想想看。）

于 2012-10-05T11:14:30.140 回答
-1

可以为将相似值分组的浮点定义比较函数。你可以通过四舍五入来做到这一点：

bool cmp(double a, double b)
{
    const double eps = 0.0001;
    int a_exp;
    double a_mant = frexp(a, &a_exp); // Between 0.5 and 1.0
    a_mant -= modf(a_mant, eps); // Round a_mant to 0.00001
    a = ldexp(a_mant, a_exp); // Round a to 0.00001 * 10^a_exp
    // and the same for b
    int b_exp;
    double b_mant = frexp(b, &b_exp); 
    b_mant -= modf(b_mant, eps);  
    b = ldexp(b_mant, b_exp);
    // Compare rounded results.
    return a < b;
}

Nowcmp(a,b)==true暗示a<b， anda==b和a>b都暗示cmp(a,b)==false。

于 2012-10-05T11:44:57.667 回答