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;
}
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.
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;
}
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.
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;
}
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.
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
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.
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
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.
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
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.
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 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 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 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 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 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 ?
(...) tu nous a fait
une belle boucle infinie.
(Et je ne vois pas l'utilite du +1 dans a = m
+1).
(...) tu nous a fait
une belle boucle infinie.
(Et je ne vois pas l'utilite du +1 dans a = m
+1).
(...) tu nous a fait
une belle boucle infinie.
(Et je ne vois pas l'utilite du +1 dans a = m
+1).
Bonjour,
Juste un avis perso : le retour de la fonction bsearch est peu exploitabl e.
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). 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. Hélas bsearch se contente de donn er
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 ?
Bonjour,
Juste un avis perso : le retour de la fonction bsearch est peu exploitabl e.
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). 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. Hélas bsearch se contente de donn er
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 ?
Bonjour,
Juste un avis perso : le retour de la fonction bsearch est peu exploitabl e.
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). 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. Hélas bsearch se contente de donn er
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 ?
In article <gc2i75$d3d$,
Charlie Gordon wrote: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 ?
Parce que, dans ce cas precis, c'est de la recursion terminale, et que
donc
tout compilateur decent saura faire de la tail-recursion optimization,
et donc que c'est strictement equivalent a la solution iterative ?
In article <gc2i75$d3d$1@registered.motzarella.org>,
Charlie Gordon <news@chqrlie.org> wrote:
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 ?
Parce que, dans ce cas precis, c'est de la recursion terminale, et que
donc
tout compilateur decent saura faire de la tail-recursion optimization,
et donc que c'est strictement equivalent a la solution iterative ?
In article <gc2i75$d3d$,
Charlie Gordon wrote: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 ?
Parce que, dans ce cas precis, c'est de la recursion terminale, et que
donc
tout compilateur decent saura faire de la tail-recursion optimization,
et donc que c'est strictement equivalent a la solution iterative ?
Charlie Gordon a écrit :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 ?
Je ne connais aucun langage fonctionnel. La récursivité ici est assez
naturelle et le code est, je trouve, plus lisible.
Et pour moi, la lisibilité, ça compte.
Pourquoi pour qsort on implémente récursif et on ne le ferait pas pour
bsearch après tout ?
Charlie Gordon a écrit :
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 ?
Je ne connais aucun langage fonctionnel. La récursivité ici est assez
naturelle et le code est, je trouve, plus lisible.
Et pour moi, la lisibilité, ça compte.
Pourquoi pour qsort on implémente récursif et on ne le ferait pas pour
bsearch après tout ?
Charlie Gordon a écrit :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 ?
Je ne connais aucun langage fonctionnel. La récursivité ici est assez
naturelle et le code est, je trouve, plus lisible.
Et pour moi, la lisibilité, ça compte.
Pourquoi pour qsort on implémente récursif et on ne le ferait pas pour
bsearch après tout ?
"Charlie Gordon" writes: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;
}
Il ne faut pas coder avant le petit dejeuner :-) La preuve, tu nous a fait
une belle boucle infinie.
(Et je ne vois pas l'utilite du +1 dans a = m + 1).
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.
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.
Il a l'air d'avoir besoin de prefixes (j'ai toujours pas ete voir le jeu),
auquel cas une hash table n'est pas particulierement adaptee.
"Charlie Gordon" <news@chqrlie.org> writes:
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;
}
Il ne faut pas coder avant le petit dejeuner :-) La preuve, tu nous a fait
une belle boucle infinie.
(Et je ne vois pas l'utilite du +1 dans a = m + 1).
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.
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.
Il a l'air d'avoir besoin de prefixes (j'ai toujours pas ete voir le jeu),
auquel cas une hash table n'est pas particulierement adaptee.
"Charlie Gordon" writes: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;
}
Il ne faut pas coder avant le petit dejeuner :-) La preuve, tu nous a fait
une belle boucle infinie.
(Et je ne vois pas l'utilite du +1 dans a = m + 1).
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.
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.
Il a l'air d'avoir besoin de prefixes (j'ai toujours pas ete voir le jeu),
auquel cas une hash table n'est pas particulierement adaptee.
difficile de ne pas en faire. Ecrire un qsort sur une feuille blanche, qui
fonctionne correctement du premier coup est une prouesse remarquable.
difficile de ne pas en faire. Ecrire un qsort sur une feuille blanche, qui
fonctionne correctement du premier coup est une prouesse remarquable.
difficile de ne pas en faire. Ecrire un qsort sur une feuille blanche, qui
fonctionne correctement du premier coup est une prouesse remarquable.
