Miglioramento delle tempistiche

Question

Ho concluso oramai da ore l'hw2, nella prima stesura passavo 14 test su 16, dunque mettendomici ho riscritto un paio di volte il codice ed ottimizzato fin dove potevo, arrivando a passare 16 test su 16 nelle tempistiche previste.... sul mio pc.
Il tanto odiato test_1_esempio5 nul mio pc impiega tra i 1.47 e 1.49 secondi (facendo una stima), ma sulla vm non riesce ad avere un tempo decente. Non saprei più come ottimizzare il codice personalmente e so benissimo di non poterlo inviare dunque l'aiuto sarà limitato. Chi ha dei consigli sono ben accetti, molte cose le ho già attuate, ma chissà che altri non trovino utile questo post.

Answer 1

Molti di noi passano tutti i test sul nostro pc, ma sulla vm vanno un po' più lenti. Ma i professori hanno fissato il timeout in base alle tempistiche della vm. Se hai ottimizzato al massimo il codice, allora è probabilmente l'approccio che è da cambiare.

Una cosa sicuramente utile è cercare un modo per ridurre il numero di scambi che vengono fatti, e cercare di ridurre il numero di accessi effettuati a dizionari o liste (che di per se non hanno un grande costo, ma ripetuto per oltre un milione di volte si fa sentire).

Io come ha detto @gian- avevo usato un dizionario per matchare i piloti, e rendendolo il più efficiente possibile ero riuscito ad avere sui 1.48s per il test 5 (sulla vm). Quindi teoricamente è possibile usare quell'approccio, ma devi ridurre al minimo il numero di scambi che fai.

Comments

Mi trovo nella stessa situazione: 1,47s per il test 5, ottimizzando più che potevo quell'algoritmo. Alla fine hai cambiato completamente algoritmo o sei riuscito ad ottimizzare ancora?

---

Ho cambiato algoritmo

Answer 2

Immagino che tu abbia già usato i dizionari? Nel caso tu non l'abbia fatto te lo consiglio vivamente

Comments

Penso che fare questi tempi senza i dizionari sia impossibile

Answer 3

Io in locale passo tutti i test per 2 secondi, su q2a il 5 non me lo passa.

Comunque l’idea è quella di creare un dizionario che matcha ogni pilota con quello dietro e con quello davanti, e conviene usare una lista per farlo.

Il problema è che quando c’è un sorpasso in quanto bisogna fare almeno 4 modifiche al dizionario.. il che rallenta di molto a quanto pare

Comments

Il mio algoritmo si basa sullo stesso identico concetto
Non metto in mezzo la questione dell'ordinamento finale perchè in quel test vanno ordinati solo 10 elementi dunque il tempo è insignificante (a meno che ovviamente non si scrivano cose senza senso)

---

Si sta tutto nei sorpassi, almeno per me

---

Ho usato il codice che sta nei test per capire quanti eventi ci fossero tra sorpassi e ritiri e sono più di 1 milione

---

Sul mio PC termino tutti i test in meno di un secondo. Il tempo di esecuzione della funzione per test_1_esempio5 è di appena 650 millisecondi. Tanto per darvi un'idea, la parte di creazione delle liste per il test in questione ci impiega circa 300ms (quindi fuori dall'algoritmo).

Sulla VM lo stesso test sfora il secondo e mezzo...

Ho qualche dubbio circa le performance della VM...forse è sovraccarica.

---

No, hai un PC figo