Implementation de qsort

Le
candide
Bonjour !

Plauger implémente qsort en déclarant un tableau local d'une taille de
256 bytes. Ce tableau sert à faire des transpositions (swap) de clés.
Mais comme la taille size des données est inconnue, le code doit, le cas
échéant s'y prendre en plusieurs fois pour terminer le swap, ce qui doit
être assez couteux. Alors je me demandais pourquoi il n'avait pas décidé
d'utiliser malloc pour éviter toutes ses contorsions. Quelque chose dans
la norme l'interdit-t-il ? En plus, il s'agirait d'allouer juste une
fois un buffer dynamique qui permet de faire un swap de façon classique.
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses Page 1 / 8
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Jean-Marc Bourguet
Le #17869531
candide
Plauger



Je suppose dans son bouquin sur la bibliotheque standard? (Ou bien tu vas
voir dans les sources actuelles de Dinkumware?)

implémente qsort en déclarant un tableau local d'une taille de 256
bytes. Ce tableau sert à faire des transpositions (swap) de clés. Mais
comme la taille size des données est inconnue, le code doit, le cas
échéant s'y prendre en plusieurs fois pour terminer le swap, ce qui doit
être assez couteux.



Es-tu sur? A mon avis c'est meilleur pour le cache de travailler comme
cela.

Alors je me demandais pourquoi il n'avait pas décidé d'utiliser malloc
pour éviter toutes ses contorsions.



Aucune idee. Je doute que le cache etait un gros facteur au moment ou il a
concu la fonction -- vraisemblablement bien avant la publication de la
norme.

Est-ce qu'il ne discutte pas la chose dans le texte?

Quelque chose dans la norme l'interdit-t-il ?



Meme si ce n'est pas interdit, eviter de dependances peut etre un bon
argument pour quelqu'un qui vend une bibliotheque dans certains marches.
Et avant l'ere des bibliotheques partagees, l'argument avait une portee
beaucoup plus large.

A+

--
Jean-Marc
FAQ de fclc: http://www.levenez.com/lang/c/faq
Site de usenet-fr: http://www.usenet-fr.news.eu.org
ld
Le #17869921
On 17 nov, 03:00, candide
Bonjour !

Plauger implémente qsort en déclarant un tableau local d'une taille d e
256 bytes. Ce tableau sert à faire des transpositions (swap) de clés.
Mais comme la taille size des données est inconnue, le code doit, le ca s
échéant s'y prendre en plusieurs fois pour terminer le swap, ce qui d oit
être assez couteux. Alors je me demandais pourquoi il n'avait pas déc idé
d'utiliser malloc pour éviter toutes ses contorsions. Quelque chose dan s
la norme l'interdit-t-il ? En plus, il s'agirait d'allouer juste une
fois un buffer dynamique qui permet de faire un swap de façon classique .



qsort n'est pas un algorithme, mais une fonction fournie par la bib
standard. Il est donc difficile de commenter. S'il s'agit de
quicksort, il n'y a pas besoin de tampon pour faire le swap d'element.

a+, ld.
candide
Le #17871791
Jean-Marc Bourguet a écrit :


Je suppose dans son bouquin sur la bibliotheque standard? (



Oui, son livre "The Standard C Library" (1992).

Ou bien tu vas
voir dans les sources actuelles de Dinkumware?)



Ah bon le code-source est disponible ? si tu une URL, ça m'intéresse.


implémente qsort en déclarant un tableau local d'une taille de 256
bytes. Ce tableau sert à faire des transpositions (swap) de clés. Mais
comme la taille size des données est inconnue, le code doit, le cas
échéant s'y prendre en plusieurs fois pour terminer le swap, ce qui doit
être assez couteux.



Es-tu sur? A mon avis c'est meilleur pour le cache de travailler comme
cela.



Je dis assez couteux par rapport à une copie en une seule traite.


Alors je me demandais pourquoi il n'avait pas décidé d'utiliser malloc
pour éviter toutes ses contorsions.



Aucune idee. Je doute que le cache etait un gros facteur au moment ou il a
concu la fonction -- vraisemblablement bien avant la publication de la
norme.



Euh non, son livre suit la norme à la lettre d'ailleurs chaque chapitre
commence par l'extrait correspondant de la norme.


Est-ce qu'il ne discutte pas la chose dans le texte?




