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

Do you need help?

Problema di efficienza HW3opt

g
giac (2790 points)
10 14 27
in HW3 opzionale by (2.8k points)
edited by
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?
370 views
closed

1 Answer

Best answer
Exyss (21510 points)
1 2 79
by (21.5k points)
selected by

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)
10 14 27
by (2.8k 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 (21510 points)
1 2 79
by (21.5k 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)
10 14 27
by (2.8k 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 (21510 points)
1 2 79
by (21.5k 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)
10 14 27
by (2.8k 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 (21510 points)
1 2 79
by (21.5k 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)
10 14 27
by (2.8k 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