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.
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
candide <candide@free.invalid> writes:
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
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
On 17 nov, 03:00, candide wrote:
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.
On 17 nov, 03:00, candide <cand...@free.invalid> wrote:
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.
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
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).
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).
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
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 */
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 -------------------------*/
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 */
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 -------------------------*/
(...) 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 */
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
candide writes:
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
candide <candide@free.invalid> writes:
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
> > 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
"candide" a écrit dans le message de news: 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" <candide@free.invalid> a écrit dans le message de news:
4920d029$0$18524$426a74cc@news.free.fr...
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.
"candide" a écrit dans le message de news: 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
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 a écrit :
http://www.dinkumware.com/SourceEdition.aspx
Ah OK mais c'est payant (et je suppose pas donné).
Ah OK mais c'est payant (et je suppose pas donné).
Jean-Marc Bourguet
candide writes:
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 <candide@free.invalid> writes:
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
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
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 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 ?
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
"candide" a écrit dans le message de news: 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.
"candide" <candide@free.invalid> a écrit dans le message de news:
49218432$0$15993$426a74cc@news.free.fr...
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.
"candide" a écrit dans le message de news: 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.
