Do you need any help?

Notice Board

Per partecipare al corso di Fondamenti di programmazione 2021-22 loggatevi e attivatelo nella vostra pagina dei corsi preferiti. A quel punto il corso appare nel menù personale cliccando sul proprio avatar. Per i materiali degli anni precedenti seguite lo stesso metodo.

To join the Programming/Lab 2021-22 course, log-on and select it on the my courses page. It will appear on the personal menu of your avatar. For earlier years use the same method.

VIDEOLEZIONI DEL CORSO DI FONDAMENTI DI PROGRAMMAZIONE AA20-21

PROGRAMMING COURSE VIDEOCONFERENCES AY20-21

Problema di efficienza HW3opt

g
giac (2790 points)
7 14 27
asked Nov 6, 2021 in HW3 opzionale by giac (2,790 points)
edited Nov 6, 2021 by giac
Ciao a tutti, lavorando al HW3opt ho un importante problema di efficienza. Con la profilazione, ho notato che è un problema legato alla lentezza nel percorrere la sequenza per individuare le sottosequenze di lunghezza compresa tra a e b.

Con la mia poca esperienza, non vedo altro modo per fare ciò se non usare un ciclo for e un ciclo while annidato che mi diano gli indici con cui, grazie allo slicing, seleziono le sottosequenze di lunghezza valida e le uso come chiavi di un dizionario contatore (spero di essermi spiegato).

La mia domanda è proprio questa: già in altre occasioni ho notato che cicli annidati aumentano considerevolmente il costo computazionale, ma quando bisogna scandagliare un alto numero di sottosequenze di una sequenza (che sia lista o stringa ecc.) non vedo altro modo che ricorrere ai cicli per individuare gli indici (ho avuto un problema simile con HW1opt); c'è un modo per sostiuire in modo più efficiente i doppi cicli? Oppure il problema è lavorare con lo slicing? O ancora, esistono delle modalità più snelle di manipolazione delle sequenze che non conosco? Filter può essere di aiuto?

1 Answer

Best answer
Exyss (21390 points)
1 2 79
answered Nov 6, 2021 by Exyss (21,390 points)
selected Nov 8, 2021 by giac

Probabilmente la lentezza è dovuta alle operazioni che avvengono nei for annidati e non ai for stessi, anche perchè il ragionamento che hai effettuato è giusto (o almeno, nel mio caso ho fatto una cosa molto simile e il tempo d'efficienza è molto basso). Sicuro di aver snellito al massimo quello che avviene dentro i due cicli?

g
giac (2790 points)
7 14 27
commented Nov 6, 2021 by giac (2,790 points)
effettivamente la maggior parte del tempo è occupata da ciò che succede dentro il ciclo, dove semplicemente aggiorno il contatore di frequenze (dizionario) con il modulo .get; ma comunque sono obbligato a scorrere tutte le possibili sottosequenze e contarne la frequenza per poter restituire le n massime frequenze alla fine, o sbaglio?

(ho provato sia con due cicli for, che con un ciclo for e uno while, ma cambia poco)
Exyss (21390 points)
1 2 79
commented Nov 6, 2021 by Exyss (21,390 points)
Perche .get(chiave) ? Non puoi semplicemente incrementare utilizzando dizionario[chiave] += 1 ?
Comunque si in un modo o nell'altro devi scorrere tutte le sottofrequenze contando quante volte capitino.
g
giac (2790 points)
7 14 27
commented Nov 6, 2021 by giac (2,790 points)
dizionario[sequenza[x:y]] = dizionario.get(sequenza[x:y], 0) + 1

perché se incontro per la prima volta una sottosequenza non posso aumentare il valore se la chiave ancora non esiste. insomma uso il get al posto dell'if che controlla se la chiave è già nel dizionario. in linea teorica dovrebbe essere più veloce col get, ma posso provare nell'altro modo
Exyss (21390 points)
1 2 79
commented Nov 6, 2021 by Exyss (21,390 points)
Non so quale dei due casi sia più veloce, ma puoi anche usare un semplice if che controlli se la chiave esista o no
g
giac (2790 points)
7 14 27
commented Nov 6, 2021 by giac (2,790 points)
ho provato a cambiare il get con un if e +=1 del contatore, ma niente. dal test 1600 va in timeout.

ho il dubbio che forse con i cicli faccio troppo: il primo ciclo (indice x) lo mando da zero a (len(sequenza)-a+1), il ciclo while (indice y) lo faccio con le condizioni che la lunghezza sia tra a e b e che y non "sbordi" oltre la fine della sequenza. in poche parole, il risultato esce, ma eccessivamente lentamente. non so bene che pesci pigliare, anche perché non mi sembra di star facendo cose cosi astruse che debbano essere semplificate e velocizzate. forse il secondo ciclo potrebbe essere più "smart", ma non so come
Exyss (21390 points)
1 2 79
commented Nov 6, 2021 by Exyss (21,390 points)
Forse il problema è altrove. Nel profiler ti da che i cicli for occupano la maggior parte dell'esecuzione proprio perchè è la parte centrale del programma, dunque ovviamente "la più lenta". Hai già provato a snelline ciò che è al di fuori dei due cicli? Ad esempio il modo in cui viene calcolata la lista finale delle frequenze
g
giac (2790 points)
7 14 27
commented Nov 8, 2021 by giac (2,790 points)
grazie, avevi ragione! in effetti nei cicli c'era poco da migliorare. ho tagliuzzato un po il processo di lista finale e voilà! grazie :D