Implementation de qsort

In article <mn.a4c97d8bb66b09d3.79899@wanadoo.fr>,
Pierre Maurette <maurettepierre@wanadoo.fr> wrote:

Bien entendu. Je ne peux l'ignorer, puisque c'est rappelé sur f.c.l.c
tous les deux ou trois jours.
J'ai pris soin d'écrire que ce code était défectueux - en C portable -,
et seulement en renvoi, j'ai signalé qu'il marchera dans "beaucoup de
cas". J'ai rapidement testé par acquit de conscience avec VC, 32bit et
64bit, et gcc 4.3.2, Ubuntu x86-64.
Je me demande quelles précautions oratoires faut-il prendre pour ne pas
provoquer ce genre de réponse. Peut-être écrire soi-même la réponse
dans le message, tant cette réponse est prévisible et était attendue?
Ou alors décider que ce petit truc assez amusant et qui ponctuellement
peut être pratique n'est pas digne d'intéresser quiconque sur f.c.l.c.
et le remettre dans sa culotte ?

Ben dire que c'est non-portable. Et sortir chapitre et verset de la norme
pour expliquer ce qui se passe... j'avoue que je ne l'ai pas ressorti pour
verifier si c'etait undefined behavior ou implementation-defined behavior,
je pencherais pour le second, ce qui veut dire qu'il est effectivement
possible que ca marche de facon previsible sur certaines implementations.

Si c'est bien implementation-defined, d'ailleurs, verifier que ca fonctionne
n'est que la 2e etape (le test), la premiere etant bien sur de lire la
doc de l'implementation pour verifier que ca va fonctionner comme on
pense...

Sur des points comme celui-ci, un peu de flou artistique va forcement
declencher des reactions epidermiques. Suffit de s'etre fait avoir une
fois ou deux a devoir corriger le code d'un zozo qui maitrisait mal son
langage pour avoir des boutons des que quelqu'un parle de comportement
indefini ou defini par l'implementation sans employer de termes techniques
precis...

Charlie Gordon, le 20/11/2008 a écrit :

[...]

Pour éviter cela, il suffit d'utiliser le type unsigned char.
En fait le probleme avec ce "classique" est qu'il ne fonctionne pas si a et b
sont la meme variable. La valeur est alors forcée à zero.
Une variante consiste à utiliser le ou exclusif:
#define SWAP(a, b) ((a)^=(b), (b)^=(a), (a)^=(b))

C'est mieux. Je l'avais oubliée. Mais bien entendu, on force également
à zéro pour une variable unique.

Notons aussi que ni l'un ni l'autre ne fonctionne pour des variables non
entières (float...)

Certes. Enfin, ça pourrait fonctionner en assembleur ou en castant
l'adresse du float en pointeur vers un entier de la taille du float,
sous réserve qu'il en existe.

Enfin il n'est pas prudent d'oublier les parenthèses extérieures dans
l'expansion de cette macro.

Oui. Plus utiles dans ce cas même que les "petites" parenthèses.
Justement, à ce propos, y a-t-il des règles particulères pour
l'écriture de macros qui n'acceptent en argument que des variables
(lvalues évaluables) ?

--
Pierre Maurette

(supersedes <mn.a4dd7d8b7520d89d.79899@wanadoo.fr>)

Charlie Gordon, le 20/11/2008 a écrit :

[...]

Pour éviter cela, il suffit d'utiliser le type unsigned char.
En fait le probleme avec ce "classique" est qu'il ne fonctionne pas si a et
b sont la meme variable. La valeur est alors forcée à zero.
Une variante consiste à utiliser le ou exclusif:
#define SWAP(a, b) ((a)^=(b), (b)^=(a), (a)^=(b))

C'est mieux. Je l'avais oubliée. Mais bien entendu, on force également
à zéro pour une variable unique.

Notons aussi que ni l'un ni l'autre ne fonctionne pour des variables non
entières (float...)

Certes. Enfin, ça pourrait fonctionner en assembleur ou en castant
l'adresse du float en pointeur vers un entier de la taille du float,
sous réserve qu'il en existe.
Ajout:
#define SWAP(f1, f2)
(*(int*)&f1^=*(int*)&f2, *(int*)&f2^=*(int*)&f1,
*(int*)&f1^=*(int*)&f2)

