Retour de la fonction bsearch

En news:48e3534c$0$29455$426a74cc@news.free.fr, candide va escriure:

Juste un avis perso : le retour de la fonction bsearch est peu
exploitable.

Euh, si tu cherches un élément dans une liste, le fait de te retourner un
pointeur vers cet élément, c'est assez exactement l'objectif recherché, non?

Bien souvent, face à une liste croissante, on ne se préoccupe pas
essentiellement de savoir si un élément donné s'y trouve ou ne s'y
trouve pas, on cherche à savoir où il est placé dans la liste (et
éventuellement hors de la liste à gauche ou à droite).

Cela dépend complètement de ce que tu veux faire avec ta « liste
croissante ». Si tu _recherches_ un élément qui est censé y exister, la
valeur retournée par bsearch me semble adaptée (et en anglais, rechercher se
dit "to search", et non, ce n'est pas un hasard ;-))

Si par contre tu as un autre objectif, peut-être préparer un tri par
insertion ou que sais-je, il est probable que la fonction bsearch sera
sous-optimale...

Or, quel que
soit l'algorithme utilisé par bsearch (recherche séquentielle ou
dichotomique), bsearch serait en mesure sans coût supplémentaire
excessif de donner cette position.

1) Tu tombes au bon moment pour proposer que la norme C1x inclut une
fonction fsearch() [f pour "fuzzy"]

2) C'est un peu comme avec les propositions des politiques, j'aime bien
connaître le détail, histoire de voir le coût réel du supplément « non
excessif » ; entre autres questions qui me viennent à l'esprit, serait-ce un
paramètre supplémentaire ? retourner une structure ? avec ou sans restrict ?
Ou, dans un autre domaine, y a-t'il des microcontrôlleurs avec la fonction
bsearch() câblée, ou des optimisateurs capables d'analyser le code pour
utiliser par exemple SCANS sur architecture 8086, qui auraient alors une
pénalité importante à l'utilisation de ta proposition alternative ?
[ L'histoire de scans est un exemple, je sais parfaitement qu'aujourd'hui
une telle optimisation ne serait pas rentable. ]

3) Tu dois évaluer l'utilité de cette amélioration (cas où elle apporte
réellement quelque chose en _plus_ de ce qui existe déjà), et le comparer
avec tous les cas similaires, y compris par exemple les algorithmes d'arbres
balancés (où ni l'une ni l'autre des deux fonctions ne s'appliquent) ; je ne
suis pas certain que le bilan global soit exceptionnel.

Hélas bsearch se contente de
donner une réponse binaire. Et je trouve particulièrement agaçant
d'avoir à me recoder un truc aussi classique qu'une recherche
dichotomique, pas vous ?

bsearch est historique, elle doit avoir 30 ±2 ans...
Donc en 1987, il n'était plus question de proposer une alternative, la seule
question futde considérer si cela valait la peine d'avoir cela dans la norme
(difficulté de codage sans erreur, bon rapport poids/performance de mettre
telle ou telle fonction dans la bibliothèque standard, entre autres) ou pas
; bsearch(3) a passé la barre de même que qsort(3), mais pas leur homologue
lsearch(3) [recherche « linéaire » dans un tableau pas forcément trié].


Antoine

Antoine Leca a écrit :

2) C'est un peu comme avec les propositions des politiques, j'aime bien
connaître le détail, histoire de voir le coût réel du supplément « non
excessif » ; entre autres questions qui me viennent à l'esprit, serait-ce un
paramètre supplémentaire ? retourner une structure ? avec ou sans restrict ?

Comment fonctionne une recherche dichotomique ? elle finit par encadrer
la clé par deux éléments consécutifs du tableau. En fait, pas tout à
fait, si la recherche a du bol, elle peut trouver la réponse avant
d'avoir encadré la clé. Par exemple si la liste est

int t[7]= {5, 9, 10, 19, 34, 34, 45}

le premier pivot est 19 (index (0+6)/2=3) et si la valeur cherchée est
justement 19, bsearch va s'arrêter là et renvoyer l'adresse correspondante.

