Retour de la fonction bsearch

candide

02/10/2008 à 23:58

Charlie Gordon a écrit :

elle n'est pas récursive mais ça doit sans doute être plus efficace.

J'ai peur que cette dernière remarque soit à prendre au premier degré...
Faut-il que les étudiants soient bien intoxiqués de langages fonctionnels
pour imaginer systématiquement des solutions recursives aux problèmes les
plus simples ?

J'ai cru que la solution récursive serait très lisible mais pas tant que
ça. Je me risque à proposer un code :

void *dicho(const void *key, const void *base, size_t nmemb, size_t
size, int (*compar) (const void *, const void *))
{
if (nmemb == 0)
return NULL;
else if (nmemb == 1)
return compar(key, base) == 0 ? (void *) base : NULL;
else
{
size_t m = (nmemb - 1) / 2;
const char *p = base, *mil = p + m * size;
int v = compar(key, mil);

if (v > 0)
return dicho(key, mil + size, nmemb - m - 1, size, compar);
else if (v < 0)
return dicho(key, p, m, size, compar);
else
return (void *) mil;
}
}

candide

03/10/2008 à 00:12

Charlie Gordon a écrit :

Primo, la recherche dichotomique dans un tableau en mémoire n'est pas une
plaie à coder, tout au plus un rapide échauffement des petits doigts pour le
petit déjeuner.

Parles-en à Plauger, voilà ce qu'il en dit dans son livre sur la
bibliothèque standard (page 353) :

Function bsearch : (...). The logic is simple but easy to get wrong.

C'est exactement mon avis et c'est aussi pour ça que je trouve que c'est
une plaie à coder : un bsearch c'est une mécanique de précision.

Néanmoins, je trouve le code de Plauger assez compliqué .

Charlie Gordon

03/10/2008 à 09:02

"candide" a écrit dans le message de news:
48e543f5$0$16902$

Charlie Gordon a écrit :

elle n'est pas récursive mais ça doit sans doute être plus efficace.

J'ai peur que cette dernière remarque soit à prendre au premier degré...
Faut-il que les étudiants soient bien intoxiqués de langages fonctionnels
pour imaginer systématiquement des solutions recursives aux problèmes les
plus simples ?

J'ai cru que la solution récursive serait très lisible mais pas tant que
ça. Je me risque à proposer un code :

void *dicho(const void *key, const void *base, size_t nmemb, size_t size,
int (*compar) (const void *, const void *))
{
if (nmemb == 0)
return NULL;
else if (nmemb == 1)
return compar(key, base) == 0 ? (void *) base : NULL;
else
{
size_t m = (nmemb - 1) / 2;
const char *p = base, *mil = p + m * size;
int v = compar(key, mil);

if (v > 0)
return dicho(key, mil + size, nmemb - m - 1, size, compar);
else if (v < 0)
return dicho(key, p, m, size, compar);
else
return (void *) mil;
}
}

Ton code me semble fonctionner correctement, mais il peut être
simplifié pour plus de lisibilité sans pénalité notable sur la
performance (si on suppose que la récursion terminale est simplifiée
par le compilateur ;-).

void *dicho(const void *key, const void *base, size_t nmemb,
size_t size, int (*compar)(const void *, const void *))
{
if (nmemb == 0) {
return NULL;
} else {
size_t m = nmemb / 2;
const char *p = base, *mil = p + m * size;
int v = (*compar)(key, mil);

if (v < 0)
return dicho(key, mil + size, nmemb - m - 1, size, compar);
else if (v < 0)
return dicho(key, p, m, size, compar);
else
return (void *)mil;
}
}

Il n'est en effet pas nécessaire de tester nmemb == 1 dans le cas où on
prend le milieu par une simple division par 2 qui arrondit vers 0. On
peut facilement vérifier ce qui se passe pour les valeurs de nmemb
jusqu'à 2 et raisonner par recurrence pour se convaincre que
l'algorithme simplifié fonctionne.

La partition du tableau que tu proposes (m = (nmemb - 1) / 2) peut
sembler plus équilibrée vu qu'on récurse sur un peu moins que la moitié
du tableau, le pivot étant exclu. Dans les faits, cette formule donne
exactement la même partition si nmemb est impair et décale le pivot
d'une position vers la gauche si nmemb est pair, avec des moitiés de
mêmes tailles, la plus petite étant à gauche au lieu d'être à droite.

Une petite remarque concernant le pointeur de fonction : j'utilise la
syntaxe (*compar)(x, y) pour qu'il soit bien visible que compar n'est
pas le nom d'une fonction, mais bien un pointeur vers une fonction. On
peut parfaitement supprimer les parenthèses et l'étoile, de même qu'on
en rajouter dans tout appel de fonction en C : free(p), (free)(p),
(*free)(p), voire (***free)(((p))) sont des formes équivalentes. En
fait il y a bien un cas tordu où le code généré peut différer, et c'est
d'ailleurs une raison de plus d'utiliser (*compar) dans la fonction
ci-dessus.

