Timeout in vari esercizi

f
fpoldi (210 points)
0 1 3
asked Jun 18, 2020 in Recupero HW2 by fpoldi (210 points)
Buona sera a tutti.
Ho problemi di timeout in vari HW e vorrei un consiglio per superarli.
Nell'HW2rec, ad esempio, a volte non supero 1 test per 0,016 sec, in altri tentativi i timeout sono 2, più o meno sempre per lo stesso tempo.
Premetto di aver letto vari commenti che però non hanno portato alcuna variazione.
Uso i set  e scandisco le liste una sola volta. Non le confronto con tutte le precedenti ma solo con 2 valori int che aggiorno di volta in volta, secondo i massimi.
Pensavo fosse un algoritmo decente ma non riesco a togliere tempo nonostante avessi sconvolto il codice molte volte.
Grazie a chiunque mi possa aiutare.
Francesco
308 views

4 Answers

EffeGi (1530 points)
0 1 5
answered Jun 18, 2020 by EffeGi (1,530 points)
Ciao, l'idea che hai implementato è la stessa che ho utilizzato io e sono riuscito a passare i test senza problemi, probabilmente c'è qualche parte di codice che può essere ottimizzata ulteriormente.

Quello che ho fatto io è stato di portarmi dietro un primo massimo ed un secondo massimo, in modo da poter confrontare i nuovi elementi con quelli delle varie stringhe. Quindi è molto simile, inoltre ho utilizzato un dizionario per effettuare le operazioni di controllo con i vari massimi... puoi entrare più nel dettaglio? Con pseudo codice o descrizione più dettagliata?

Grazie
f
fpoldi (210 points)
0 1 3
commented Jun 18, 2020 by fpoldi (210 points)
Grazie per la risposta così celere.
Ho organizzato l'algoritmo con la creazione di un insieme dalla lista suddivisa sulle virgole.
Dal set ho preso ogni intero e l'ho inserito in una lista (con la list comprehension) e nello stesso ciclo ho individuato i due massimi che ho confrontato con i 2 massimi "assoluti" che mi sono portato dietro.
Ho effettuato la ricerca dei massimi in modi diversi per migliorare le prestazioni: con un max generale, con max su delle slice di 100, 300, 500, oppure Scandendo ogni elemento. In ogni caso la differenza è poca cosa.
Grazie di nuovo.
F.
andrea.sterbini (172780 points)
513 935 1789
answered Jun 18, 2020 by andrea.sterbini (172,780 points)
Notate che il sistema mostra un tempo di esecuzione appena superiore al timeout, senza mostrare quanto tempo in totale l'esecuzione avrebbe impiegato se non fosse stata fermata.
Per vedere i tempi veri (sul vostro PC) settate la variabile DEBUG=True in test_01.py
EffeGi (1530 points)
0 1 5
answered Jun 18, 2020 by EffeGi (1,530 points)
Se ho ben capito, prima viene creato un set dalla lista di stringhe e poi dal set viene creata di nuovo una lista.

Questo passaggio mi sembra superfluo, a te conviene lavorare con gli insiemi... quindi ti suggerirei di trasformare la lista di stringhe in un insieme di interi, poi prendere il primo e secondo massimo (in ogni set) con cui poter fare il controllo ad ogni iterazione, ovvero un check tra la riga in esame (che in realtà è un diventato un set) ed i max e min salvati (in un dizionario ad esempio) precedenti.

Per questo ti è sufficiente un ciclo for per fare il check su ogni stringa e un ciclo for interno per fare il check tra la stringa e tutti i precedenti max e min.

Di nulla!
f
fpoldi (210 points)
0 1 3
commented Jun 19, 2020 by fpoldi (210 points)
Scusa ma ho ancora lo stesso timeout 0,016.
Forse perchè per creare l'insieme di interi a partire dalla lista iniziale ho usato uno split sulle virgole?
Ma altrimenti avevo il problema di gestire il passaggio: un ciclo avrebbe preso ogni singolo carattere, virgole comprese).
Per il resto mi sembra di aver seguito i tuoi consigli.
Anche i controlli dei massimi sono molto veloci visto che non devo scandire tutto ma paragonare gli attuali con i 2 "assoluti".
EffeGi (1530 points)
0 1 5
commented Jun 19, 2020 by EffeGi (1,530 points)
Guarda anche io ho utilizzato lo split in una list comprehension per dividere le stringe in insiemi di interi.. Hai provato ad aumentare il tempo di timeout?

Perchè come ha ricordato il prof, il timeout segnato è leggeremente superiore al timeout impostato, anche se il programma avesse impiegato 100 secondi
f
fpoldi (210 points)
0 1 3
commented Jun 19, 2020 by fpoldi (210 points)
Infatti, settando debug = True vengono superati tutti i test.
Ho solo sprecato moooolto tempo.
Spero di non aver problemi con i test segreti.
Ti ringrazio di nuovo e ringrazio anche il prof.
andrea.sterbini (172780 points)
513 935 1789
commented Jun 20, 2020 by andrea.sterbini (172,780 points)
Mettendo DEBUG=True viene tolto il controllo del timeout, per  forza che li passi tutti!
Usa le opzioni di pytest per misurare le durate dei test.
- Gabbo (800 points)
1 2 7
answered Jun 24, 2020 by - Gabbo (800 points)

il Profiler è tuo amico.

C'era un hw che mi faceva impazzire, avevo una funzioncina che (se non erro) restituiva una lista di parole derivate da una parola in input, qualche riga che rimbalzavo da un tentativo all'altro perchè comunque mi serviva fare quel passaggio e sapevo che, a funzionare, funzionava... ma niente, non c'era verso di passare molti test a prescindere da come lavoravo l'output della funzioncina... finchè non ho scelto un test enorme,DEBUG=True, ed ho inziato a studiare i risultati:

 Mi sono reso conto che praticamente tutti i due secondi che impiegava li passavo dentro la funzioncina stupida, cacchio! avoja te a costruire programmi efficienti partendo da una funzione costosa...

Morale della favola ho cambiato modo di costruire le stringhe da mettere nella lista e lo stesso test ci metteva 1/3 di secondo :)

f
fpoldi (210 points)
0 1 3
commented Jun 25, 2020 by fpoldi (210 points)
Si ho notato anche io che il metodo di costruzione e soprattutto il "type" utilizzato per manipolare i dati sono fondamentali.
Ho finalmente trovato la soluzione.
andrea.sterbini (172780 points)
513 935 1789
commented Jun 25, 2020 by andrea.sterbini (172,780 points)
BENE!!!!!!                                  .
f
fpoldi (210 points)
0 1 3
commented Jul 5, 2020 by fpoldi (210 points)
Forse sarò recidivo ma anche per l'HW4rec e HW6rec ho problemi di timeout. Nel 6, in particolare, ho fatto una unica scansione dell'immagine mettendo in un dizionario colori/coordinate per poi tornare quanto chiesto. Ho provato a scandire "saltando" un paio di pixels ma senza grandi miglioramenti. Qualche suggerimento? Dove posso trovare soluzioni (video,  testi...) per gestire i timeout?
andrea.sterbini (172780 points)
513 935 1789
commented Jul 6, 2020 by andrea.sterbini (172,780 points)
Bisogna ragionare sull'algoritmo