Par convention, on aurait pu décider que l'adresse renvoyée serait celle
de l'élément directement supérieur et NULL si on sort à droite du
tableau de valeur. Donc je ne vois pas ce que ça coûte, c'est epsilon en
plus, on renvoie un pointeur, pareil, ça marche même dans le cas où on a
du bol. Pour reprendre mon exemple ci-dessus, si la clé vaut 20, on
renvoie t+4, si la clé est 34, on renvoie t+4 ou t+5 et si la clé est 50
on renvoie NULL.

Toutefois, ça présente l'inconvénient qu'on n'est pas sûr que la clé
soit présente lorsque le retour est non NULL et ça oblige l'utilisateur
à tester le retour pour être sûr.

De toute façon, si ça n'a pas été fait ainsi c'est que ça ne présentait
pas suffisamment d'intérêt pour une majorité de gens.

Je viens de regarder l'implémentation de Plauger et à ma grande
surprise, elle n'est pas récursive mais ça doit sans doute être plus
efficace.

Jean-Marc Bourguet a écrit :

Je ne me souviens pas d'une fois ou ce que tu proposes aurais evite de
devoir le faire.

Tu veux faire un solveur de Boggle
(cf. http://massiveboggle.fr/game/play).

Tu as un lexique qui fait presque 400000 mots (l'officiel du scrabble
version 5) sous forme de fichier texte. Tu charges ce lexique en mémoire
(pour pouvoir accéder aux mots autrement que séquentiellement).

L'algorithme de résolution du boggle est facile, c'est en fait un DFS.
Tu vas être amené à répondre à ce genre de questions : comment trouver
le premier mot du lexique qui commence par 'K' alors que cette lettre
n'est pas un mot figurant dans le lexique en sorte que bsearch va
renvoyer nul. Pourtant, bsearch aura examiné dans son algorithme (sauf
bol particulier) les mots JUXTATROPICAUX (d'index 215226) et KA
(d'indice 215227), c'est dommage de ne pouvoir l'utiliser. Donc, si on
ne veut pas se contenter d'une recherche séquentielle (qui d'ailleurs
tournera sans lenteur sur un P4) il faut se recoder une recherche
dichotomique, quelle plaie !


En fait, je pourrais étendre mon propos. Ce qu'il pourrait être
intéressant de coder, c'est une recherche dichotomique qui épargne d'en
coder jamais une, une sorte de dichotomie générique avec une interface
plus générale que celle de bsearch. Voici deux exemples où on a besoin
de coder une dichotomie :

*) Résoudre une équation f(x)=0 ? Même un bsearch aménagé n'y suffirait
pas.

*) On a un "tableau" de N "boules", d'abord que des boules blanches puis
que des boules noires (avec au moins une boule noire). Question :
trouver la position de la première boule noire. La solution naturelle
est une dichotomie.

Marc Boyer wrote:

D'ailleurs, une recherche dichotomique dans une liste, ça
va être dur...

J'ai vu ça dans un sujet d'exam... Je vais rester pudique et
ne pas donner de noms hein :-)

candide <candide@free.invalid> writes:

Jean-Marc Bourguet a écrit :
> Je ne me souviens pas d'une fois ou ce que tu proposes aurais evite de
> devoir le faire.
>

