Comment comparer les doubles longs avec qsort et par rapport à NaN?

Comment comparer les doubles longs avec qsort() et en ce qui concerne not-a-number ?

Lors du sorting d’un tableau susceptible de ne pas contenir de nombres, j’aimerais placer tous ces NAN à une extrémité du tableau sortingé.


qsort() impose certaines ressortingctions à la fonction de comparaison.

La fonction doit renvoyer un entier inférieur, égal ou supérieur à zéro si le premier argument est considéré comme étant respectivement inférieur, égal ou supérieur au second.
C11dr §7.22.5.2 3

Lorsque les mêmes objects … sont passés plus d’une fois à la fonction de comparaison, les résultats doivent être cohérents entre eux. Autrement dit, pour qsort ils doivent définir un classement total sur le tableau, … le même object doit toujours comparer la même manière avec la clé.
§7.22.5 4

a > b est faux quand a <= b ou si a n’est pas un nombre ou si b n’est pas un nombre. Donc, a > b n’est pas identique à !(a <= b) car ils ont des résultats opposés si l’un d’entre eux est NaN.

Si la fonction de comparaison utilise return (a > b) - (a < b); , le code renverrait 0 si un ou les deux a ou b sont NaN. Le tableau ne sortinge pas comme vous le souhaitez et il perd le total de la commande .

Le long double aspect long double de ce type est important lorsque vous utilisez les fonctions de classification telles que int isnan(real-floating x); ou int isfinite(real-floating x); . Je sais que isfinite( finite_long_double_more_than_DBL_MAX) peut retourner la valeur false. J’ai donc des inquiétudes sur ce qui isnan(some_long_double) pourrait faire quelque chose d’ inattendu.


J’ai essayé le dessous. Il sortinge apparemment comme souhaité.

Sous-question: Est-ce que compare() ci-dessous est suffisant pour sortinger à votre guise? Des simplifications recommandées? Si non – comment réparer? (Pour cette tâche, les valeurs telles que 0.0L et -0.0L conviennent à un sorting quelconque)

 #include  #include  #include  #include  int compare(const void *a, const void *b) { const long double *fa = (const long double *) a; const long double *fb = (const long double *) b; if (*fa > *fb) return 1; if (*fa < *fb) return -1; if (*fa == *fb) { //return -memcmp(fa, fb, sizeof *fa); if -0.0, 0.0 order important. return 0; } // At least one of *fa or *fb is NaN // is *fa a non-NaN? if (!isnan(*fa)) return -1; if (!isnan(*fb)) return 1; // both NaN return 0; // return -memcmp(fa, fb, tbd size); if NaN order important. } int main(void) { long double x[] = { 0.0L / 0.0, 0.0L / 0.0, 0.0, 1.0L / 0.0, -0.0, LDBL_MIN, LDBL_MAX, 42.0, -1.0L / 0.0, 867-5309, -0.0 }; x[0] = -x[0]; printf("unsorted: "); size_t n = sizeof x / sizeof x[0]; for (size_t i = 0; i < n; i++) { printf("%.3Le,", x[i]); } printf("\nsorted: "); qsort(x, n, sizeof x[0], compare); for (size_t i = 0; i < n; i++) { printf("%.3Le,", x[i]); } puts(""); } 

Sortie

 unsorted: nan,-nan,0.000e+00,inf,-0.000e+00,3.362e-4932,1.190e+4932,4.200e+01,-inf,-4.442e+03,-0.000e+00, sorted: -inf,-4.442e+03,-0.000e+00,0.000e+00,-0.000e+00,3.362e-4932,4.200e+01,1.190e+4932,inf,nan,-nan, 

Si je savais que la fonction de comparaison était correcte, je publierais sur Code Review des idées d’amélioration. Pourtant, je ne suis pas assez convaincu que le code fonctionne correctement avec ces satanés NaN.

