Функция qsort в C неожиданное поведение?

Я испытываю странное и неожиданное поведение функции qsort(). У меня есть свой список узлов, и каждый из них содержит два значения, на основании которых я хочу отсортировать свой список (технически, массив).

Например:

Если у меня есть оригинальный массив, который выглядит следующим образом (1-й элемент р, 2-й элемент т):

[0,10 | 1], [0,05 | 0], [0,10 | 0], [0,05 | 2], [0,10 | 2], [0,15 | 1], [0,05 | 1]

После сортировки это должно выглядеть так:

[0,05 | 0], [0,05 | 1], [0,05 | 2], [0,10 | 0], [0,10 | 1], [0,10 | 2], [0, 15 | 1].

Структурный узел:

typedef struct node{
    int t;
    double p;
}node;

Функция сравнения называется qsort(nodes, num_of_node, sizeof(node), compare_pairs);

static int compare_pairs(const void *n1, const void *n2){

const node *na1= n1;
const node *na2= n2;

if(na1->p < na2->p) return -1;
if(na1->p > na2->p) return 1;

// At this point, value p is equal, so I am sorting based on t

if(na1->t < na2->t) return -1;
if(na1->t > na2->t) return 1;

return 0;

проблема

Нежелательное поведение начинается с 3. ШАГ, который выглядит так:

Список: [0.10 | 2] [0,10 | 999] [0,10 | 999] [0,15 | 999] [0,15 | 999] [0,15 | 1] [0,25 | 999]

И должно выглядеть так:

Список: [0.10 | 2] [0,10 | 999] [0,10 | 999] [0,15 | 1] [0,15 | 999] [0,15 | 999] [0,25 | 999]

Начальный список: [0.25 | 999] [0,15 | 999] [0,15 | 999] [0,10 | 999] [0,10 | 999] [0,05 | 999] [0,05 | 999] [0,05 | 999] [0,05 | 999] [0,05 | 999]

  1. ШАГ:

Стирание (мин) узла 0.050000...

Стирание (мин) узла 0.050000...

Создание (новый) узел 0.100000...

Список: [0.05 | 999] [0,05 | 999] [0,05 | 999] [0,10 | 1] [0,10 | 999] [0,10 | 999] [0,15 | 999] [0,15 | 999] [0,25 | 999]

  1. ШАГ:

Стирание (мин) узла 0.050000...

Стирание (мин) узла 0.050000...

Создание (новый) узел 0.100000...

Список: [0.05 | 999] [0,10 | 1] [0,10 | 2] [0,10 | 999] [0,10 | 999] [0,15 | 999] [0,15 | 999] [0,25 | 999]

  1. ШАГ:

Стирание (мин) узла 0.050000...

Стирание (мин) узла 0.100000...

Создание (новый) узел 0.150000...

Список: [0.10 | 2] [0,10 | 999] [0,10 | 999] [0,15 | 999] [0,15 | 999] [0,15 | 1] [0,25 | 999]

  1. ШАГ:

Стирание (мин) узла 0.100000...

Стирание (мин) узла 0.100000...

Стирание (новый) узел 0.200000...

Список: [0.10 | 999] [0,15 | 999] [0,15 | 999] [0,15 | 1] [0,20 | 1] [0,25 | 999]

  1. ШАГ:

Стирание (мин) узла 0.100000...

Стирание (мин) узла 0.150000...

Создание (новый) узел 0.250000...

Список: [0.15 | 999] [0,15 | 1] [0,20 | 1] [0,25 | 1] [0,25 | 999]

  1. ШАГ:

Стирание (мин) узла 0.150000...

Стирание (мин) узла 0.150000...

Стирающий (новый) узел 0.300000...

Список: [0.20 | 1] [0,25 | 1] [0,25 | 999] [0,30 | 1]

  1. ШАГ:

Стирание (мин) узла 0.200000...

Стирание (мин) узла 0.250000...

Стирающий (новый) узел 0.450000...

Список: [0.25 | 999] [0,30 | 1] [0,45 | 1]

  1. ШАГ:

Стирание (мин) узла 0.250000...

Стирание (мин) узла 0.300000...

Создание (новый) узел 0.550000...

Список: [0.45 | 1] [0,55 | 1]

  1. ШАГ:

Стирание (мин) узла 0.450000...

Стирание (мин) узла 0.550000...

Создание (новый) узел 1.000000...

Список: [1.00 | 1]

Общая идея *

На каждом шаге два минимальных узла удаляются из списка, и один новый узел вставляется в список. Вставляемый узел имеет значение t на 1 больше, чем наибольшее в списке, за исключением того, что он не сравнивается со значением t 999. Если наибольшее в списке имеет t = 999, то вставленный будет есть 1.

Найти наибольшее т:

int max_t(node *nodes, int num, double p){
int max_t= 0;
int i;
for(i=0; i<num; i+=1){
    if(nodes[i].p== p && nodes[i].t != 999){
        if(nodes[i].t > max_t){
            max_t = nodes[i].t;
        }
    }
}
return max_t;

Основной код:

node *nodes = malloc(num_of_nodes*sizeof(node));
int i;
for(i=0; i<num_of_nodes; i+=1){
    node n;
    n.t = 999;
    n.p = *(probabs+ i);
    *(nodes+i) = n;
}

qsort(nodes, num_of_nodes, sizeof(node), compare_pairs);

while(num_of_nodes> 1){

    printf("\n%d. STEP:\n", z);
    z += 1;

    // 2) Find two min nodes
    node *min_n1 = malloc(sizeof(node));
    node *min_n2 = malloc(sizeof(node));

    *min_n1 = nodes[0];
    printf("Erasing (min) node %lf...\n", min_n1->p);
    nodes= erase_node(nodes, min_n1, num_of_nodes);
    num_of_nodes -= 1;

    *min_n2 = nodes[0];
    printf("Erasing (min) node %lf...\n", min_n2->p);
    nodes= erase_node(nodes, min_n2, num_of_nodes);
    num_of_nodes-= 1;

    // 3) Create new node, add it to the list
    node *new_node = malloc(sizeof(node));
    new_node->p= min_n1->p + min_n2->p;
    double p = new_node->p;
    int max_t = max_t(nodes, num_of_nodes, p);
    new_node->t = max_t + 1;

    printf("Creating (new) node %lf...\n", new_node->p);
    nodes = add_node(nodes, new_node, num_of_nodes);
    num_of_nodes += 1;

    qsort(nodes, num_of_nodes, sizeof(node), compare_pairs);

    printf("List: ");
    int k;
    for(k=0; k<num_of_nodes; k+=1){
        printf("[%.2lf | %d]  ", nodes[k].p, nodes[k].t);
    }
    printf("\n");

Добавить / Удалить узел...

node *add_node(node *nodes, node *n, int num){
nodes = realloc(nodes, (num+1)*sizeof(node));
nodes[num] = *n;
return nodes;

node *erase_node(node *nodes, node *n, int num){
int i;
int index = 0;
for(i=0; i<num; i+=1){
    if(nodes_equal(&nodes[i], n)){
        index = i;
        break;
    }
}

for(i=index; i<num-1; i+=1){
    nodes[i] = nodes[i+1];
}

nodes= realloc(nodes, (num-1)*sizeof(node));

return nodes;

}

   int nodes_equal(node *n1, node *n2){

    return !memcmp(n1, n2, sizeof(node));
 }
Источник

1 ответ

Решение

Проблема у вас с неточностью с плавающей запятой. Ни одно из точных десятичных чисел 0,1, 0,05 и 0,15 не имеет точного представления в двоичной с плавающей запятой.

Использование IEEE 64-bit double представлении, самое близкое представимое значение до 0,15 немного меньше, чем 0,15, а самые близкие представимые значения до 0,05 и 0,10 немного больше, чем 0,05 и 0,10 соответственно. В реализации, использующей округление до ближайшего, это означает, что если вы сложите 0,05 и 0,10, то в итоге получите число, немного большее 0,15, и если вы установите double непосредственно до 0,15, вы получите число чуть меньше 0,15. Эти не будут сравниваться равными.

Это то, что, по-видимому, происходит на вашем шаге 3. Вы удаляете два узла со значениями 0,05 и 0,10 (фактически, как обсуждалось, их действительные значения немного больше, чем эти числа) и складываете их вместе, в результате чего число немного больше 0,15., Это сравнивает больше, чем существующие узлы, чьи реальные значения чуть меньше 0,15, поэтому сортирует по ним.

Пока не ясно, имеет ли это значение для вашего алгоритма? Разве это не заканчивается в том же самом конечном состоянии в любом случае? Если это имеет значение, так как вы, очевидно, храните вероятности в диапазоне от 0,0 до 1,0 включительно, вы можете вместо этого использовать десятичное представление с фиксированной точкой (например, сохранить вероятность, умноженную на 10000 в long int а не double, а затем просто разделить на 10000 для отображения).

Источник
Другие вопросы по тегам