Mouarf...

Enfin il n'est pas prudent d'oublier les parenthèses extérieures dans
l'expansion de cette macro.

Oui. Plus utiles dans ce cas même que les "petites" parenthèses.
Justement, à ce propos, y a-t-il des règles particulères pour
l'écriture de macros qui n'acceptent en argument que des variables
(lvalues évaluables) ?

--
Pierre Maurette

Pierre Maurette a écrit :

Un grand classique, pas exempt de défauts(*):
#define SWAPPE(a, b) (a)+=(b), (b)=(a)-(b), (a)-=(b)

Très joli et astucieux, je ne connaissais pas.

Grand classique ? ça dépend pour qui, peut-être qu'on fait ça en
assembleur mais je n'ai vu ça nulle part dans la littérature classique
du C (K&R, Harbison & Steele, Expert C programming, etc) ce qui ne fait
que me confirmer que la littérature C est mal faite.

(*)Mais qui marchera dans "beaucoup de cas" même en cas d'overflow.

Mais c'est donc sans risque pour échanger des unsigned char ?

candide, le 20/11/2008 a écrit :

Pierre Maurette a écrit :

Un grand classique, pas exempt de défauts(*):
#define SWAPPE(a, b) (a)+=(b), (b)=(a)-(b), (a)-=(b)

Très joli et astucieux, je ne connaissais pas.

Grand classique ? ça dépend pour qui, peut-être qu'on fait ça en
assembleur mais je n'ai vu ça nulle part dans la littérature classique
du C (K&R, Harbison & Steele, Expert C programming, etc) ce qui ne fait
que me confirmer que la littérature C est mal faite.

(*)Mais qui marchera dans "beaucoup de cas" même en cas d'overflow.

Mais c'est donc sans risque pour échanger des unsigned char ?

Oui. C'est intuitivement évident, mais un peu long à verbaliser. La
norme nous garantit que le comportement aux dépassements de l'addition
et la soustraction sur des types entiers unsigned est "en compteur
kilimétrique [mécanique]", genre:
9999 + x donne x - 1
0 - x donne 9999 - x + 1
C'est connu, ça doit se déduire de §6.3.1.3.2, avec la note de bas de
page.
De là on peut montrer facilement que les opérations x + C - C, x - C +
C, C + x - C, etc. (sans simplification, c'est à dire en effectuant
successivement les deux opérations) donneront x. Bref, c'est de
l'arithmétique modulo TYPE_MAX. A partir de là c'est trivial.

Pour swapper deux variables de même type, il suffit de swapper leurs
représentations physiques, ce qu'on peut effectuer par le cast en type
unsigned. Soit deux variables d'un type quelconque et 'ent' le type
entier non signé de même taille. Ceci à mon avis fonctionnera toujours:
#define SWAP(x1, x2)
(*(ent*)&x1 += *(ent*)&x2,
*(ent*)&x2 = *(ent*)&x1 - *(ent*)&x2,
*(ent*)&x1 -= *(ent*)&x2)

Mais l'opérateur bitwise ^ (OU exclusif) que signalait Charlie Gordon
est plus "logique", puisqu'il s'intéresse naturellement à la
représentation en mémoire de la donnée:
#define SWAP(x1, x2)
(*(ent*)&x1^=*(ent*)&x2, *(ent*)&x2^=*(ent*)&x1,
*(ent*)&x1^=*(ent*)&x2)

Une fois de plus on constate que ce genre d'opération est bien plus
compliquée et génératrice d'erreurs en C qu'en assembleur. Du fait
qu'en C les données sont typées et les opérateurs ne le sont pas, alors
que dans la machine sous-jacente, c'est (sur les archis que je connais)
le contraire: données non typées, instructions typées s'il le faut.
Remarquons que le représentation en complément à 2 permet de ne pas
spécialiser des instructions comme l'addition, la incrémentation, etc.


Notons enfin que la notion de "sans variable intermédiaire" ne signifie
pas grand chose. Un registre est-il une "variable intermédiaire" ?
En x86, l'addition et le OU exclusif ne se font qu'entre un registre et
une mémoire. Donc...
En revanche, en codant:

int tempo; // ou 'register int tempo;', mais à qoui bon...
tempo = a;
a = b;
b = tempo;

le compilateur fera "au mieux", il pourra créer tempo dans un registre,
mais également () sur la pile:
push a
mov reg, b
mov a, reg
pop b

ou pourquoi pas:
push a
push b
pop a
pop b

En x86, "pensera-t-il" à xchg, qui swappe directement, mais demande
quand même le passage par un registre ? Pas spécialement économique,
d'ailleurs, mais atomique (lock-é) automatiquement.

--
Pierre Maurette

On 17 nov, 15:48, candide <cand...@free.invalid> wrote:

Donc, si j'ai bien compris, plus efficace car qsort copiera alors des
adresses plutôt que des  (éventuellement grosses) structures ?

C'est un principe général. Organiser ses données pour que les
manipulations concernent des pointeurs et non des blocs de données
importants (disons > 10 x la taille d'un pointeur[1]) fait partie du
B.A. BA de la programmation efficace...

La norme n'a pas imposé ce principe, et donc propose de passer la
taille de l'élément. C'est probablement un bon compromis, car sortir
un tableau de pointeur pour trier des entiers, c'est pas non plus très
efficace... Par contre dès qu'on a des structures un peu étoffées, je
recommande le tableau de pointeurs...

------------------
[1] A la place de Plaugher, plutôt qu'un 256 en dur, j'aurais mis (64
* sizeof (void *)) pour exprimer cette intention et la traduire de
façon portable...

On 20 nov, 16:21, candide <cand...@free.invalid> wrote:

ld a écrit :

Ton nom ld me disait quelque chose, ah! je viens de réaliser que tu es
Laurent Deniau.

yep.

> je n'appelle pas une variable, une zone tampon.

> static inline void
> swap(char *restrict a, char *restrict b, size_t s)
> {
>   char t, *e = a+s;

>   while (a < e) t=*a, *a++=b, *b++=t;
> }

OK, pour moi, tu utilises un tampon ... d'un caractère.

Dans ce cas ton programme est plein de tampons ;-)

Au passage, je
ne connais pas vraiment inline (ni restrict) car je me cantonne à C90.

tu peux les oublier (les enlever), un bon compilateur c89 devrait
generer le meme code.

Ta façon de procéder n'est-elle pas très lente (sans inline donc)?

c'est la seule en l'absence de connaissance de l'alignement des
donnees. Il est possible pour des gros elements mal alignes (tres rare
en principe) de commencer avec des char* jusqu'au prochain alignement
d'un long* (< sizeof(long)), de continuer avec des long* et enfin de
finir avec des char* pour le dernier mot (< sizeof(long)). Sinon comme
dans la glibc, d'utiliser un peu de magie de compilateur.

Le plus simple reste tout de meme de faire ce que j'avais dit, c'est a
dire specialiser l'algo pour les trois cas: compatible long*, int* ou
char* comme ci-dessus (toujours ok).

Est-il "académique" d'implémenter qsort sans tampon (avec ta méthod e) ?
(j'aime utiliser les procédés éprouvés, ça m'économise les ne urones ;) )

en quoi c'est plus ou moins academique que le tampon? L'utilisation
d'un tampon pose des problemes que le swap n'a pas. Si c'est aussi
efficace (a ±10%) je choisi toujours le plus simple.

> Le quicksort que tu as montre n'est pas ce qui se fait de mieux, de
> loin.

Qu'est-ce qui du point de vue du codage C ne te parait pas convenable
dans l'implémentation de Plauger (je ne parle pas de l'algorithme, choi x
du pivot et toutes les optimisations de nature algorithmique qu'on
pourrait ajouter) ?