--
Chqrlie.

"candide" <candide@free.invalid> a écrit dans le message de news:
48e543f5$0$16902$426a74cc@news.free.fr...

Charlie Gordon a écrit :

elle n'est pas récursive mais ça doit sans doute être plus efficace.

J'ai peur que cette dernière remarque soit à prendre au premier degré...
Faut-il que les étudiants soient bien intoxiqués de langages fonctionnels
pour imaginer systématiquement des solutions recursives aux problèmes les
plus simples ?

J'ai cru que la solution récursive serait très lisible mais pas tant que
ça. Je me risque à proposer un code :

void *dicho(const void *key, const void *base, size_t nmemb, size_t size,
int (*compar) (const void *, const void *))
{
if (nmemb == 0)
return NULL;
else if (nmemb == 1)
return compar(key, base) == 0 ? (void *) base : NULL;
else
{
size_t m = (nmemb - 1) / 2;
const char *p = base, *mil = p + m * size;
int v = compar(key, mil);

if (v > 0)
return dicho(key, mil + size, nmemb - m - 1, size, compar);
else if (v < 0)
return dicho(key, p, m, size, compar);
else
return (void *) mil;
}
}

Ton code me semble fonctionner correctement, mais il peut être
simplifié pour plus de lisibilité sans pénalité notable sur la
performance (si on suppose que la récursion terminale est simplifiée
par le compilateur ;-).

void *dicho(const void *key, const void *base, size_t nmemb,
size_t size, int (*compar)(const void *, const void *))
{
if (nmemb == 0) {
return NULL;
} else {
size_t m = nmemb / 2;
const char *p = base, *mil = p + m * size;
int v = (*compar)(key, mil);

if (v < 0)
return dicho(key, mil + size, nmemb - m - 1, size, compar);
else if (v < 0)
return dicho(key, p, m, size, compar);
else
return (void *)mil;
}
}

Il n'est en effet pas nécessaire de tester nmemb == 1 dans le cas où on
prend le milieu par une simple division par 2 qui arrondit vers 0. On
peut facilement vérifier ce qui se passe pour les valeurs de nmemb
jusqu'à 2 et raisonner par recurrence pour se convaincre que
l'algorithme simplifié fonctionne.

La partition du tableau que tu proposes (m = (nmemb - 1) / 2) peut
sembler plus équilibrée vu qu'on récurse sur un peu moins que la moitié
du tableau, le pivot étant exclu. Dans les faits, cette formule donne
exactement la même partition si nmemb est impair et décale le pivot
d'une position vers la gauche si nmemb est pair, avec des moitiés de
mêmes tailles, la plus petite étant à gauche au lieu d'être à droite.

Une petite remarque concernant le pointeur de fonction : j'utilise la
syntaxe (*compar)(x, y) pour qu'il soit bien visible que compar n'est
pas le nom d'une fonction, mais bien un pointeur vers une fonction. On
peut parfaitement supprimer les parenthèses et l'étoile, de même qu'on
en rajouter dans tout appel de fonction en C : free(p), (free)(p),
(*free)(p), voire (***free)(((p))) sont des formes équivalentes. En
fait il y a bien un cas tordu où le code généré peut différer, et c'est
d'ailleurs une raison de plus d'utiliser (*compar) dans la fonction
ci-dessus.

--
Chqrlie.

Vous avez filtré cet utilisateur ! Consultez son message

"candide" a écrit dans le message de news:
48e543f5$0$16902$

Charlie Gordon a écrit :

elle n'est pas récursive mais ça doit sans doute être plus efficace.

J'ai peur que cette dernière remarque soit à prendre au premier degré...
Faut-il que les étudiants soient bien intoxiqués de langages fonctionnels
pour imaginer systématiquement des solutions recursives aux problèmes les
plus simples ?

J'ai cru que la solution récursive serait très lisible mais pas tant que
ça. Je me risque à proposer un code :

void *dicho(const void *key, const void *base, size_t nmemb, size_t size,
int (*compar) (const void *, const void *))
{
if (nmemb == 0)
return NULL;
else if (nmemb == 1)
return compar(key, base) == 0 ? (void *) base : NULL;
else
{
size_t m = (nmemb - 1) / 2;
const char *p = base, *mil = p + m * size;
int v = compar(key, mil);

if (v > 0)
return dicho(key, mil + size, nmemb - m - 1, size, compar);
else if (v < 0)
return dicho(key, p, m, size, compar);
else
return (void *) mil;
}
}

Ton code me semble fonctionner correctement, mais il peut être
simplifié pour plus de lisibilité sans pénalité notable sur la
performance (si on suppose que la récursion terminale est simplifiée
par le compilateur ;-).

void *dicho(const void *key, const void *base, size_t nmemb,
size_t size, int (*compar)(const void *, const void *))
{
if (nmemb == 0) {
return NULL;
} else {
size_t m = nmemb / 2;
const char *p = base, *mil = p + m * size;
int v = (*compar)(key, mil);

if (v < 0)
return dicho(key, mil + size, nmemb - m - 1, size, compar);
else if (v < 0)
return dicho(key, p, m, size, compar);
else
return (void *)mil;
}
}

