Fonction de comparaison d'entiers avec qsort()
Le
ccandide
On 27 juil, 15:23, -ed- <emmanuel.delah@gmail.com> wrote:
> Ce qui compte, ce n'est pas l'historique, mais l'état des lieux tel
> qu'il est affirmé à ce jour, c'est à dire, par exemple, sur mon
> site
Tiens justement, j'avais à coder, en réponse à une question du forum =
C
du Site du Zéro, une fonction callback compar() pour un qsort()
d'entiers. J'ai donc eu l'idée de regarder ce que tu proposais sur ton
site. Voici ton code, cf. http://www.bien-programmer.fr/qsort.htm :
/*=
=*/
/* fonction utilisateur de comparaison fournie a qsort() */
static int compare (void const *a, void const *b)
{
/* definir des pointeurs type's et initialise's
avec les parametres */
int const *pa = a;
int const *pb = b;
/* evaluer et retourner l'etat de l'evaluation (tri croissant) */
return *pa - *pb;
}
/*=
=*/
Il me semble que ce code contient une erreur : *pa - *pb peut
engendrer un dépassement de capacité (integer overflow), ce qui est un
comportement indéterminé.
Voici un exemple d'exécution :
/*=
=*/
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
/* fonction utilisateur de comparaison fournie a qsort() */
static int compare (void const *a, void const *b)
{
/* definir des pointeurs type's et initialise's
avec les parametres */
int const *pa = a;
int const *pb = b;
/* evaluer et retourner l'etat de l'evaluation (tri croissant) */
return *pa - *pb;
}
void afficher(int x, int y)
{
int delta=compare(&x, &y);
printf("%d %c %d", x, delta > 0 ? '>' : delta == 0 ? '=' : '<',
y);
}
int main (void)
{
int x=INT_MAX-1, y=-1;
afficher(x,y);
afficher(x=INT_MAX,y); /* <- Overflow */
return 0;
}
/*=
=*/
et qui affiche chez moi :
2147483646 > -1
2147483647 < -1
> Ce qui compte, ce n'est pas l'historique, mais l'état des lieux tel
> qu'il est affirmé à ce jour, c'est à dire, par exemple, sur mon
> site
Tiens justement, j'avais à coder, en réponse à une question du forum =
C
du Site du Zéro, une fonction callback compar() pour un qsort()
d'entiers. J'ai donc eu l'idée de regarder ce que tu proposais sur ton
site. Voici ton code, cf. http://www.bien-programmer.fr/qsort.htm :
/*=
=*/
/* fonction utilisateur de comparaison fournie a qsort() */
static int compare (void const *a, void const *b)
{
/* definir des pointeurs type's et initialise's
avec les parametres */
int const *pa = a;
int const *pb = b;
/* evaluer et retourner l'etat de l'evaluation (tri croissant) */
return *pa - *pb;
}
/*=
=*/
Il me semble que ce code contient une erreur : *pa - *pb peut
engendrer un dépassement de capacité (integer overflow), ce qui est un
comportement indéterminé.
Voici un exemple d'exécution :
/*=
=*/
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
/* fonction utilisateur de comparaison fournie a qsort() */
static int compare (void const *a, void const *b)
{
/* definir des pointeurs type's et initialise's
avec les parametres */
int const *pa = a;
int const *pb = b;
/* evaluer et retourner l'etat de l'evaluation (tri croissant) */
return *pa - *pb;
}
void afficher(int x, int y)
{
int delta=compare(&x, &y);
printf("%d %c %d", x, delta > 0 ? '>' : delta == 0 ? '=' : '<',
y);
}
int main (void)
{
int x=INT_MAX-1, y=-1;
afficher(x,y);
afficher(x=INT_MAX,y); /* <- Overflow */
return 0;
}
/*=
=*/
et qui affiche chez moi :
2147483646 > -1
2147483647 < -1
Poser une question
| On 27 juil, 15:23, -ed- | > Ce qui compte, ce n'est pas l'historique, mais l'état des lieux tel
| > qu'il est affirmé à ce jour, c'est à dire, par exemple, sur mon
| > site ...
|
| Tiens justement, j'avais à coder, en réponse à une questio n du forum C
| du Site du Zéro, une fonction callback compar() pour un qsort()
| d'entiers. J'ai donc eu l'idée de regarder ce que tu proposais sur t on
| site. Voici ton code, cf. http://www.bien-programmer.fr/qsort.htm :
|
|
| /*======================= ==*/
| /* fonction utilisateur de comparaison fournie a qsort() */
| static int compare (void const *a, void const *b)
| {
| /* definir des pointeurs type's et initialise's
| avec les parametres */
| int const *pa = a;
| int const *pb = b;
|
| /* evaluer et retourner l'etat de l'evaluation (tri croissant) */
| return *pa - *pb;
| }
| /*======================= ==*/
|
| Il me semble que ce code contient une erreur : *pa - *pb peut
| engendrer un dépassement de capacité (integer overflow), ce qui est un
| comportement indéterminé.
Exact.
J'aurais écrit
static int
int_compare(const void* p, const void* q) {
const int a = *(const int*)p;
const int b = *(const int*)q;
if (a < b) return -1;
if (a > b) return 1;
return 0;
}
-- Gaby
OK.
C'est sûr que c'est plus lisible que
return a<b ? -1 : a>b;
mais est-ce aussi efficace (avec les compilos actuels) ?
Antoine
| Le 28/07/2009 17:16Z, Gabriel Dos Reis écrivit :
| > J'aurais écrit
| >
| > static int
| > int_compare(const void* p, const void* q) {
| > const int a = *(const int*)p;
| > const int b = *(const int*)q;
| > if (a < b) return -1;
| > if (a > b) return 1;
| > return 0;
|
|
| C'est sûr que c'est plus lisible que
|
| return a<b ? -1 : a>b;
|
| mais est-ce aussi efficace (avec les compilos actuels) ?
Je comprends que la légende urbaine voudrait que l'efficacité d'u ne
fonction C soit une fonction croissante du numbre de tokens utilisés
pour l'écrire, mais je serai vraiment surpris si un compilateur moderne
tombait dans ce panneau dans ce cas précis :-)
Le compilateur C qui vient avec mon système génère (gcc-4.3. 2)
.file "gdr.c"
.text
.p2align 4,,15
.globl int_compare
.type int_compare, @function
int_compare:
.LFB2:
movl (%rsi), %eax
cmpl %eax, (%rdi)
movl $-1, %edx
jl .L3
setg %al
movzbl %al, %edx
.L3:
movl %edx, %eax
ret
.LFE2:
.size int_compare, .-int_compare
pour ma version, et
.file "al.c"
.text
.p2align 4,,15
.globl int_compare
.type int_compare, @function
int_compare:
.LFB2:
movl (%rsi), %eax
cmpl %eax, (%rdi)
movl $-1, %edx
jl .L3
setg %al
movzbl %al, %edx
.L3:
movl %edx, %eax
ret
.LFE2:
.size int_compare, .-int_compare
pour ta version. Je ne vois pas de différence (et diff non plus).
Donc, je pense que je préfère ma version :-)
-- Gaby