HW2 - ES3 - Tempi di esecuzione eccezionali!!!

Question

Ciao a tutti,
ho appena concluso il 3° esercizio dell'HW con un tempo che giudicavo molto molto basso... Sono andato a vedere la classifica e non ho potuto fare a meno di notare che ci sono colleghi che superano tutti i test in circa 0.2s, circa un terzo del mio tempo... Come diavolo fate? Io ho una sola riga di codice che accresce vertiginosamente il mio tempo (da sola prende circa 250ms su mp3.txt), non saprei proprio dove migliorare...
Che malefiche strategie avete adottato? Condividereste qualcuno dei vostri oscuri segreti con Noi, 'sti giovenotti de' 'sta Roma bella?

Answer 1

Eh, se magari ci dici come hai proceduto tu possiamo darti qualche spunto...

Io ti dico che ho utilizzato subito un dizionario: diz[x] = y, molto veloce. E tu mi dirai, ma nel caso in cui a una x corrispondano più di una y?
Eheh, se guardi i grafici, per il primo robottino ti basta la y più piccola, mentre per quello di sotto quella più grande, così approssimi il grafico a quello strettamente necessario, dato che i punti non possono essere sul bordo.

Comments

Tutta l'elaborazione dei dati, dal file txt alla determinazione dell'area in cui verificare la presenza dei punti, impiega un tempo trascurabile... Roba come 0.003s o giù di lì...
Come ho detto, ho un'unica Istruzione che da sola impiega 250ms in mp3.txt... E questa sfrutta l'utilizzo di Matplotlab...
Come avete risolto diversamente?

---

Non so cosa sia matplotlab, ho risolto con un dizionario in cui salvo le coordinate del primo percorso e poi un altro in cui salvo quelle del secondo

---

Certo, quello anche io... E alla fine ho a disposizione un dizionario con i punti di entrambi, in modo da avere l'intero percorso e quindi l'area delimitata... E' il controllo di inclusione di un punto che mi ci mette tanto.

---

@Auron Sei sicuro di avere bisogno di una libreria esterna per il controllo dell'inclusione con due grafici così semplici? Una volta che li hai entrambi preso un qualsiasi punto (x, y) ricavi le y corrispondenti dei due grafici e controlli se la x del punto si trova fra di loro

---

Grazie per la risposta Xriuk... Ci ho provato come prima ipotesi... Ma superavo tutti e 4 i test in 37 secondi sul mio pc che è molto veloce 
Ora ci metto 560ms per superarne 13 sulla VM :)
Non sono sicuro di aver bisogno di una libreria apposita, ma non sono riuscito a trovare un modo agevole per farlo in maniera iterativa...

---

Oppure ricavi la x e controlli la y. È uguale, dipende da come hai salvato i dizionark

---

Si si ovvio... Ma non è il concetto che mi sfugge, è il modo in cui costruire un algoritmo simile che sia veloce, perchè a costruirlo l'avevo costruito e mi sembrava anche molto semplice... Solo che era lento da morire...

---

Strano. Devi solo scorrere le coordinate che ti chiedono e vedere che la x (o la y) sia compresa tra le x (o le y) dei robottini, a parità di y (o di x)

---

Io arrivo alla fine con un dizionario di tuple, questo vorrebbe dire fare un ciclo per scorrere i punti da verificare e identificare tutte le tuple che hanno la x (per esempio) uguale a quella del punto cercato... Una volta fatto questo, tra le tuple che si sono trovate, va controllato se la y del punto è compresa tra il minimo e il massimo delle y presenti nelle tuple stesse...
Mi viene obbligatorio un ciclo annidato... Ho provato ad usare anche any, con lambda, ma il risultato sono stati quei 37 Secondi di "efficienza" :(

---

Cambia il dizionario, non di tuple ma di coordinate

---

Quindi, per esempio, se il mio Dizionario è: {(1,1), (1,6), (1,8), (2,1), (2,3), (6,3), (6,5)} renderlo qualcosa del tipo: {1:[1,6,8], 2:[1,3], 6:[3,5]}?
Dove ovviamente la chiave è la x e il valore la lista delle y correlate a quella x?

---

Una cosa del genere, ma con un solo valore, non lista di valori

---

@Auron, se ho capito tu hai un dizionario di tuple (per ogni robottino?) con tutti i punti? Io ti dico che ho utilizzato subito un dizionario: diz[x] = y, molto veloce. E tu mi dirai, ma nel caso in cui a una x corrispondano più di una y?
Eheh, se guardi i grafici, per il primo robottino ti basta la y più piccola, mentre per quello di sotto quella più grande, così approssimi il grafico a quello strettamente necessario, dato che i punti non possono essere sul bordo.

Questa è una chicca personale ;)

---

Dovevi lasciare che ci arrivasse da solo

---

@Xriuk Non esattamente, io ho un dizionario di tuple, con i soli vertici della parte di figura che interessa il percorso di ogni robottino...
Esempio... Il mio percorso è [2,2,-2], partendo da (1,1) io avrò {(1,1), (1,5), (3,5)} e non {(1,1),  (1,3), (1,5), (3,5)}...
Comunque ho capito la tua "chicca", appena ho un minuto per poter incollare le dita alla tastiera faccio qualche tentativo :)
Grazie mille per il supporto, che vada bene o male ahahah
BA per te :D

Answer 2

che metodo usi tu e quanto ci metti in totale?

Comments

Tutti i test, qui sulla VM, impiegano circa 550/560ms di media... Per il procedimento, ho risposto a Xriuk sotto :)

---

Vabbè dai 500 non sono mica tanti. Non bastano per il bonus? O sei tu che punti proprio al top?

---

Io per natura punto al Top ahahah
Poi c'è il discorso Bonus che sicuramente pesa, visto che è l'unico dei 6 che non riuscirei a prendere di questo Hw...
Però ero anche curioso di sapere come era stato progettato l'algoritmo per renderlo ancora più veloce (so che 500 non è tanto :P).
Tu che tempo avevi?

---

Io faccio meno di 400ms

---

Beh, ottimo :D