Il n'est en effet pas nécessaire de tester nmemb == 1 dans le cas où on
prend le milieu par une simple division par 2 qui arrondit vers 0. On
peut facilement vérifier ce qui se passe pour les valeurs de nmemb
jusqu'à 2 et raisonner par recurrence pour se convaincre que
l'algorithme simplifié fonctionne.

La partition du tableau que tu proposes (m = (nmemb - 1) / 2) peut
sembler plus équilibrée vu qu'on récurse sur un peu moins que la moitié
du tableau, le pivot étant exclu. Dans les faits, cette formule donne
exactement la même partition si nmemb est impair et décale le pivot
d'une position vers la gauche si nmemb est pair, avec des moitiés de
mêmes tailles, la plus petite étant à gauche au lieu d'être à droite.

Une petite remarque concernant le pointeur de fonction : j'utilise la
syntaxe (*compar)(x, y) pour qu'il soit bien visible que compar n'est
pas le nom d'une fonction, mais bien un pointeur vers une fonction. On
peut parfaitement supprimer les parenthèses et l'étoile, de même qu'on
en rajouter dans tout appel de fonction en C : free(p), (free)(p),
(*free)(p), voire (***free)(((p))) sont des formes équivalentes. En
fait il y a bien un cas tordu où le code généré peut différer, et c'est
d'ailleurs une raison de plus d'utiliser (*compar) dans la fonction
ci-dessus.

--
Chqrlie.

Charlie Gordon

03/10/2008 à 09:48

"candide" a écrit dans le message de news:
48e5475f$0$26687$

Charlie Gordon a écrit :

Primo, la recherche dichotomique dans un tableau en mémoire n'est pas une
plaie à coder, tout au plus un rapide échauffement des petits doigts pour
le petit déjeuner.

Parles-en à Plauger, voilà ce qu'il en dit dans son livre sur la
bibliothèque standard (page 353) :

Function bsearch : (...). The logic is simple but easy to get wrong.

Je n'avais pas regardé "The Standard C Library" de Plauger, mais
j'avais bien le même point de vue :

"Il est encore facile de faire des erreurs d'implementation quand
on code bsearch pour le petit dej"

C'est exactement mon avis et c'est aussi pour ça que je trouve que c'est
une plaie à coder : un bsearch c'est une mécanique de précision.

C'est une mécanique de précision relativement simple, où s'applique
parfaitement l'adage de Saint-Exupéry : "La perfection est atteinte,
non pas lorsqu'il n'y a plus rien à ajouter, mais lorsqu'il n'y a plus
rien à retirer."

Néanmoins, je trouve le code de Plauger assez compliqué :

/* bsearch function */
#include <stdlib.h>

void *(bsearch)(const void *key, const void *base,
size_t nelem, size_t size, _Cmpfun *cmp)
{ /* search sorted table by binary chop */
const char *p = base;
size_t n;

for (p = base, n = nelem; 0 < n; )
{ /* check midpoint of whatever is left */
const size_t pivot = n >> 1;
const char *const q = p + size * pivot;
const int val = (*cmp)(key, q);

if (val < 0)
n = pivot; /* search below pivot */
else if (val == 0)
return ((void *)q); /* found */
else
{ /* search above pivot */
p = q + size;
n -= pivot + 1;
}
}
return (NULL); /* no match */
}

Moi aussi. Je le trouve peu élégant, surtout à cause des lourdeurs
inutiles comme les parenthèses dans ``return (NULL);'' ``return ((void
*)q);'', le const dans ``const size_t pivot'' et pire encore : ``const
char *const q''

Qualifier les variables locales avec const est sans intérêt dans un
code d'une page, et mettre const avant le type est peu lisible,
d'autant qu'on doitle mettre après l'étoile pour les pointeurs.

La boucle for est particulièrement lourdingue : l'affectation de p est
redondante avec la définition deux lignes plus haut, celle de n aurait
aussi dû se faire dans la définition, enfin l'ordre des arguments de <
est une ineptie : ``0 < n''. Je n'aime pas non plus les accolades
indentées ni les commentaires cadrés à droite.

--
Chqrlie.

"candide" <candide@free.invalid> a écrit dans le message de news:
48e5475f$0$26687$426a34cc@news.free.fr...

Charlie Gordon a écrit :

Primo, la recherche dichotomique dans un tableau en mémoire n'est pas une
plaie à coder, tout au plus un rapide échauffement des petits doigts pour
le petit déjeuner.

Parles-en à Plauger, voilà ce qu'il en dit dans son livre sur la
bibliothèque standard (page 353) :

Function bsearch : (...). The logic is simple but easy to get wrong.

Je n'avais pas regardé "The Standard C Library" de Plauger, mais
j'avais bien le même point de vue :

"Il est encore facile de faire des erreurs d'implementation quand
on code bsearch pour le petit dej"

