C ++ STL Vector Sorting - искажение и обнуление - PullRequest
Новая
       17

C ++ STL Vector Sorting - искажение и обнуление

2 голосов
/ 03 февраля 2011

Программа, которую я разрабатываю, предназначена для обработки очень больших объемов данных и генерирования как минимум 2 ^ 34 логических данных.Эти данные статически генерируются и очищаются на протяжении всего выполнения программы (в каждом экземпляре сортируется только часть), и, наконец, вектор с минимальными 2 ^ 21 строками статистических данных передается на последний этап для дальнейшей обработки.

Однако, сортировка STL не удалась для некоторых входных данных.После того, как сортировка завершит свой процесс, некоторые из векторных строк будут обнулены или повреждены.Кажется, единственный вариант, который у меня есть, - это попытаться жестко закодировать гибридный алгоритм сортировки Quicksort / Insertion.

Я ценю, если вы спроецируете свои мысли.Cheers.

Структура данных данных для конечной стадии: 

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-Галлахер

Ответы [ 2 ]

4 голосов
/ 03 февраля 2011

Ваш компаратор не реализует строгий слабый порядок.Например, два элемента A и B с равными col_Sensitivity и col_Precision, оба значения A <<code>B и B <<code>A имеют значение true.Как вы можете себе представить, попытка сортировки с помощью функции сортировки, которая фактически не обеспечивает упорядочение, может привести к неопределенному поведению.

Спасибо (и цитируем) @David Thornley за стандартную справку:

Standard, часть 25.3 / 3: «Для правильной работы алгоритмов comp должен вызыватьстрогое слабое упорядочение по значениям ".Это означает, что отсутствие строгого слабого порядка не определено (Стандарт ничего не говорит).

Я думаю, что в этом случае вы просто хотите полностью удалить все проверки эпсилон: 

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);
    }
}};
4 голосов
/ 03 февраля 2011

Сортировка STL может повредить данные, если оператор сравнения может выдавать противоречивые результаты, такие как x

Ваш оператор сравнения может давать противоречивые результаты.

...