Non, il reste dans les généralités (Hoare, description de l'algorithme,
choix du pivot, complexité de l'algorithme).
candide
Le #17871921
ld a écrit :

(...) S'il s'agit de
quicksort, il n'y a pas besoin de tampon pour faire le swap d'element.



Ah bon ? Alors tu fais comment ? je ne vois pas comment tu peux échanger
deux valeurs sans avoir une zone de "transit", un tampon donc, aussi
petit soit-il.

Plauger code un quicksort. J'ai trouvé le code ci-dessous sur le net,
c'est quasiment le même que celui du livre de Plauger. Ce que j'appelle
les "contorsions", c'est les lignes 30 à 36. Tout se passe bien si size
<= 256 mais sinon, il doit s'y prendre en plusieurs fois, faute de place
suffisante, pour faire l'échange.


/* ------------------- ligne 1 -------------------------*/
/* macros */
#define MAX_BUF 256 /* chunk to copy on swap */

static
void qsortErsatz (void *base, size_t n, size_t size,
int(*cmp)(const void *a, const void *b))
{
while (1 < n)
{ /* worth sorting */
size_t i = 0;
size_t j = n - 1;
char *qi = base;
char *qj = qi + size * j;
char *qp = qj;

while (i < j)
{/* partition about pivot */
while (i < j && (*cmp)(qi, qp) <= 0)
++i, qi += size;
while (i < j && (*cmp)(qp, qj) <= 0)
--j, qj -= size;
if (i < j)
{/* swap elements i and j */
char buf[MAX_BUF];
char *q1 = qi;
char *q2 = qj;
size_t m, ms;

for (ms = size; 0 < ms; ms -= m, q1 += m, q2 -= m)
{/* swap as many as possible */
m = ms < sizeof (buf) ? ms : sizeof (buf);
memcpy(buf, q1, m);
memcpy(q1, q2, m);
memcpy(q2, buf, m);
}
++i, qi += size;
--j, qj -= size;
}
}
if (qi != qp)
{/* swap elements i and pivot */
char buf[MAX_BUF];
char *q1 = qi;
char *q2 = qp;
size_t m, ms;

for (ms = size; 0 < ms; ms -= m, q1 += m, q2 -= m)
{/* swap as many as possible */
m = ms < sizeof (buf) ? ms : sizeof (buf);
memcpy(buf, q1, m);
memcpy(q1, q2, m);
memcpy(q2, buf, m);
}
}
j = n - i;
if (j < i)
{/* recurse on smaller partition */
if (1 < j)
qsortErsatz(qi, j, size, cmp);
n = i;
}
else
{/* lower partition is smaller */
if (1 < i)
qsortErsatz(base, i, size, cmp);
base = qi;
n = j;
}
}
}
/* ------------------- ligne 72 -------------------------*/
Jean-Marc Bourguet
Le #17872341
candide
Jean-Marc Bourguet a écrit :

>
> Je suppose dans son bouquin sur la bibliotheque standard? (

Oui, son livre "The Standard C Library" (1992).

> Ou bien tu vas
> voir dans les sources actuelles de Dinkumware?)

Ah bon le code-source est disponible ? si tu une URL, ça m'intéresse.



http://www.dinkumware.com/SourceEdition.aspx

>> implémente qsort en déclarant un tableau local d'une taille de 256
>> bytes. Ce tableau sert à faire des transpositions (swap) de clés. Mais
>> comme la taille size des données est inconnue, le code doit, le cas
>> échéant s'y prendre en plusieurs fois pour terminer le swap, ce qui doit
>> être assez couteux.
>
> Es-tu sur? A mon avis c'est meilleur pour le cache de travailler comme
> cela.

Je dis assez couteux par rapport à une copie en une seule traite.



Swapper demande 3 copies. Directe ou via des trucs comme
a^=b; b^=a; a ^= b;

>> Alors je me demandais pourquoi il n'avait pas décidé d'utiliser malloc
>> pour éviter toutes ses contorsions.
>
> Aucune idee. Je doute que le cache etait un gros facteur au moment ou il a
> concu la fonction -- vraisemblablement bien avant la publication de la
> norme.

Euh non, son livre suit la norme à la lettre d'ailleurs chaque chapitre
commence par l'extrait correspondant de la norme.



Le code precede les deux, meme s'il a du etre revu pour etre totalement
conforme.

Ne pas oublier qu'un des auteurs principaux de la partie bibliotheque,
c'est PJP.

A+

--
Jean-Marc
FAQ de fclc: http://www.levenez.com/lang/c/faq
Site de usenet-fr: http://www.usenet-fr.news.eu.org
Charlie Gordon
Le #17872821
"candide" 4920d029$0$18524$
Bonjour !

Plauger implémente qsort en déclarant un tableau local d'une taille de
256 bytes. Ce tableau sert à faire des transpositions (swap) de clés.
Mais comme la taille size des données est inconnue, le code doit, le cas
échéant s'y prendre en plusieurs fois pour terminer le swap, ce qui doit
être assez couteux. Alors je me demandais pourquoi il n'avait pas décidé
d'utiliser malloc pour éviter toutes ses contorsions. Quelque chose dans
la norme l'interdit-t-il ? En plus, il s'agirait d'allouer juste une
fois un buffer dynamique qui permet de faire un swap de façon classique.



En C99 on pourrait allouer le tableau directement de la bonne taille sur la
pile, mais à l'évidence, cette option n'était pas loisible quand ce bouquin
a été écrit.

La raison me semble très simple : le malloc peut tout-à-fait retourner NULL.
Or qsort doit quand même faire son boulot dans ce cas. Donc le code devrait
prevoir les deux cas : swap avec un tableau de la bonne taille ET swap avec
un tableau trop petit. Le code serait donc encore plus compliqué.

Quitte à faire un cas particulier, je pense qu'il faut le faire pour les
tableaux de pointeurs, et il est alors loisible de changer l'API pour
utiliser une fonction de comparaison qui prend directement les pointeurs en
argument au lieu de leur adresse dans le tableau. On peut alors par exemple
trier un tableau de pointeurs de chaines de caracteres en passant
directement strcmp ou strcoll comme fonction de comparaison.

Dans les faits, les tableaux que l'on trie avec qsort sont souvent des
tableaux de pointeurs sur des structures allouees au fur et a mesure des
besoins, plutôt que des tableaux de structures qu'il faut reallouer en bloc
quand la taille grandit. L'approche tableau de pointeurs est
considerablement plus efficace au prix d'un faible surcoût en memoire.

--
Chqrlie.
candide
Le #17873091
Jean-Marc Bourguet a écrit :

http://www.dinkumware.com/SourceEdition.aspx





Ah OK mais c'est payant (et je suppose pas donné).
Jean-Marc Bourguet
Le #17873081
candide
Jean-Marc Bourguet a écrit :
>
> http://www.dinkumware.com/SourceEdition.aspx

Ah OK mais c'est payant (et je suppose pas donné).



Il y a le prix quelque part. J'ai en tete 3000$ ou approchant, ce qui est
raisonnable pour une entreprise, mais effectivement pas pour satisfaire la
curiosite d'un particulier.

A+

--
Jean-Marc
FAQ de fclc: http://www.levenez.com/lang/c/faq
Site de usenet-fr: http://www.usenet-fr.news.eu.org
candide
Le #17873071
Charlie Gordon a écrit :


La raison me semble très simple : le malloc peut tout-à-fait retourner NULL.
Or qsort doit quand même faire son boulot dans ce cas.



Oui, exact, je n'avais pas pensé à ça (pour un programmeur du dimanche,
malloc ne retourne jamais NULL !)