C'est exactement mon avis et c'est aussi pour ça que je trouve que c'est
une plaie à coder : un bsearch c'est une mécanique de précision.

C'est une mécanique de précision relativement simple, où s'applique
parfaitement l'adage de Saint-Exupéry : "La perfection est atteinte,
non pas lorsqu'il n'y a plus rien à ajouter, mais lorsqu'il n'y a plus
rien à retirer."

Néanmoins, je trouve le code de Plauger assez compliqué :

/* bsearch function */
#include <stdlib.h>

void *(bsearch)(const void *key, const void *base,
size_t nelem, size_t size, _Cmpfun *cmp)
{ /* search sorted table by binary chop */
const char *p = base;
size_t n;

for (p = base, n = nelem; 0 < n; )
{ /* check midpoint of whatever is left */
const size_t pivot = n >> 1;
const char *const q = p + size * pivot;
const int val = (*cmp)(key, q);

if (val < 0)
n = pivot; /* search below pivot */
else if (val == 0)
return ((void *)q); /* found */
else
{ /* search above pivot */
p = q + size;
n -= pivot + 1;
}
}
return (NULL); /* no match */
}

Moi aussi. Je le trouve peu élégant, surtout à cause des lourdeurs
inutiles comme les parenthèses dans ``return (NULL);'' ``return ((void
*)q);'', le const dans ``const size_t pivot'' et pire encore : ``const
char *const q''

Qualifier les variables locales avec const est sans intérêt dans un
code d'une page, et mettre const avant le type est peu lisible,
d'autant qu'on doitle mettre après l'étoile pour les pointeurs.

La boucle for est particulièrement lourdingue : l'affectation de p est
redondante avec la définition deux lignes plus haut, celle de n aurait
aussi dû se faire dans la définition, enfin l'ordre des arguments de <
est une ineptie : ``0 < n''. Je n'aime pas non plus les accolades
indentées ni les commentaires cadrés à droite.

--
Chqrlie.

Vous avez filtré cet utilisateur ! Consultez son message

"candide" a écrit dans le message de news:
48e5475f$0$26687$

Charlie Gordon a écrit :

Primo, la recherche dichotomique dans un tableau en mémoire n'est pas une
plaie à coder, tout au plus un rapide échauffement des petits doigts pour
le petit déjeuner.

Parles-en à Plauger, voilà ce qu'il en dit dans son livre sur la
bibliothèque standard (page 353) :

Function bsearch : (...). The logic is simple but easy to get wrong.

Je n'avais pas regardé "The Standard C Library" de Plauger, mais
j'avais bien le même point de vue :

"Il est encore facile de faire des erreurs d'implementation quand
on code bsearch pour le petit dej"

C'est exactement mon avis et c'est aussi pour ça que je trouve que c'est
une plaie à coder : un bsearch c'est une mécanique de précision.

C'est une mécanique de précision relativement simple, où s'applique
parfaitement l'adage de Saint-Exupéry : "La perfection est atteinte,
non pas lorsqu'il n'y a plus rien à ajouter, mais lorsqu'il n'y a plus
rien à retirer."

Néanmoins, je trouve le code de Plauger assez compliqué :

/* bsearch function */
#include <stdlib.h>

void *(bsearch)(const void *key, const void *base,
size_t nelem, size_t size, _Cmpfun *cmp)
{ /* search sorted table by binary chop */
const char *p = base;
size_t n;

for (p = base, n = nelem; 0 < n; )
{ /* check midpoint of whatever is left */
const size_t pivot = n >> 1;
const char *const q = p + size * pivot;
const int val = (*cmp)(key, q);

if (val < 0)
n = pivot; /* search below pivot */
else if (val == 0)
return ((void *)q); /* found */
else
{ /* search above pivot */
p = q + size;
n -= pivot + 1;
}
}
return (NULL); /* no match */
}

Moi aussi. Je le trouve peu élégant, surtout à cause des lourdeurs
inutiles comme les parenthèses dans ``return (NULL);'' ``return ((void
*)q);'', le const dans ``const size_t pivot'' et pire encore : ``const
char *const q''

Qualifier les variables locales avec const est sans intérêt dans un
code d'une page, et mettre const avant le type est peu lisible,
d'autant qu'on doitle mettre après l'étoile pour les pointeurs.

La boucle for est particulièrement lourdingue : l'affectation de p est
redondante avec la définition deux lignes plus haut, celle de n aurait
aussi dû se faire dans la définition, enfin l'ordre des arguments de <
est une ineptie : ``0 < n''. Je n'aime pas non plus les accolades
indentées ni les commentaires cadrés à droite.

--
Chqrlie.

Jean-Marc Bourguet

03/10/2008 à 10:23

"Charlie Gordon" writes:

Ah bon ? Peux-tu être plus explicite ?

