排序比较

Question

我正在将 C++ 代码转换为 Go，但是我很难理解这个比较函数：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>

using namespace std;

typedef struct SensorIndex
{   double value;
    int    index;
} SensorIndex;

int comp(const void *a, const void* b)
{   SensorIndex* x = (SensorIndex*)a;
    SensorIndex* y = (SensorIndex*)b;

    return abs(y->value) - abs(x->value);
}

int main(int argc , char *argv[])
{

    SensorIndex *s_tmp;

    s_tmp = (SensorIndex *)malloc(sizeof(SensorIndex)*200);

    double q[200] = {8.48359,8.41851,-2.53585,1.69949,0.00358129,-3.19341,3.29215,2.68201,-0.443549,-0.140532,1.64661,-1.84908,0.643066,1.53472,2.63785,-0.754417,0.431077,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256,-0.123256};

    for( int i=0; i < 200; ++i ) {
        s_tmp[i].value = q[i];
        s_tmp[i].index = i;
    }

    qsort(s_tmp, 200, sizeof(SensorIndex), comp);

    for( int i=0; i<200; i++)
    {   
        cout << s_tmp[i].index << " " << s_tmp[i].value << endl;
    }

}

我预计 "comp" 函数将允许从最高（绝对）值到次要值排序，但在我的环境中（gcc 32 位）结果是：

1 8.41851
0 8.48359
2 -2.53585
3 1.69949
11 -1.84908
5 -3.19341
6 3.29215
7 2.68201
10 1.64661
14 2.63785
12 0.643066
13 1.53472
4 0.00358129
9 -0.140532
8 -0.443549
15 -0.754417
16 0.431077
17 -0.123256
18 -0.123256
19 -0.123256
20 -0.123256
...

此外，对我来说似乎很奇怪的一件事是，通过使用在线服务执行相同的代码，我得到不同的值（cpp.sh，C++98）：

0 8.48359
1 8.41851
5 -3.19341
6 3.29215
2 -2.53585
7 2.68201
14 2.63785
3 1.69949
10 1.64661
11 -1.84908
13 1.53472
4 0.00358129
8 -0.443549
9 -0.140532
12 0.643066
15 -0.754417
16 0.431077
17 -0.123256
18 -0.123256
19 -0.123256
20 -0.123256
...

有什么帮助吗？

Answer 1

您的比较功能存在错误。你 return 一个 int 这意味着你失去了元素值之间的区别其 绝对差异 小于 1!

int comp(const void* a, const void* b)
{
    SensorIndex* x = (SensorIndex*)a;
    SensorIndex* y = (SensorIndex*)b;

    // what about differences between 0.0 and 1.0?
    return abs(y->value) - abs(x->value); 
}

你可以这样修复：

int comp(const void* a, const void* b)
{   SensorIndex* x = (SensorIndex*)a;
    SensorIndex* y = (SensorIndex*)b;

    if(std::abs(y->value) < std::abs(x->value))
        return -1;

    return 1;
}

一种更现代（也更安全）的方法是使用 std::vector 和 std::sort:

// use a vector for dynamic arrays
std::vector<SensorIndex> s_tmp;

for(int i = 0; i < 200; ++i) {
    s_tmp.push_back({q[i], i});
}

// use std::sort
std::sort(std::begin(s_tmp), std::end(s_tmp), [](SensorIndex const& a, SensorIndex const& b){

    return std::abs(b.value) < std::abs(a.value);
});

Answer 2

此行为是由于使用 abs（一个与 int 一起使用的函数）并向其传递 double 个参数引起的。 double 被隐式转换为 int，在比较它们之前截断小数部分。从本质上讲，这意味着您采用原始数字，去除符号，然后去除小数点右侧的所有内容并比较这些值。所以8.123和-8.9都转换为8，比较相等。由于减法的输入是相反的，因此顺序按幅度降序排列。

您的 cpp.sh 输出反映了这一点；大小在8和9之间的所有值首先出现，然后是3-4s，然后是2-3s，1-2s和小于1的值。

如果您想修复此问题以实际按一般降序排序，您需要一个正确使用 the double-friendly fabs function 的比较函数，例如

int comp(const void *a, const void* b)
{   SensorIndex* x = (SensorIndex*)a;
    SensorIndex* y = (SensorIndex*)b;
    double diff = fabs(y->value) - fabs(x->value);
    if (diff < 0.0) return -1;
    return diff > 0;
}

更新： 进一步阅读，看起来 <cmath> 的 std::abs 已经与 double 一起工作了很长时间，但是std::abs for doubles 仅添加到 C++17 中的 <cstdlib>（其中整数 abs 函数驻留）。 And the implementers got this stuff wrong all the time, so different compilers would behave differently at random. In any event, both the answers given here are right; if you haven't included <cmath> and you're on pre-C++17 compilers, you should only have access to integer based versions of std::abs (or ::abs from math.h), which would truncate each value before the comparison. And even if you were using the correct std::abs, ，使幅度差异小于 1.0 的任何值看起来相等。更糟糕的是，根据执行的特定比较及其排序（因为并非所有值都相互比较），这种影响的后果可能会连锁，因为比较排序更改可能会使 1.0 看起来等于 1.6反过来会看起来等于 2.5，即使 1.0 在相互比较时会被正确识别为小于 2.5；理论上，只要每个数字与其他数字的差值在 1.0 以内，比较结果可能会认为它们彼此相等（病态情况是的，但肯定会出现较小的此类错误）。

要点是，弄清楚这段代码的真实意图的唯一方法是弄清楚它最初编译的确切编译器版本和 C++ 标准，并在那里进行测试.

排序比较

Qsort comparison

go

qsort