c - C 意外行为中的 qsort 函数？

Question

我遇到了 qsort() 函数奇怪和意外的行为。我有我的节点列表，每个节点都包含两个值，我想根据这些值对列表进行排序(从技术上讲，是一个数组)。

例如:

如果我有一个看起来像这样的原始数组(第一个元素是 p，第二个元素是 t):

[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 开始。 STEP 看起来像这样:

列表:[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。

找到最大的 t:

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));
 }

Answer 1

您遇到的问题是浮点不精确。精确的十进制数 0.1、0.05 和 0.15 都没有二进制 float 的精确表示。

使用 IEEE 64 位 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 显示)。