3

我正在开发的程序旨在处理大量数据并生成至少 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

4

2 回答 2

5

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

感谢（并引用）@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);
    }
}};
于 2011-02-03T19:30:10.467 回答
4

如果比较运算符会产生不一致的结果，例如 x < y < z < x，则 STL 排序可能会损坏数据。

您的比较运算符可能会产生不一致的结果。

于 2011-02-03T19:24:02.480 回答