Consigli ottimizzazione es2 HW1bis

m
mel8 (1250 points)
0 12 19
asked Jan 2, 2019 in HW1bis by mel8 (1,250 points)
recategorized Jan 2, 2019 by mel8
Come potrei migliorare i tempi dell'es2? Io mi creo una lista contenente tutti 0 dove poi andrò a posizionare gli elementi nella giusta posizione secondo lmosse, poi faccio una copia della lista passata per non modificarla chiamandola lsTmp e poi faccio due for concatenati, nel primo itero per k volte, nel secondo itero per len(ls) e aggiungo il valore di lsTmp nella posizione i alla lista finale nella posizione di lmosse nella posizione di i(lsFin[lmosse[i]] = lsTmp[i]), dopo che si conclude il secondo for faccio una copia con copy() della lista finale in lsTmp e ripeto questo per k volte. Infine ritorno la lista corretta. Come posso ottimizzare? Mi passa 4 test su 8, il quinto non lo passa per 0.1 s.

Grazie in anticipo

1 Answer

Best answer
_andrea_ (45670 points)
2 39 297
answered Jan 2, 2019 by _andrea_ (45,670 points)
selected Jan 2, 2019 by mel8
Premetto che non sto facendo questo hw di recupero, però il secondo esercizio l'ho provato per curiosità e l'ho fatto come te, e anche a me andava in timeout. Ora ci stavo ripensando e mi è venuto in mente che forse invece di creare sempre la nuova lista, potresti fare sempre 2 for, ma invece di fare prima su k e poi su len, fai prima su len e poi su k. Dentro al secondo for dovresti fare una specie di "percorso" diciamo, nel senso che se ora hai il numero che sta in posizione 0, tu come lo fai adesso lo metti subito nella prossima posizione. Invece forse potresti ricavarti prima tutto il suo percorso e poi metterlo direttamente nell'ultima posizione fhe otterresti. Cioè se ora hai la posizione 0, e nella lista delle posizioni hai che in 0 c'è 3, tu dovresti metterlo in posizione 3. Ora però invece di metterlo, vai a vedere che posizione hai nella posizione 3 della lista posizioni. Facendo un esempio:
l=[1,2,3] p=[2,0,1]. Tu prendi l'1 e lo dovresti mettere in posizione 2 al primo giro. Al prossimo lo metti in posizione 1 e dopo in 0 e così via. Però col metodo che ho pensato tu devi fare così: sto in 0, lo 0 va in 2, poi il 2 va in 1, poi in 0, poi 2 e così via. Alla fine l'ultimo numero che ottieni è la posizione finale. Per ora però è tutto teorico perché non l'ho provato, ma ti farebbe risparmiare tutte le liste intermedie. Dimmi se riesci a farlo
S
Stefano Urani (1940 points)
0 16 34
commented Jan 2, 2019 by Stefano Urani (1,940 points)
è vero, ma risulta che la ciclicità su ogni lista è molto breve, si tratta ogni volta di 6, o 10 ecc cicli, quindi è già veramente molto veloce
S
Stefano Urani (1940 points)
0 16 34
commented Jan 2, 2019 by Stefano Urani (1,940 points)
ecco si è così come dice Andrea
_andrea_ (45670 points)
2 39 297
commented Jan 2, 2019 by _andrea_ (45,670 points)
Appunto quindi se hai una periodicità di 6 ti dovrebbe andare velocissimo usando questo modo. Per farlo controllando che dopo tutti gli spostamenti se la lista copia è uguale all'originale esci. Così sei sicuro che si interrompa quando sono uguali e poi applichi le rotazioni rimanenti
m
mel8 (1250 points)
0 12 19
commented Jan 2, 2019 by mel8 (1,250 points)
Ok ragazzi grazie mille, ora passo tutti i test in 0.21s. grazie mille ancora!!!
_andrea_ (45670 points)
2 39 297
commented Jan 2, 2019 by _andrea_ (45,670 points)
Ottimo, bene così