Charlie Gordon a écrit :

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:

C'est une plaie tout simplement parce que c'est une plaie de réinventer la roue chaque matin au petit déjeuner ... Quant à la longueur, ce n'est pas un argument.

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;
}

Et ce genre de code, il faut pas mal d'années de pratique pour arriver à le pondre en 20 minutes et au saut du lit.

Secondo, la sémantique qui t'intéresse est triviale à obtenir en remplacant

C'est ce que je dis depuis le début mais je n'ai pas envie de recoder bsearch pour lui rajouter une trivialité.

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.

Oui, tu veux dire la structure (le /trie/) dont Jean-Marc a parlé ci-dessus. Décidément les informaticiens vous êtes faits sur le même moule, je parlais de ce problème avec un collègue informaticien et il m'a répondu exactement la même chose que vous.


À problème simple j'aime bien essayer d'apporter une solution simple. Il existe un algorithme de recherche de mot naïf et facile  à implémenter qui simule complètement la structure de données évoquées par JMB (sauf que le parcours séquentiel des successeurs d'un noeud est remplacé par une recherche dichotomique).

Il est vrai néanmoins que cette structure de données est bien adaptée au problème posée et qu'elle diminuera la taille des données à consulter et que l'exécution sera sensiblement plus rapide. Mais le binary search est aussi assez rapide surtout si tu l'aides en lui donnant les adresses des lettres initiales (ce sont elles qui nécessitent le traitement le plus long). Moi j'ai l'impression que les temps sont assez comparables.

Ce qui ne m'incite pas à choisir la structure de données  c'est qu'il faut s'en taper l'implémentation puis la routine de recherche dans le /trie/, conceptuellement assez facile, techniquement moins facile. Mais avec plus de pratique peut-être effectivement que je ferais comme vous.