Non. Il y a des jours ou il vaudrait mieux ne rien poster :-(

> (Et je ne vois pas l'utilite du +1 dans a = m + 1).

Cela accélère la convergence : la clé est > au pivot donc l'element cherché
est forcément strictement au delà du pivot.

Consequence de la confusion ci-dessus.

>> On peut dans ce cas améliorer légèrement l'efficacité de la recherche et
>> garantir de trouver le premier match en cas de doublons en remplacant les
>> deux tests sur cmp par un seul (laissé au lecteur à titre d'exercice ;-).
>
> Rien n'empeche de faire cela ici aussi, il suffit de tester l'egalite
> avant
> de retourner une valeur. C'est un gain meme si la valeur se trouve
> toujours dans le tableau.

Non, ce n'est pas loisible : dans le cas général on a plus de comparaisons
avec *key != *p, donc il est préférable de tester ces cas en premier.

Autre source de confusion.

A+

--
Jean-Marc
FAQ de fclc: http://www.isty-info.uvsq.fr/~rumeau/fclc
Site de usenet-fr: http://www.usenet-fr.news.eu.org

candide

03/10/2008 à 14:44

Charlie Gordon a écrit :

Il n'est en effet pas nécessaire de tester nmemb == 1

Oui, c'est ce que je souhaitais faire, merci de ton amélioration.

Une petite remarque concernant le pointeur de fonction : j'utilise la
syntaxe (*compar)(x, y) pour qu'il soit bien visible que compar n'est
pas le nom d'une fonction,

Et en effet c'est une bonne raison. D'ailleurs Plauger utilise cette
notation.

C'est l'occasion pour moi de regarder un peu ce que dit la littérature
concernant l'utilisation dans le corps de définition d'une fonction d'un
paramètre de type pointeur de fonction.

*) A tout seigneur tout honneur, commençons par la norme. Comme
d'habitude, les explications sont plutôt données de manière relativement
didactique, oui, je dis bien "didactique", car il suffit d'examiner
6.9.1 p14 example 2 pour s'en convaincre même s'ils auraient pu un peu
améliorer la présentation
[au passage, je trouve juste un peu curieux que dans les points de
sémantique de 6.9.1 figure un _exemple_, c'est un peu comme si dans le
Code civil, un article de loi se référait à tel jugement du tribunal de
Becon-les-Bruyères]

*) Passons à K&R, lui qui m'a fait tant souffrir. Seul bon point pour
lui, on sait facilement où regarder pour trouver l'information : c'est
écrit dans la table des matières (pas de quoi pavoiser pour autant,
c'est quand même la moindre des choses). Le § en question, le §5.11,
est un des pires paragraphes de tout le livre d'un point de vue de la
qualité didactique, un sommet dans l'art de l'absconsisation. Tellement
abscons d'ailleurs que les auteurs se sont complètement vautrés dans
leur code, cf. l'errata de l'ouvrage. Naturellement la question de
savoir si on peut appeler notre pointeur par f(truc) au lieu de
(*f)(truc) n'est pas du tout évoqué, les cuisines c'est l'étage en dessous.

*) Autre monstre sacré, le Harbison & Steele. En fait une réputation
mais rien que cela. Le livre est encore pire que le K&R. Moi il ne me
sert que de contre-modèle : si je dois écrire un document didactique, je
me réfère à H&S pour savoir comment ne pas l'écrire. Le titre du livre
de ces messieurs ? Rép. : "C a Reference Manual". Vous avez dit
"référence" ? Vous cherchez des infos sur les pointeurs de fonctions
donc vous commencez par regarder dans la table des matières :

-- il y a un chapitre "Type" avec un § sur les pointeurs mais on n'y
trouve quasiment aucune information sur les pointeurs de fonctions ;

-- il y a un chapitre "Functions" (le dernier chapitre, incroyable !!
c'est exactement le contraire de ce qu'il fallait faire : le chapitre UN
du C c'est les fonctions ...) et dans aucun paragraphe (si je me fie à
leur titre) il n'est question de pointeur vers des fonctions.

Peut-être aurais-je plus de chance avec l'index ? Bon, déjà, ces auteurs
ne savent pas faire un index, il est super lacunaire tout en étant
surabondant. Alors je regarde à "functions" qui commence par me renvoyer
au chapitre correspondant pages "285-308", ils ont même pas compris la
différence entre index et toc. Ensuite, il y a une sous-entrée vers
"pointers to" qui me renvoie :
-- page 136 et qui dit uniquement la chose suivante :
"Pointer types are referred to as object pointers or function
pointers(...)", voilà c'est tout dans cette page pour les pointeurs de
fonctions, instructif non ?
-- page 167 où il y a un exemple super compliqué (surchargé) et non
contextualisé où figure, entre autres, une déclaration de pointeur vers
une fonction, faite ainsi :

extern int f(), (*fp)(), (*apf[])(double);

[N'auraient-ils pas dû écrire

extern int f(void), (*fp)(void);

?]

Ensuite , il y a un exemple (non contextualisé) où ils donnent un
exemple d'utilisation de fp (d'ailleurs assez curieux puisqu'il ecrivent

int i,j,k;
i=(*fp)(j,k);

j'y comprends rien, ça doit être du vieux C KR1, non ?)
Et un peu plus loin dans le texte, ils précisent, je dois le
reconnaître, qu'en effet
(*fp)(j,k) peut se réécrire fp(j,k).

*) Delannoy (le gros pavé) est très peu clair sur cette question.

