HW4REC consigli?

Question

Buongiorno a tutti,

ormai è da mesi che cerco un modo  per velocizzare di molto il mio programma ma nulla da fare. Ho scritto più algoritmi diversi ma continuo a passare solo 4 test e i restanti vanno in Timeout. Oggi ne ho scritto un altro più veloce  ma ancora non abbastanza da superare i test. A questo punto credo che il problema sia il confronto tra le parole (controllo lettera per lettera) ma non mi vengono metodi più efficaci per farlo ( dato che non si possono usare gli insiemi al posto delle liste vista la ripetizione di alcune lettere nella stessa parola).

Spero che qualcuno possa "illuminarmi".

Grazie mille in anticipo per la disponibilità

Answer 1

Abbiamo affrontato un problema analogo qui: https://q2a.di.uniroma1.it/16619/timeout-in-vari-esercizi

Personalmente il consiglio che ti do è lo stesso, utilizza il profiler per capire dove sono i problemi.

Una cosa che faccio spesso quando mi impantano sulle funzioncine consiste nel implementarne qualcuna che logicamente sembra appropriata,

Poi testo (anche separatamente) solo quelle in un for che si ripetete [inserire numero molto molto maggiore rispetto al numero reale di chiamate] volte, questo simula la chiamata della funzione all'interno del più tosto dei test e mi permette di concentrarmi solo sul confronto tra quelle implementazioni, tanto se una funzione ci mette svariati secondi a completare il test non c'è motivo di provare ad ottimizzare le altre...

In pratica perdi un po' di tempo a costruire un banchetto di prova, che ti mostra la differenza (anche di interi ordini di grandezza) tra due funzioni che, all'apparenza, sembrano simili e ti toglie ogni dubbio su quale delle due sia più appropriata, e a tua volta vai in loop ad apportare piccole modifiche, testare, eliminare le peggiori, ottimizzare le migliori, finchè non arriva il momento di gioia in cui i secondi diventano ms/ns, a quel punto sostituisci la nuova funzione alla vecchia e vedi se qualcosa prende fuoco.

(Detto ciò non fucilatemi, la buona riuscita di questo esperimento dipende dalla funzione presa in considerazione e da quanto gli input del test sono simili a quello dell'esperimento, ovviamente non conviene andare a tentativi con gli algoritmi di sorting o quando abbiamo metodi più accurati)

Feature bonus: se hai una funzione lenta ma corretta puoi confrontare il risultato con quello di una nuova e (quantomeno per gli input testati) deleghi il lavoro di controllare la correttezza dell'output alla vecchia funzione  :D

Spero di essere stato chiaro e d'aiuto