google "quicksort is optimal sedgwick" et tu verras un code beaucoup
plus lisible (et qui peut l'etre encore plus). sedgwick a fait sa
these sur le quicksort et ne cesse depuis d'essaye de l'ameliorer.

pour voir une implementation qui fonctionne (avec les ameliorations de
rigueur), tu peux regarder la fin du fichier

http://cos.cvs.sourceforge.net/viewvc/cos/CosStd/src/Array.c?revision=1.1 5&view=markup

(le reste du fichier n'as pas d'interet sur ce sujet et il bouge
encore beaucoup.)

les resultats sont meilleurs que ceux de la glibc (qui en plus a un
bug au passage) et le code est beaucoup plus simple et court (la glibc
utilise un merge-sort et un quicksort seulement si elle n'a pas assez
de memoire pour le merge-sort).

a+, ld.

ld a écrit :

c'est la seule en l'absence de connaissance de l'alignement des
donnees. Il est possible pour des gros elements mal alignes (tres rare
en principe) de commencer avec des char* jusqu'au prochain alignement
d'un long* (< sizeof(long)), de continuer avec des long* et enfin de
finir avec des char* pour le dernier mot (< sizeof(long)).

Rien compris.

Le plus simple reste tout de meme de faire ce que j'avais dit, c'est a
dire specialiser l'algo pour les trois cas: compatible long*, int* ou
char* comme ci-dessus (toujours ok).

Je crois que je vais me contenter de char*, le reste m'a l'air trop
compliqué pour moi.

en quoi c'est plus ou moins academique que le tampon? L'utilisation
d'un tampon pose des problemes que le swap n'a pas.

Je comprends pas vraiment les problèmes que poserait un tampon.



Sinon, je viens de regarder le source du qsort du compilateur tigcc
(calculatrice TI89), il utilise ta méthode, voici le code :


/* qsort.h */
#include <stdlib.h>

// Do not use register a5; callback function might need it.
register long __tbl asm ("a5");

__ATTR_LIB_C__ void qsort(void *list, short num_items, short size,
compare_t cmp_func)
{
unsigned short gap,byte_gap,i,j;
char *p,*a,*b,temp;
for (gap=((unsigned short)num_items)>>1; gap>0; gap>>=1) // Yes,
this is not a quicksort,
{ // but
works fast enough...
byte_gap=gap*(unsigned short)size;
for(i=byte_gap; i<((unsigned short)num_items)*(unsigned
short)size; i+=size)
for(p=(char*)list+i-byte_gap; p>=(char*)list; p-= byte_gap)
{
a=p; b=p+byte_gap;
if(cmp_func(a,b)<=0) break;
for(j=size;j;j--)
temp=*a, *a++=*b, *b++=temp;
}
}
}

google "quicksort is optimal sedgwick" et tu verras un code beaucoup
plus lisible (et qui peut l'etre encore plus). sedgwick a fait sa
these sur le quicksort et ne cesse depuis d'essaye de l'ameliorer.

J'ai récupéré QuicksortIsOptimal.pdf mais il n'y a pas de code C d'un
quicksort _générique_ (il n'y a d'ailleurs pas de raison que le code C
intéresse spécialement Sedgewick même si dans son livre "Algorithms in
C, Parts 1-4", il implémente de nombreuses variantes du quicksort).

http://cos.cvs.sourceforge.net/viewvc/cos/CosStd/src/Array.c?revision=1.15&view=markup

BEAUCOUP trop compliqué pour moi, d'ailleurs je ne souhaite pas
atteindre ce degré de maitrise du C.

bug au passage) et le code est beaucoup plus simple et court (la glibc
utilise un merge-sort et un quicksort seulement si elle n'a pas assez
de memoire pour le merge-sort).

Alors ça, je trouve que c'est étonnant, je pensais que le quicksort
était dans la pratique universellement répandu. Peux-tu nous dire en
deux mots comment (malloc ?) la glibc alloue la mémoire nécessaire pour
faire les copies de fusion du merge sort ?

Pierre Maurette a écrit :

Un grand classique, pas exempt de défauts(*):
#define SWAPPE(a, b) (a)+=(b), (b)=(a)-(b), (a)-=(b)

On le trouve ici :

http://graphics.stanford.edu/~seander/bithacks.html#SwappingValuesSubAdd

>
Pour swapper deux variables de même type, il suffit de swapper leurs
représentations physiques, ce qu'on peut effectuer par le cast en type
unsigned. Soit deux variables d'un type quelconque et 'ent' le type
entier non signé de même taille.

Pas compris ce qu'est ent. Si le type "quelconque" est, au hasard,

struct toto
{
int a;
char b;
void *c;
double z[24];
};

c'est quoi "le type entier non signé de même taille" ?