*) K.N. KING lui est au contraire assez clair (mais pas extrêmement
clair pour autant) puisqu'on peut lire dans le chapitre ad hoc et dans
le paragraphe ad hoc que les deux notations sont possibles. Dommage
seulement

-- qu'il le dise au détour d'une phrase, comme ça en passant,
-- qu'il ne donne pas d'exemple d'utilisation contextualisée
-- et dommage qu'il n'explique pas l'intérêt d'une notation sur l'autre.

Charlie Gordon a écrit :

Il n'est en effet pas nécessaire de tester nmemb == 1

Oui, c'est ce que je souhaitais faire, merci de ton amélioration.

Une petite remarque concernant le pointeur de fonction : j'utilise la
syntaxe (*compar)(x, y) pour qu'il soit bien visible que compar n'est
pas le nom d'une fonction,

Et en effet c'est une bonne raison. D'ailleurs Plauger utilise cette
notation.

C'est l'occasion pour moi de regarder un peu ce que dit la littérature
concernant l'utilisation dans le corps de définition d'une fonction d'un
paramètre de type pointeur de fonction.

*) A tout seigneur tout honneur, commençons par la norme. Comme
d'habitude, les explications sont plutôt données de manière relativement
didactique, oui, je dis bien "didactique", car il suffit d'examiner
6.9.1 p14 example 2 pour s'en convaincre même s'ils auraient pu un peu
améliorer la présentation
[au passage, je trouve juste un peu curieux que dans les points de
sémantique de 6.9.1 figure un _exemple_, c'est un peu comme si dans le
Code civil, un article de loi se référait à tel jugement du tribunal de
Becon-les-Bruyères]

*) Passons à K&R, lui qui m'a fait tant souffrir. Seul bon point pour
lui, on sait facilement où regarder pour trouver l'information : c'est
écrit dans la table des matières (pas de quoi pavoiser pour autant,
c'est quand même la moindre des choses). Le § en question, le §5.11,
est un des pires paragraphes de tout le livre d'un point de vue de la
qualité didactique, un sommet dans l'art de l'absconsisation. Tellement
abscons d'ailleurs que les auteurs se sont complètement vautrés dans
leur code, cf. l'errata de l'ouvrage. Naturellement la question de
savoir si on peut appeler notre pointeur par f(truc) au lieu de
(*f)(truc) n'est pas du tout évoqué, les cuisines c'est l'étage en dessous.

*) Autre monstre sacré, le Harbison & Steele. En fait une réputation
mais rien que cela. Le livre est encore pire que le K&R. Moi il ne me
sert que de contre-modèle : si je dois écrire un document didactique, je
me réfère à H&S pour savoir comment ne pas l'écrire. Le titre du livre
de ces messieurs ? Rép. : "C a Reference Manual". Vous avez dit
"référence" ? Vous cherchez des infos sur les pointeurs de fonctions
donc vous commencez par regarder dans la table des matières :

-- il y a un chapitre "Type" avec un § sur les pointeurs mais on n'y
trouve quasiment aucune information sur les pointeurs de fonctions ;

-- il y a un chapitre "Functions" (le dernier chapitre, incroyable !!
c'est exactement le contraire de ce qu'il fallait faire : le chapitre UN
du C c'est les fonctions ...) et dans aucun paragraphe (si je me fie à
leur titre) il n'est question de pointeur vers des fonctions.

Peut-être aurais-je plus de chance avec l'index ? Bon, déjà, ces auteurs
ne savent pas faire un index, il est super lacunaire tout en étant
surabondant. Alors je regarde à "functions" qui commence par me renvoyer
au chapitre correspondant pages "285-308", ils ont même pas compris la
différence entre index et toc. Ensuite, il y a une sous-entrée vers
"pointers to" qui me renvoie :
-- page 136 et qui dit uniquement la chose suivante :
"Pointer types are referred to as object pointers or function
pointers(...)", voilà c'est tout dans cette page pour les pointeurs de
fonctions, instructif non ?
-- page 167 où il y a un exemple super compliqué (surchargé) et non
contextualisé où figure, entre autres, une déclaration de pointeur vers
une fonction, faite ainsi :

extern int f(), (*fp)(), (*apf[])(double);

[N'auraient-ils pas dû écrire

extern int f(void), (*fp)(void);

?]

Ensuite , il y a un exemple (non contextualisé) où ils donnent un
exemple d'utilisation de fp (d'ailleurs assez curieux puisqu'il ecrivent

int i,j,k;
i=(*fp)(j,k);

j'y comprends rien, ça doit être du vieux C KR1, non ?)
Et un peu plus loin dans le texte, ils précisent, je dois le
reconnaître, qu'en effet
(*fp)(j,k) peut se réécrire fp(j,k).

