Please ignore secret bonuses. Secret tests do NOT award bonus. Max hw grade is 30+2 bonus efficiency

Do you need help?

Consigli ottimizzazione es2 HW1bis

m
mel8 (1250 points)
1 12 19
in HW1bis by (1.3k points)
recategorized by
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
715 views
closed

1 Answer

Best answer
_andrea_ (45670 points)
11 42 297
by (45.7k points)
selected by
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
m
mel8 (1250 points)
1 12 19
by (1.3k points)
provo e faccio sapere
S
Stefano Urani (1940 points)
2 19 34
by (1.9k points)
io l'ho fatto così per curiosità, e ho notato che si creano delle ciclicità. Ogni tot di ripetizioni si ritorna alla lista di partenza. Non sono però riuscito a capire quale sia la formula che permette di calcolare ogni quanti cicli la lista si ripete. Credo dipenda più che dalla lunghezza della lista ls, dalle mosse: a volte certi valori non si spostano mai, altri si alternano tra due posizioni, quindi ogni numero ci metterà un certo numero di mosse a tornare al proprio posto. Invece che cercare di calcolare queste ricorrenze, basta verificare, ad ogni trasformazione della lista se questa è tornata uguale alla lista ls di partenza. Se sì basta prendere il resto n della divisione tra k e il numero di cicli fatti fino a quel momento e applicare un for per n volte sulla stringa di partenza.

Non so se sono stato chiaro, ma così passa tutti i test in 0,05s . Ovviamente ls non va modificata si lavora con due liste copiate da ls.
m
mel8 (1250 points)
1 12 19
by (1.3k points)
@Stefano Urani, non ho capito cosa intendi fare
_andrea_ (45670 points)
11 42 297
by (45.7k points)
Usando questo metodo si può ottimizzare ancora di più ma anche questo è già un buon modo. Volendo potresti applicare il riconoscimento di periodicità sul singolo elemento e non sulla lista intera, che sarebbe più veloce, ma anche sulla lista intera basta e avanza
m
mel8 (1250 points)
1 12 19
by (1.3k points)
scusate ma non vi sto capendo
S
Stefano Urani (1940 points)
2 19 34
by (1.9k points)
io l'ho fatto come l'hai fatto te @mel8, solo che all'interno del for che modifica la lista ho messo un if di controllo, se la lista modificata risulta uguale a quella di partenza inizia un nuovo for annidato, che rifà le stesse cose ma questa volta per n volte, dove n è il resto tra k e il il valore del loop a cui era arrivato, quindi modifica la lista allo stesso modo per n volte e poi interrompe il ciclo di for. Si usano due liste perchè ls ti serve che resti immutata per poterla confrontare con la lista che ottieni ad ogni for.

Mi dispiace di non riuscire a essere più chiaro..
_andrea_ (45670 points)
11 42 297
by (45.7k points)
Mel8 praticamente se tu applichi tante volte gli stessi movimenti, prima o poi probabilmente giungerai a un punto in cui i numeri si riposizionano nelle stesse posizioni iniziali. Usando questa proprietà puoi fare finta che ripeti tante volte quel ciclo ripetitivo e poi aggiungi le rotazioni che rimangono. Praticamente se tu hai 101 rotazioni da fare ma la lista dopo 10 volte torna uguale, tu puoi fare 101%10 e ti viene 1, a quel punto fai una sola rotazione e ottieni la lista finale perché tanto se ogni 10 si ripete, tu arrivi a 100 che l'hai fatto 10 volte e hai ottenuto comunque la stessa lista
S
Stefano Urani (1940 points)
2 19 34
by (1.9k 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)
2 19 34
by (1.9k points)
ecco si è così come dice Andrea
_andrea_ (45670 points)
11 42 297
by (45.7k 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)
1 12 19
by (1.3k points)
Ok ragazzi grazie mille, ora passo tutti i test in 0.21s. grazie mille ancora!!!
_andrea_ (45670 points)
11 42 297
by (45.7k points)
Ottimo, bene così