Buscando una buena prueba de bonificación para probar la eficiencia (específicamente la eficiencia relacionada con el tiempo) [cerrado

Question

Estoy haciendo una introducción al Laboratorio de Ciencias de la Computación una vez por semana. Esperaba tener un concurso rápido al final de mi próximo laboratorio. Quiero darles un bloque de código como este:

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

}

Implementarán el método de dos tendencias y la persona con el código más rápido obtendrá un puñado de marcas de bonificación.

El problema es que la pregunta debe ser algo simple. Los estudiantes tienen una buena comprensión de: bucles, si/else, cuerdas, agregando, matrices, etc.

Estas son mis ideas para cuáles podrían ser la pregunta:

• Encuentra todos los números perfectos entre 1 y 1,000,000. (Un número perfecto es un número donde todos los factores del número se suman al número. Es decir: 6 = 3 + 2 + 1)
• Encuentre todos los números primos entre 1 y 1,000,000

Creo que para que haya una diferencia medible en el rendimiento entre los métodos, debe hacer algo muchas veces.

Answer 1

Porque esta es una clase introductoria y sus estudiantes aún no han cubierto la clasificación. es una diferencia apreciable de velocidad entre las diferentes implementaciones en una computadora moderna. Sin embargo, su verdadero problema es que cualquier cosa lo suficientemente simple como para que lo intenten ya tiene una implementación canónica a solo una breve búsqueda en Google.

Mi sugerencia es invertir el desafío. Haga que sus alumnos compitan para crear la solución más retorcida, más lenta y de acero de memoria que se les ocurra. Creo que es tan valioso educativamente pensar en todas las formas incorrectas de hacer algo como pensar en el derecho, y es tan difícil ser lo peor como lo mejor. Es más fácil ver los resultados subjetivamente también ya que el código malo será De Verdad lento. No hay Google para una respuesta tampoco. Finalmente, en mi opinión (irrelevante), esto tiene la ventaja adicional de hacer que el desafío sea más divertido.

Algo como encontrar una cadena dentro de otra cadena es más fácil de ser malo que bueno. Tal vez haga que extraen todos los números primos de una cadena de 2kb de caracteres alfanuméricos aleatorios. Muchas maneras de hacer la oreja de un cerdo de ese problema.

Answer 2

Acordó "muchas veces" para operaciones cortas, pero para las más largas, una vez podría ser suficiente por sí solo.

Sugiero investigar Proyecto Euler, una excelente colección de preguntas de programación. La mejor parte es que los problemas están diseñados con una "regla de un minuto" en mente, que la mayoría de los problemas deberían tomar una computadora moderada menos de un minuto para ejecutar una eficiente algoritmo para encontrar las respuestas. Así que un excelente lugar para comenzar. :)

Answer 3

Dos cosas.

Primero, la eficiencia es más que el tiempo de ejecución. También se trata del uso de la memoria, el acceso a la memoria, el sistema del sistema de archivos/el acceso a los recursos, etc. Hay toneladas de cosas que tienen la eficiencia. Así que sea explícito que está buscando la rutina con el tiempo de ejecución más corto. De lo contrario, está enviando un mensaje mixto ...

En segundo lugar, escuché este problema hace unos 15 años, y no puedo olvidarlo:

Producir una lista de todos los pares de números de 5 dígitos que suma 121212. Sin embargo, ninguno de los 2 números puede repetir un dígito decimal. Asi que 1 solo puede aparecer una vez en cualquiera de los números. Entonces un par de resultados de ejemplo es 98167 + 23045. Hay un número justo, y es fácil construir una solución de fuerza bruta, pero una solución eficiente requiere algo de pensamiento. Hay 192 pares únicos ...

Answer 4

Esas son buenas ideas. ¿Qué hay de tener una pregunta de clasificación?

Answer 5

Ordenar una variedad de números también puede ser una buena idea, ya que hay un montón de algoritmos para él (inserción, selección, rápido, montón, etc.) que tienen diferentes características de rendimiento. Esto también les daría a los estudiantes la oportunidad de aprender sobre la notación Big-O, etc.