*) Delannoy (le gros pavé) est très peu clair sur cette question.

*) K.N. KING lui est au contraire assez clair (mais pas extrêmement
clair pour autant) puisqu'on peut lire dans le chapitre ad hoc et dans
le paragraphe ad hoc que les deux notations sont possibles. Dommage
seulement

-- qu'il le dise au détour d'une phrase, comme ça en passant,
-- qu'il ne donne pas d'exemple d'utilisation contextualisée
-- et dommage qu'il n'explique pas l'intérêt d'une notation sur l'autre.

Vous avez filtré cet utilisateur ! Consultez son message

Charlie Gordon a écrit :

Il n'est en effet pas nécessaire de tester nmemb == 1

Oui, c'est ce que je souhaitais faire, merci de ton amélioration.

Une petite remarque concernant le pointeur de fonction : j'utilise la
syntaxe (*compar)(x, y) pour qu'il soit bien visible que compar n'est
pas le nom d'une fonction,

Et en effet c'est une bonne raison. D'ailleurs Plauger utilise cette
notation.

C'est l'occasion pour moi de regarder un peu ce que dit la littérature
concernant l'utilisation dans le corps de définition d'une fonction d'un
paramètre de type pointeur de fonction.

*) A tout seigneur tout honneur, commençons par la norme. Comme
d'habitude, les explications sont plutôt données de manière relativement
didactique, oui, je dis bien "didactique", car il suffit d'examiner
6.9.1 p14 example 2 pour s'en convaincre même s'ils auraient pu un peu
améliorer la présentation
[au passage, je trouve juste un peu curieux que dans les points de
sémantique de 6.9.1 figure un _exemple_, c'est un peu comme si dans le
Code civil, un article de loi se référait à tel jugement du tribunal de
Becon-les-Bruyères]

*) Passons à K&R, lui qui m'a fait tant souffrir. Seul bon point pour
lui, on sait facilement où regarder pour trouver l'information : c'est
écrit dans la table des matières (pas de quoi pavoiser pour autant,
c'est quand même la moindre des choses). Le § en question, le §5.11,
est un des pires paragraphes de tout le livre d'un point de vue de la
qualité didactique, un sommet dans l'art de l'absconsisation. Tellement
abscons d'ailleurs que les auteurs se sont complètement vautrés dans
leur code, cf. l'errata de l'ouvrage. Naturellement la question de
savoir si on peut appeler notre pointeur par f(truc) au lieu de
(*f)(truc) n'est pas du tout évoqué, les cuisines c'est l'étage en dessous.

*) Autre monstre sacré, le Harbison & Steele. En fait une réputation
mais rien que cela. Le livre est encore pire que le K&R. Moi il ne me
sert que de contre-modèle : si je dois écrire un document didactique, je
me réfère à H&S pour savoir comment ne pas l'écrire. Le titre du livre
de ces messieurs ? Rép. : "C a Reference Manual". Vous avez dit
"référence" ? Vous cherchez des infos sur les pointeurs de fonctions
donc vous commencez par regarder dans la table des matières :

-- il y a un chapitre "Type" avec un § sur les pointeurs mais on n'y
trouve quasiment aucune information sur les pointeurs de fonctions ;

-- il y a un chapitre "Functions" (le dernier chapitre, incroyable !!
c'est exactement le contraire de ce qu'il fallait faire : le chapitre UN
du C c'est les fonctions ...) et dans aucun paragraphe (si je me fie à
leur titre) il n'est question de pointeur vers des fonctions.

Peut-être aurais-je plus de chance avec l'index ? Bon, déjà, ces auteurs
ne savent pas faire un index, il est super lacunaire tout en étant
surabondant. Alors je regarde à "functions" qui commence par me renvoyer
au chapitre correspondant pages "285-308", ils ont même pas compris la
différence entre index et toc. Ensuite, il y a une sous-entrée vers
"pointers to" qui me renvoie :
-- page 136 et qui dit uniquement la chose suivante :
"Pointer types are referred to as object pointers or function
pointers(...)", voilà c'est tout dans cette page pour les pointeurs de
fonctions, instructif non ?
-- page 167 où il y a un exemple super compliqué (surchargé) et non
contextualisé où figure, entre autres, une déclaration de pointeur vers
une fonction, faite ainsi :

extern int f(), (*fp)(), (*apf[])(double);

[N'auraient-ils pas dû écrire

extern int f(void), (*fp)(void);

?]

Ensuite , il y a un exemple (non contextualisé) où ils donnent un
exemple d'utilisation de fp (d'ailleurs assez curieux puisqu'il ecrivent

int i,j,k;
i=(*fp)(j,k);

j'y comprends rien, ça doit être du vieux C KR1, non ?)
Et un peu plus loin dans le texte, ils précisent, je dois le
reconnaître, qu'en effet
(*fp)(j,k) peut se réécrire fp(j,k).

*) Delannoy (le gros pavé) est très peu clair sur cette question.

