HW1bis - esercizio 2

f.cocci (650 points)
1 13 17
asked Feb 27, 2019 in HW1bis by f.cocci (650 points)
Salve a tutti, volevo qualche dritta su come ottimizzare le performance relativamente alla soluzione da me sviluppata per l'esercizio 2 dell' HW1 di recupero.

In pratica:

#inizializzo un contatore a 0

#creo na lista di appoggio uguale ad ls

#finche' il contatore e' minore dell'intero k:

 # inizializzo una variabilire risultato di tipo lista

 # in una range pari alla lunghezza della lista:

  #appendo al risultato l'elemento della lista di appoggio (inizialmente uguale a ls) il cui indice corrisponde all'indice estratto dalla lista lmosse per l'indice i del range di lmosse che stiamo scorrendo.

 #pongo appo uguale al risultato

#incremento il contatore.

Alla fine la funzione una volta arrivato a k-1 esce dal ciclo e ritorna il risultato che e' la lista dopo le k combinazioni.

Il codice funziona perfettamente solo che a partire dal 5 test becco il time-out e non so davvero come ottimizzare.

il problema penso sia ndovuto al fatto che l'operazione venga ripetuta per k volte e dal quinto test k e' davvero grande.

Sto provando a fare ragionamenti su ena eventuale periodicita' del risultato, infatti per la prima coppia di ls e lmosse in pratica a partire dal sesto tentativo che in pratica restituisce il risultato immutato per poi ricominciare a reiterare le stesse combinazioni da 1 a 5.

Grazie, F.
378 views

1 Answer

Best answer
_andrea_ (45670 points)
2 40 297
answered Feb 27, 2019 by _andrea_ (45,670 points)
selected Feb 27, 2019 by f.cocci
Si devi usare la periodicità. Se la lista si ripete dopo 10 volte, e tu devi farlo 1037 volte, ti basta farlo solo 7 volte per ottenere il vero risultato. Ovviamente in realtà devi farlo prima 10 volte (per capire che dopo 10 si ripete) e poi altre 7, quindi 17 in totale, che è diverso sicuramente da 1037. Ovviamente questo è un esempio ma se lo fai il programma ti gira anche il meno di mezzo secondo
f.cocci (650 points)
1 13 17
commented Feb 27, 2019 by f.cocci (650 points)
Perfetto, ero sicuro che da qualche parte si utilizzasse l'operazione di modulo :-)
A
AFulvio (220 points)
0 2 5
commented Feb 27, 2019 by AFulvio (220 points)

Vi mostro il mio pseudo-codice (a me sembra molto simile a quello riportato sopra) e volevo chiedervi se avevate un minuto per vedere dove sto sbagliando.

# faccio una copia della lista ls

# inizializzo un contatore

# creo una lista per il risultato formata da tutti 0 (con uno 0 per ogni elemento della lista)

# finchè il contatore è diverso da k itero le istruzioni successive:

    # per ogni indice della lista copia: (itero nel range della lunghezza della lista):

        # aggiungo l'elemento della lista copia (dell'indice corrente) nell'elemento del risultato che come indice ha il valore dell'elemento in lmosse con                                                                                                                                                                                                                                 indice corrente

    # copio la lista 'risultato' nella 'lista copia'

    # aumento il contatore

# ritorno la 'lista copia' (perchè ci ho trosferito la lista risultato nell'ultimo passaggio)

Il procedimento mi sembra molto simile ma al contrario di F.Cocci non mi passa nessun test... 

_andrea_ (45670 points)
2 40 297
commented Feb 27, 2019 by _andrea_ (45,670 points)
L'esempio nel testo ti viene?
A
AFulvio (220 points)
0 2 5
commented Feb 27, 2019 by AFulvio (220 points)

Si ho provato a farlo con il suo metodo ma niente neanche così (e sono tornato al mio codice iniziale). Comunque il mio metodo per farlo come lui è:

# faccio una copia della lista ls

# inizializzo un contatore

# creo una lista vuota per il risultato

# finchè il contatore è minore di k itero le istruzioni successive:

    # per ogni indice della lista copia: (itero nel range della lunghezza della lista):

        # appendo al risultato l'elemento di 'lista copia' nella posizione con valore uguale all'elemento corrente di lmosse

    # copio la lista 'risultato' nella 'lista copia'

    # aumento il contatore

# ritorno la lista risultato

(Ho cercato di riportare le stesse indentazioni)

