Vous cherchez un bon quiz bonus à l'efficacité des tests (en particulier l'efficacité par rapport au temps) [fermé]

Question

Je suis en train de faire un laboratoire d'introduction à l'informatique une fois par semaine. J'espérais avoir un concours rapide à la fin de mon laboratoire suivant. Je veux leur donner un bloc de code comme ceci:

public class EfficientCode{

    public static void main(){
        long startTime, endTime, executionTime;
        startTime = System.currentTimeMillis();

        yourEfficientMethod():
        endTime = System.currentTimeMillis();
        executionTime = endTime – startTime;

    }

    public static void doSomething(){
        // you do this part.  
    }

}

Ils mettront en œuvre la méthode doSomething et la personne avec le code le plus rapide obtenir une poignée de marques de bonus.

Le problème est que la question doit être assez simple. Les élèves ont une bonne connaissance de: boucles, if / else, Cordes, ajoutant, tableaux, etc.

Voici mes idées pour ce que la question pourrait être:

• trouver tous les nombres parfaits entre 1 et 1.000.000. (Un nombre parfait est un numéro où tous les facteurs du nombre ajouter au nombre Ie:. 6 = 3 + 2 + 1)
• trouver tous les nombres premiers entre 1 et 1.000.000

Je pense que pour qu'il y ait une différence mesurable de la performance entre les méthodes que vous devez faire quelque chose plusieurs fois.

Answer 1

Parce que c'est un cours d'initiation et vos élèves ont, je pense ne sont pas couverts de tri mais il va être très difficile de trouver assez de simple quelque chose à faire, assez intéressant d'avoir plusieurs façons de le faire, et complexe assez qu'il ya une différence appréciable de vitesse entre les différentes implémentations sur un ordinateur moderne. Votre vrai problème, cependant, est que quelque chose assez simple pour eux d'essayer a déjà une mise en œuvre canonique à une courte distance de recherche Google.

Ma suggestion est d'inverser le défi. Demandez à vos étudiants en compétition pour trouver la gnarliest, le plus lent, la solution la plus monopolisant mémoire qu'ils peuvent penser. Je crois qu'il est aussi important de penser pédagogiquement sur toutes les mauvaises façons de faire quelque chose comme il est de penser à droite, et il est tout aussi difficile d'être le pire comme il est d'être le meilleur. Il est plus facile de voir les résultats subjectivement aussi bien depuis le mauvais code sera vraiment lent. Pas de recherche sur Google pour une réponse non plus. Enfin, dans mon (non pertinent) avis, cela a l'avantage supplémentaire de rendre le défi plus amusant.

Quelque chose comme trouver une chaîne dans une autre est plus facile fait mal que de bien. ont peut-être les extraire tous les nombres premiers d'une chaîne de 2kb de caractères alphanumériques aléatoires. Beaucoup de façons de faire de l'oreille de ce problème d'un porc.

Answer 2

D'accord au sujet de « plusieurs fois » pour les opérations courtes, mais pour les plus longues, une fois pourrait être suffisant en soi.

Je suggère à la recherche dans Projet Euler , une excellente collection de questions de programmation. La meilleure partie est que les problèmes sont conçus avec un « minutes de punition dans » à l'esprit que la plupart des problèmes devraient prendre un ordinateur modéré moins d'une minute pour exécuter une efficace algorithme pour trouver les réponses. Donc, un excellent endroit pour commencer. :)

Answer 3

Deux choses.

Tout d'abord, l'efficacité est plus que temps d'exécution. Il est également sur l'utilisation de la mémoire, l'accès mémoire, système de fichiers / accès aux ressources, etc. Il y a des tonnes de choses qui entrent dans l'efficacité. Alors s'il vous plaît soyez explicite que vous êtes à la recherche de la routine avec le plus court d'exécution. Sinon, vous envoyez un message mixte ...

En second lieu, j'ai entendu ce problème il y a environ 15 ans, et je ne peux pas l'oublier:

produire une liste de toutes les paires de numéro à 5 chiffres cette somme à 121212. Cependant, aucune des 2 chiffres peut répéter un chiffre décimal. Alors 1 ne peut apparaître qu'une seule fois dans les deux numéro. Ainsi, un résultat exemple paire est 98167 + 23045. Il y a un certain nombre de juste, et il est facile de construire une solution de force brute, mais une solution efficace nécessite une certaine réflexion. Il y a 192 paires uniques ...

Answer 4

Ce sont de bonnes idées. Qu'en est-il d'avoir une question de tri?

Answer 5

Tri d'un tableau de nombres pourrait être aussi une bonne idée, car il y a tout un tas d'algorithmes pour elle (insertion, sélection, rapide, tas, etc.) qui ont toutes les caractéristiques de performances différentes. Cela permettrait également de donner aux étudiants une chance d'en apprendre davantage sur la notation grand-O, etc.