*) K.N. KING lui est au contraire assez clair (mais pas extrêmement
clair pour autant) puisqu'on peut lire dans le chapitre ad hoc et dans
le paragraphe ad hoc que les deux notations sont possibles. Dommage
seulement

-- qu'il le dise au détour d'une phrase, comme ça en passant,
-- qu'il ne donne pas d'exemple d'utilisation contextualisée
-- et dommage qu'il n'explique pas l'intérêt d'une notation sur l'autre.

candide

03/10/2008 à 14:53

Charlie Gordon a écrit :

/* bsearch function */
#include <stdlib.h>

void *(bsearch)(const void *key, const void *base,
size_t nelem, size_t size, _Cmpfun *cmp)
{ /* search sorted table by binary chop */
const char *p = base;
size_t n;

for (p = base, n = nelem; 0 < n; )
{ /* check midpoint of whatever is left */
const size_t pivot = n >> 1;
const char *const q = p + size * pivot;
const int val = (*cmp)(key, q);

if (val < 0)
n = pivot; /* search below pivot */
else if (val == 0)
return ((void *)q); /* found */
else
{ /* search above pivot */
p = q + size;
n -= pivot + 1;
}
}
return (NULL); /* no match */
}

T'as scanné le code ? t'as une version numérique du livre ? T'as quand
même pas recopié le code à la main, c'est copie conforme, aux espaces
près, de sa Figure 13.8 page 356 ?

Charlie Gordon

03/10/2008 à 17:11

"candide" a écrit dans le message de news:
48e615d6$0$8937$

Charlie Gordon a écrit :

/* bsearch function */
#include <stdlib.h>

void *(bsearch)(const void *key, const void *base,
size_t nelem, size_t size, _Cmpfun *cmp)
{ /* search sorted table by binary chop */
const char *p = base;
size_t n;

for (p = base, n = nelem; 0 < n; )
{ /* check midpoint of whatever is left */
const size_t pivot = n >> 1;
const char *const q = p + size * pivot;
const int val = (*cmp)(key, q);

if (val < 0)
n = pivot; /* search below pivot */
else if (val == 0)
return ((void *)q); /* found */
else
{ /* search above pivot */
p = q + size;
n -= pivot + 1;
}
}
return (NULL); /* no match */
}

T'as scanné le code ? t'as une version numérique du livre ? T'as quand
même pas recopié le code à la main, c'est copie conforme, aux espaces
près, de sa Figure 13.8 page 356 ?

Comme tu l'as remarqué, je suis du genre pointilleux sur les petits détails,
et l'espacement est une partie importante de la présentation et donc de la
lisibilité. Non je n'ai pas scanné le bouquin, j'ai bêtement demandé à
google codesearch de me trouver des sources qui contiennent "const char
*const q = p + size * pivot", bout de code passablement spécifique de
l'auteur. J'ai ainsi trouvé 2 packages qui réutilisent le code de Plauger,
dont un qui n'avait modifié que légèrement la présentation :
http://surf.de.uu.net/gnuland/atari/scc-3.0.tar.gz module
scc-3.0/src/ansi/stdlib/bsearch.c
J'ai ensuite remis les conventions discutables de Plauger pour pouvoir les
critiquer ;-)

--
Chqrlie.

Antoine Leca

07/10/2008 à 14:09

En news:48e6139f$0$10248$, candide va escriure:

tel jugement du tribunal de Becon-les-Bruyères

Il n'y a pas de Tribunal à Bécon. Au minimum, parce que Bécon n'est qu'un
lieu-dit (d'Asnières ou de Courbevoie, selon le côté de la voie où tu es),
pas une commune. Ensuite, parce que le TI d'Asnières est à La Redoute (à
l'autre bout de la ville), tandis que celui de Courbevoie est proche de la
mairie centrale, de l'autre côté du boulevard de Verdun, un quart d'heure à
pied depuis Bécon.

extern int f(), (*fp)(), (*apf[])(double);

[N'auraient-ils pas dû écrire

extern int f(void), (*fp)(void);

Non, il y a des différences entre les deux. La plus évidente est que tu peux
écrire

int f(a,b) int a,b; { return f(a) + fp(b); }

avec l'écriture d'en haut, _pas_ avec cele d'en bas.
Ou encore, autre point de vue, que le compilateur va se plaindre si tu as
écrit auparavant la version d'en bas, mais pas obligatoirement grogner si tu
as écrit la version d'en haut...

Antoine

candide

09/10/2008 à 00:13

Antoine Leca a écrit :

En news:48e6139f$0$10248$, candide va escriure:
tel jugement du tribunal de Becon-les-Bruyères

Il n'y a pas de Tribunal à Bécon.

Certes mais il y a bien des exemples dans la sémantique.

Non, il y a des différences entre les deux. La plus évidente

"évident" dis-tu ?

est que tu peux
écrire

int f(a,b) int a,b; { return f(a) + fp(b); }

C jurassique ou crétacé inférieur ? ;)

Retour de la fonction bsearch

10 réponses

Veuillez sélectionner un problème