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 ?
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 ?
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 ?
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 .
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 .
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 .
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?
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?
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?
(...) S'il s'agit de
quicksort, il n'y a pas besoin de tampon pour faire le swap d'element.
(...) S'il s'agit de
quicksort, il n'y a pas besoin de tampon pour faire le swap d'element.
(...) S'il s'agit de
quicksort, il n'y a pas besoin de tampon pour faire le swap d'element.
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.
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.
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.
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.
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.
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.
http://www.dinkumware.com/SourceEdition.aspx
http://www.dinkumware.com/SourceEdition.aspx
http://www.dinkumware.com/SourceEdition.aspx
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é).
Jean-Marc Bourguet a écrit :
>
> http://www.dinkumware.com/SourceEdition.aspx
Ah OK mais c'est payant (et je suppose pas donné).
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.
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.
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.
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.
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.
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.
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 ?
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 ?