_andrea_ (45670 points)
2 40 297
commented Feb 27, 2019 by _andrea_ (45,670 points)
No dico: se avvii l'esempio che sta nel testo, ottieni la lista giusta o una sbagliata? Perché se la sbagli potrebbe essere che hai interpretato male la parte in cui dice come devi ottenere la lista nuova da quella vecchia. Anche a me era successo ma la logica del programma era giusta
f.cocci (650 points)
1 13 17
commented Feb 28, 2019 by f.cocci (650 points)
Ciao @Afulvio, allora dopo un po di rivisitazioni e perfezionamenti, ti posso dire che non serve utilizzira una ls di appoggio. L'esercizio chiede che la lista ls non sia modificata, e questo vuol dire che non devi modificare il suo contenuto, ma puoi tranquillamente fare nuovi assegnamenti utilizzando come nome variabile sempre ls. questo non modifica il contenuto di ls in modo distruttivo, ma crea un nuovo oggetto con lo stesso nome. ti confermo che il grader non si arrabbia.

# scorro la lista lmosse per un intervallo da 0 alla lunghezza della lista lmosse-1 estraendo l'indice i.

 #per ciascun indice di lmosse estraggo la posizione dell' l'elemento in lmosse che corrisponde all'indice che sto scorrendo.

 #utilizzo questa posizione per estrarre l'emento corrispondente nella lista ls

 #appendo in una variabile risultato.

 #se il risultato non compare tra quelli gia visti me lo salvo in una lista visti

 #altrimenti alzo il flag a Y di una variabile stop

 #posngo ls uguale al risultato e ricomincio l'terazione sse il stop e' a N

#Un volta uscito da questo ciclo avro in visti un certo numero di liste risultato tante fino a che ha smesso di collezionarle perche' si e' verificata una ripetizione.

# ottengo il resto della divisione della valore k per la lunghezza di visti-1.

#la funzione ritorna la lista in visti che corrisponde all'indice pari al resto ella divisione.

Cosi facendo in pratica eviti di iterare i cicli per k volte il che inevitabilmente di porterebbe a fallire i test non appena k e' un numero grande.
A
AFulvio (220 points)
0 2 5
commented Feb 28, 2019 by AFulvio (220 points)

Chiaro il ragionamento, non ho capito cosa volessi intendere con queste due istruzioni:

#altrimenti alzo il flag a Y di una variabile stop

 #posngo ls uguale al risultato e ricomincio l'terazione sse il stop e' a N

 

f.cocci (650 points)
1 13 17
commented Feb 28, 2019 by f.cocci (650 points)
Finche il risultato generato e' una combinazione diversa di elementi (quindi la sequenza non e' presente tra quelle viste in precedenza) significa che deve continuare a fare il ciclo per generare altri risultati.

Nel momento in cui viene generata una sequenza gia vista, metto il alzo il flag delle variabile STOP e quindi smette di produrre nuovi risultati che da quel momente sarebbere periodici.

Il risultato diventa di volta in volta la tua nuova ls su cui generarne uno nuovo e cosi via.

Facendo un assegnamento non modifichi la lista ls, ma crei una nuova variabili di nome ls.

Alla fine cosi facendo il programma inpiega 0,3 secondi sulla mia macchina a fare tutti i test.
_andrea_ (45670 points)
2 40 297
commented Feb 28, 2019 by _andrea_ (45,670 points)
Non serve un insieme di sequenze, basta vedere se la lista nuova dopo le permutazioni è uguale a quella iniziale per sapere se si è arrivati alla periodicità
f.cocci (650 points)
1 13 17
commented Feb 28, 2019 by f.cocci (650 points)
si anche, perche tornando all'esempio si nota che dopo il sesto tentativo il risultato e' uguale a ls.

Sinceramente, ho visto che funzionava egregiamente e ho chiuso la.
A
AFulvio (220 points)
0 2 5
commented Feb 28, 2019 by AFulvio (220 points)

Scusami F.Cocci ma non capisco ancora un passaggio, una volta controllato se la lista generata è nella lista degli elementi visti, come faccio in caso contrario a continuare ad iterare per le restanti volte ? (Non capisco il passaggio in cui parli di Y, flag e N laugh)

_andrea_ (45670 points)
2 40 297
commented Feb 28, 2019 by _andrea_ (45,670 points)
Esegui gli scambi che rimangono da fare sapendo che dopo n volte la lista torna a posto. Se hai 99 scambi da fare e n=10, devi fare i restanti 9 scambi, che ottieni con modulo