Tu veux faire un solveur de Boggle
(cf. http://massiveboggle.fr/game/play).

Tu as un lexique qui fait presque 400000 mots (l'officiel du scrabble
version 5) sous forme de fichier texte. Tu charges ce lexique en mémoire
(pour pouvoir accéder aux mots autrement que séquentiellement).

J'ai pas ete voir le jeu, mais il y a de bones chances que j'utiliserais
une autre structure de donnee qu'un tableau trie. Les tries
(http://fr.wikipedia.org/wiki/Trie) sont les premiers candidats, mais il y
en a d'autres.

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 wrote:

Tu as un lexique qui fait presque 400000 mots (l'officiel du scrabble
version 5) sous forme de fichier texte. Tu charges ce lexique en mémoire
(pour pouvoir accéder aux mots autrement que séquentiellement).

C'est un peu HS mais on peut la récupérer quelque part cette liste de mots ?

batyann811 a écrit :

C'est un peu HS mais on peut la récupérer quelque part cette liste de
mots ?

Par exemple ici :

http://www.madfix.com/ods/

candide wrote:

Par exemple ici :

http://www.madfix.com/ods/

Merci

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

Jean-Marc Bourguet a écrit :

Je ne me souviens pas d'une fois ou ce que tu proposes aurais evite de
devoir le faire.

Tu veux faire un solveur de Boggle
(cf. http://massiveboggle.fr/game/play).

Tu as un lexique qui fait presque 400000 mots (l'officiel du scrabble
version 5) sous forme de fichier texte. Tu charges ce lexique en mémoire
(pour pouvoir accéder aux mots autrement que séquentiellement).

L'algorithme de résolution du boggle est facile, c'est en fait un DFS. Tu
vas être amené à répondre à ce genre de questions : comment trouver le
premier mot du lexique qui commence par 'K' alors que cette lettre n'est
pas un mot figurant dans le lexique en sorte que bsearch va renvoyer nul.
Pourtant, bsearch aura examiné dans son algorithme (sauf bol particulier)
les mots JUXTATROPICAUX (d'index 215226) et KA (d'indice 215227), c'est
dommage de ne pouvoir l'utiliser. Donc, si on ne veut pas se contenter
d'une recherche séquentielle (qui d'ailleurs tournera sans lenteur sur un
P4) il faut se recoder une recherche dichotomique, quelle plaie !

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. Une implementation simple et de bon gout fait à peine un
vingtaine de lignes:

void *bsearch(const void *key, const void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
size_t a = 0;
size_t b = nmemb;

while (a < b) {
size_t m = (a + b) / 2;
const void *p = (const char *)base + m * size;
int cmp = (*compar)(key, p);
if (cmp < 0)
b = m;
else
if (cmp > 0)
a = m + 1;
else
return (void *)p;
}
return NULL;
}

Secondo, la sémantique qui t'intéresse est triviale à obtenir en remplacant
le ``return NULL'' final par ``return (void*)((const char *)base + a *
size)''.

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 ;-).

Troisièmement, la recherche dichotomique n'est pas le meilleur algorithme
pour le probleme posé (boggle solver). Il sera bien plus efficace de stocker
tous les mots possibles dans un tableau associatif (hash table)
convenablement dimensionné et avec une API de recherche efficace.

--
Chqrlie.

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

Antoine Leca a écrit :

2) C'est un peu comme avec les propositions des politiques, j'aime bien
connaître le détail, histoire de voir le coût réel du supplément « non
excessif » ; entre autres questions qui me viennent à l'esprit, serait-ce
un
paramètre supplémentaire ? retourner une structure ? avec ou sans
restrict ?

Comment fonctionne une recherche dichotomique ? elle finit par encadrer la
clé par deux éléments consécutifs du tableau. En fait, pas tout à fait, si
la recherche a du bol, elle peut trouver la réponse avant d'avoir encadré
la clé. Par exemple si la liste est

int t[7]= {5, 9, 10, 19, 34, 34, 45}

le premier pivot est 19 (index (0+6)/2=3) et si la valeur cherchée est
justement 19, bsearch va s'arrêter là et renvoyer l'adresse
correspondante.

Par convention, on aurait pu décider que l'adresse renvoyée serait celle
de l'élément directement supérieur et NULL si on sort à droite du tableau
de valeur. Donc je ne vois pas ce que ça coûte, c'est epsilon en plus, on
renvoie un pointeur, pareil, ça marche même dans le cas où on a du bol.
Pour reprendre mon exemple ci-dessus, si la clé vaut 20, on renvoie t+4,
si la clé est 34, on renvoie t+4 ou t+5 et si la clé est 50 on renvoie
NULL.

Toutefois, ça présente l'inconvénient qu'on n'est pas sûr que la clé soit
présente lorsque le retour est non NULL et ça oblige l'utilisateur à
tester le retour pour être sûr.

De toute façon, si ça n'a pas été fait ainsi c'est que ça ne présentait
pas suffisamment d'intérêt pour une majorité de gens.

Je viens de regarder l'implémentation de Plauger et à ma grande surprise,
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 ?

C'est en effet plus efficace de faire une simple boucle, mais il y a fort à
parier que les compilateurs modernes auraient détecté la récursion terminale
et produit un code similaire.

--
Chqrlie.