"Jean-Marc Bourguet" <jm@bourguet.org> a écrit dans le message de news:
pxb3ajfm6h7.fsf@news.bourguet.org...

"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.

Ah bon ?  Peux-tu être plus explicite ?

(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.

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.

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.

Effectivement, si l'algorithme repose sur une recherche de prefixes, le hash
est inadapté.
Le probleme de Boggle a peut-etre une complexité supérieure au Scrabble,
pour lequel un hash des combinaisons de lettres est a la base de programmes
qui jouent des parties entières optimales en duplicate en une fraction de
seconde.

--
Chqrlie.