C++ STL 向量排序 - 损坏和清零

Question

我正在开发的程序旨在处理大量数据并生成至少 2^34 布尔数据。这些数据在程序运行过程中静态生成和清除（每个实例仅对一部分进行排序），最后将至少 2^21 行统计数据组成的向量传递到最后阶段进行进一步处理。

但是，STL 排序对于某些输入数据会失败。排序完成其过程后，某些向量行将被清零或损坏。似乎我唯一的选择是尝试对混合快速排序/插入排序算法进行硬编码。

如果您表达您的想法，我将不胜感激。干杯。

---

最后阶段数据的数据结构：

struct statisticalValues{
    unsigned long long id;      //index id
    unsigned int col_Sum;       //Sum: total number of 1s for each combination
    unsigned int col_Relevancy; //Relevancy = total number of 1s produced by (Comb AND Rel)
    float col_Sensitivity;      //Sensitivity= Relevancy / X
    float col_Precision;        //Precision= Relevancy / Sum
};
extern vector<statisticalValues> statistics;

调用STL排序：

sort(statistics.begin(), statistics.end(), BySensitivity());

比较标准：

#define EPSILON 0.0001 // user-defined tolerance for equality of floating-point numbers
struct BySensitivity {
    bool operator()(statisticalValues const &a, statisticalValues const &b) const {
        float sensitivityDif = b.col_Sensitivity - a.col_Sensitivity;

        if((sensitivityDif < EPSILON) && (sensitivityDif > -EPSILON)){
            return ((b.col_Precision - a.col_Precision) < EPSILON);
        }else{
            return (sensitivityDif < -EPSILON);
        }
    }
};

将被损坏的样本数据行（无特定顺序）：

id,col_Sum,col_Relevancy,col_Sensitivity,col_Precision
1568676,5353,3696,94.166,69.045
1770228,5353,3696,94.166,69.045
2040533,5353,3696,94.166,69.045
2053376,5353,3696,94.166,69.045
1231712,4668,3425,87.261,73.372
1946656,4668,3425,87.261,73.372
1948021,4668,3425,87.261,73.372

通过 STL 排序进行损坏和清零后：

id,col_Sensitivity,col_Precision
10540996614775448722,5.8399e-34,5.8399e-34
8589934369,0.0000,0.0000
0,0.0000,0.0000
0,0.0000,0.0000
0,0.0000,0.0000
0,0.0000,0.0000
0,0.0000,0.0000

---

---

实施建议的修改后：

比较标准：

struct BySensitivity {
    bool operator()(statisticalValues const &a, statisticalValues const &b) const {
        float sensitivityDif = b.col_Sensitivity - a.col_Sensitivity;

        if((sensitivityDif <= EPSILON) && (sensitivityDif >= -EPSILON)){
            return ((b.col_Precision - a.col_Precision) < -EPSILON);
        }else{
            return (sensitivityDif < -EPSILON);
        }
    }
};

感谢@Mark-B、@btilly、@David-Thornley、@sth 和@Daniel-Gallagher

Answer 1

您的比较器没有实现严格的弱排序。例如，两个项目AandB等于col_Sensitivity和col_Precision，A<B和B<A均为 true。正如您可以想象的那样，尝试使用实际上不提供排序的排序函数进行排序可能会产生未定义的行为。

感谢（并引用）@David Thornley 提供的标准参考：

标准，25.3/3 的一部分：“为了使算法正常工作，comp 必须对值进行严格的弱排序。” 这意味着没有严格的弱排序是未定义的（标准什么也没说）。

我认为在这种情况下你只想完全删除所有 epsilon 检查：

struct BySensitivity {
bool operator()(statisticalValues const &a, statisticalValues const &b) const {
    float sensitivityDif = b.col_Sensitivity - a.col_Sensitivity;

    if(sensitivityDif == 0.0)){
        return ((b.col_Precision - a.col_Precision) < 0.0);
    }else{
        return (sensitivityDif < 0.0);
    }
}};