Ceci est juste une simple réorganisation de vos tests, mais cela clarifie le statut de NaN si vous voulez.

 int compare(const void *a, const void *b) { const long double fa = *(const long double *) a; const long double fb = *(const long double *) b; if (isnan(fa)) { if (isnan(fb)) { return 0; } return 1; } if (isnan(fb)) { return -1; } if (fa > fb) return 1; if (fa < fb) return -1; /* no more comparisons needed */ return 0; } 

Comme les tests pour NaN sont en haut et qu'aucun NaN ne devrait passer, les trois lignes du bas peuvent être remplacées en toute sécurité par votre

 return (a > b) - (a < b); 

Mis à part la discussion sur les différents types de NaN (un peu sonnant comme combien d'anges peuvent danser sur un cœur de processeur), cela devrait être suffisamment stable pour vos besoins, et je ne vois pas de problèmes possibles avec ce code.

Avec Clang, ni -ffast-math ni -fdenormal-fp-math=[ieee|preserve-sign|positive-zero] donne d'autres résultats. -ffast-math n’a pas non plus gcc avec -ffast-math , -funsafe-math-optimizations , et même -ffinite-math-only (ce dernier est probablement dû au fait qu’il n’ya pas d’opérations autres que la comparaison directe avec NaN ).

Juste pour être complet, j'ai testé avec std::numeric_limits::signaling_NaN(); et std::numeric_limits::quiet_NaN(); (à partir de C ++ ) également - encore une fois, aucune différence dans l’ordre de sorting.

Le test NaN

 int isnan(real-floating x); 

La macro isnan détermine si sa valeur d’argument est un NaN. Tout d’abord, un argument représenté dans un format plus large que son type sémantique est converti en son type sémantique. Ensuite, la détermination est basée sur le type de l’argument. 235
235 Pour la macro isnan , le type de détermination importe peu si l’implémentation prend en charge les NaN dans le type d’évaluation mais pas dans le type sémantique.

isnan(some_long_double) fonctionnera comme prévu, sauf sur une plate-forme rare.

int isunordered(real-floating x, real-floating y) agit comme si isnan() s’attend à ce qu’il isnan() compte les deux arguments.

Sur de nombreuses plates-formes, le code pourrait utiliser (a == a) comme test de NaN candidat, car il est évalué à 0 lorsque a est NaN et à 1 sinon. Malheureusement, à moins qu’une implémentation définisse __STDC_IEC_559__ , cela ne fonctionnera pas __STDC_IEC_559__ .


La comparaison
>=, >, <, <= et C11 7.12.14 Macros de comparaison

L'utilisation de >=, >, <, <= lorsqu'au moins un opérande est NaN peut entraîner une exception de virgule flottante "non valide". Un test préalable de NaN est donc prudent, comme l’a répondu @ @ usr2564301.

C propose des macros isgreaterequal(), isgreaterequal(), isless(), islessthna() qui effectuent la comparaison et ne lève pas l’exception de virgule flottante "non valide". C'est une bonne alternative au double , mais les macros utilisent un flottant réel qui peut différer du long double . isgreater(long_double_a, long_double_a) peut être évalué comme double et ne pas fournir le résultat de comparaison souhaité.

Le problème avec les macros de classification est que le type sémantique peut être plus étroit que long double .


Ce qui suit utilise les idées ci-dessus et comme je l'ai lu, la spécification C est bien définie et fonctionnellement correcte pour tous les cas sauf le rare: lorsqu'un long double a NaN mais pas le réel (souvent double ) ne le fait pas.

 #include  // compare 2 long double. All NaN are greater than numbers. int compare(const void *a, const void *b) { const long double *fa = (const long double *) a; const long double *fb = (const long double *) b; if (!isunordered(*fa, *fb)) { return (*fa > *fb) - (*fa < *fb); } if (!isnan(*fa)) { return -1; } return isnan(*fb); // return 0 or 1 } 

Remarque: après avoir lu de nombreux commentaires positifs et appris beaucoup de choses, je publie cette réponse personnelle, comme indiqué dans Puis-je répondre à ma propre question? en plus d'accepter une autre réponse.