Comment expliquer ce qu'est une «implémentation naïve»?

Question

Quelle est l'explication la plus claire de ce que les informaticiens entendent par "l'implémentation naïve"? J'ai besoin d'un bon exemple clair qui illustrera - idéalement, même pour des personnes non techniques - que la mise en œuvre naïve peut être techniquement une solution fonctionnelle au problème, mais pratiquement totalement inutilisable.

Answer 1

Je vais essayer de les éloigner de l'ordinateur. Demandez à votre auditoire comment trouver une entrée dans un dictionnaire. (Normal d'un dictionnaire de définitions de mots.)

L'implémentation naïve est de commencer par le tout début, et de regarder le premier mot. Oh, ce n'est pas la parole, nous sommes à la recherche pour le look à la suivante, etc. Il est intéressant de montrer à l'auditoire qu'il n'a probablement même pas penser de cette façon de faire les choses - nous sommes suffisamment intelligents pour la remise immédiatement! Il est, cependant, au sujet de la façon la plus simple que vous pourriez penser. (Il pourrait être intéressant de leur demander s'ils peuvent penser à quelque chose de plus simple et de vérifier qu'ils n'vraiment comprendre pourquoi c'est plus simple que la façon dont nous le faire.)

La prochaine mise en œuvre (et un plutôt bon) est de commencer dans le milieu de la dictionnaire. Le mot que nous cherchons avant ou après? Si c'est avant, tourner la page, à mi-chemin entre le début et où nous en sommes - sinon, passer à la page de la moitié du chemin entre l'endroit où nous sommes maintenant et la fin, etc - binaire hachez-les.

De l'homme, de la mise en œuvre est d'utiliser nos connaissances sur les lettres pour obtenir très rapidement à "près de le bon endroit" - si nous voyons "l'éléphant" nous saurons alors ce sera "quelque part près de la start" peut-être d'environ 1/5e de la voie à travers. Une fois que nous avons à E (que l'on peut faire avec de très, très simple comparaisons), on trouve EL etc.

Answer 2

Jeff Atwood de StackOverflow avait un excellent exemple d'algorithme naïf lié au brassage d'un tableau.

Answer 3

Le faire le plus simple, le moins délicat voie disponible. Un exemple est la sélection du tri.

Dans ce cas naïf ne pas dire mauvais ou inutilisable. Cela signifie simplement pas particulièrement bon.

---

La prise de Jon Skeet conseils à cœur, vous pouvez décrire la sélection de sorte que:

1. Trouver la valeur la plus élevée dans la liste et de le mettre en premier
2. Trouver la prochaine valeur la plus élevée et l'ajouter à la liste
3. Répétez l'étape 2 jusqu'à ce que vous exécutez hors de la liste

Il est facile à faire et facile à comprendre, mais pas nécessairement la meilleure.

Answer 4

une autre implémentation naïve serait l'utilisation de la récursivité dans le calcul pour la factorielle d'un entier dans un langage impératif. une solution plus efficace dans ce cas consiste simplement à utiliser une boucle.

Answer 5

Ce qui est le plus évident, naïfs algorithme d'exponentiation que vous pourriez penser?

base ** exp est base * base * ... * base, exp fois:

double pow(double base, int exp) {
    double result = 1;
    for (int i = 0; i < exp; i++)
        result *= base;
    return result;
}

Il ne gère pas les exposants négatifs, cependant. En se souvenant que, base ** exp == 1 / base ** (-exp) == (1 / base) ** (-exp):

double pow(double base, int exp) {
    double result = 1;
    if (exp < 0) {
        base = 1 / base;
        exp = -exp;
    }
    for (int i = 0; i < exp; i++)
        result *= base;
    return result;
}

Il est possible de calculer base ** exp avec moins de exp multiplications, si!

double pow(double base, int exp) {
    double result = 1;
    if (exp < 0) {
        base = 1 / base;
        exp = -exp;
    }
    while (exp) {
        if (exp % 2) {
            result *= base;
            exp--;
        }
        else {
            base *= base;
            exp /= 2;
        }
    }
    return result * base;
}

Cette méthode tire parti du fait que l' base ** exp == (base * base) ** (exp / 2) si exp est même, et vous aurez seulement besoin d'environ log2(exp) de multiplications.