Dans les faits, les tableaux que l'on trie avec qsort sont souvent des
tableaux de pointeurs sur des structures allouees au fur et a mesure des
besoins, plutôt que des tableaux de structures qu'il faut reallouer en bloc
quand la taille grandit. L'approche tableau de pointeurs est
considerablement plus efficace au prix d'un faible surcoût en memoire.




Donc, si j'ai bien compris, plus efficace car qsort copiera alors des
adresses plutôt que des (éventuellement grosses) structures ?
Charlie Gordon
Le #17873261
"candide" 49218432$0$15993$
Charlie Gordon a écrit :

La raison me semble très simple : le malloc peut tout-à-fait retourner
NULL.
Or qsort doit quand même faire son boulot dans ce cas.



Oui, exact, je n'avais pas pensé à ça (pour un programmeur du dimanche,
malloc ne retourne jamais NULL !)


Dans les faits, les tableaux que l'on trie avec qsort sont souvent des
tableaux de pointeurs sur des structures allouees au fur et a mesure des
besoins, plutôt que des tableaux de structures qu'il faut reallouer en
bloc
quand la taille grandit. L'approche tableau de pointeurs est
considerablement plus efficace au prix d'un faible surcoût en memoire.




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



Tout-à-fait. qsort échange des pointeurs et non les structures elles-mêmes,
le code generé est beaucoup plus simple et donc plus rapide. De même, la
reallocation du tableau en cas de changement de taille se fait sur un
tableau de pointeurs et non sur l'ensemble des données, de plus on peut
sur-allouer ce tableau de pointeurs avec peu de surcoût et donc reallouer
moins souvent. Enfin on peut avoir plusieurs tableaux de pointeurs qui
coexistent pour des tris sur des critères differents.

--
Chqrlie.
Publicité
Poster une réponse
Anonyme