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