Cerchi buon bonus quiz per l'efficienza di prova (in particolare l'efficienza legati alla volta) [chiusa]

Question

sto facendo un laboratorio introduttivo di informatica volta alla settimana. Speravo di avere un rapido concorso alla fine del mio prossimo laboratorio. Voglio dare loro un blocco di codice come questo:

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

}

Saranno implementare il metodo doSomething e la persona con il codice più veloce otterrà una manciata di marchi bonus.

Il problema è che la questione deve essere un po 'semplice. Gli studenti hanno una buona conoscenza di: loop, if / else, Strumenti ad arco, aggiungendo, array, ecc

Ecco le mie idee per quello che la domanda potrebbe essere:

• trovare tutti i numeri perfetti tra 1 e 1.000.000. (Un numero perfetto è un numero in cui tutti i fattori del numero aggiungere fino al numero Ie:. 6 = 3 + 2 + 1)
• trovare tutti i numeri primi compresi tra 1 e 1.000.000

Credo che perché vi sia una differenza misurabile in termini di prestazioni tra i metodi si deve fare qualcosa molte volte.

Answer 1

Poiché questa è una classe introduttiva e gli studenti non hanno coperto l'ordinamento ancora penso che sarà molto difficile trovare qualcosa abbastanza semplice da fare, abbastanza interessante per avere un paio di modi diversi di farlo, e complesso basta che v'è una notevole differenza di velocità tra le diverse implementazioni su un computer moderno. Il vostro vero problema, però, è che abbastanza nulla semplice per loro di provare già dispone di un'implementazione canonica solo una breve ricerca di Google distanza.

Il mio suggerimento è quello di invertire la sfida. Hanno i vostri studenti a gara per venire con la gnarliest, più lento, più soluzione hogging di memoria si può pensare di. Credo che sia come didatticamente prezioso per pensare a tutti i modi sbagliati di fare qualcosa in quanto è di pensare a destra, ed è altrettanto difficile da essere il peggiore in quanto è di essere il migliore. E 'più facile vedere i risultati soggettivamente e dal cattivo codice sarà davvero lento. Non usare Google per una risposta sia. Infine, a mio parere (irrilevante), questo ha il vantaggio di rendere la sfida più divertente.

Qualcosa come trovare una stringa all'interno di un'altra stringa è più facile fatta male che bene. Forse li hanno estrarre tutti i numeri primi da una stringa di caratteri alfanumerici 2kb casuali. Un sacco di modi per fare l'orecchio di un maiale di quel problema.

Answer 2

D'accordo su '' molte volte per le operazioni a breve, ma per quelle più lunghe, una volta potrebbe essere sufficiente di per sé.

Suggerisco alla ricerca in Project Euler , una straordinaria collezione di programmazione di domande. La parte migliore è che i problemi sono stati progettati con un "governo di un solo minuto" in mente, che la maggior parte dei problemi dovrebbero prendere un computer moderata meno di un minuto per eseguire un efficace algoritmo per trovare le risposte. Quindi, un ottimo posto per iniziare. :)

Answer 3

Due cose.

In primo luogo, l'efficienza è di circa più di tempo di esecuzione. Si tratta anche di utilizzo della memoria, accesso alla memoria, file system / accesso alle risorse, ecc Ci sono tonnellate di cose che vanno in efficienza. Quindi, per favore essere espliciti che stai cercando per la routine con il più breve fase di esecuzione. In caso contrario, si sta inviando un messaggio misto ...

In secondo luogo, ho sentito questo problema circa 15 anni fa, e non posso dimenticare:

Produrre un elenco di tutte le coppie di numeri a 5 cifre che somma 121212. Tuttavia, nessuno dei 2 numeri può ripetere una cifra decimale. Così 1 può apparire solo una volta in entrambe le serie. Quindi un risultato esempio coppia è 98167 + 23045. Ci sono un buon numero, ed è facile per creare una soluzione di forza bruta, ma una soluzione efficiente richiede una riflessione. Ci sono 192 coppie uniche ...

Answer 4

Queste sono le buone idee. Cosa ne dite di una domanda di smistamento?

Answer 5

Ordinamento di un array di numeri potrebbe anche essere una buona idea, in quanto ci sono un sacco di algoritmi per esso (inserimento, selezione, rapida, mucchio, etc.) che tutti hanno differenti caratteristiche di prestazione. Ciò consentirebbe anche di dare agli studenti la possibilità di conoscere la notazione O-grande, ecc.