Velocizzare algoritmo

Question

Buongiorno, ho sviluppato un codice che funziona abbastanza bene, nel senso che il risultato è sempre quello che ci si aspetta, ma essendo un pò lento, non passo gli ultimi 2 tests!!!

Avete qualche consiglio su come renderlo più veloce??

Pensavo di sfoltire la lista dove pesco i vari caratteri quando una parola è più corta dell'indice che stiamo scandendo per il risultato, ma senza riuscirci...

Grazie

Answer 1

• Usa .split() quando leggi il file, ti divide direttamente il contenuto della stringa in una lista, prendendo di default come separatore qualsiasi "spazio" (sia \n, che \t, che " ")
• Se operi su un dizionario/lista, al posto di controllare ogni volta che un indice o una chiave siano presenti, usa try ed except (KeyError ed IndexError), in questo modo ti eviti il controllo e risparmi tempo. 

Comments

Allora prima di tutto ci tengo a precisare che ho replicato solo per far discussione formativa e con nessun intento d'affronto, chiarito questo, un pensiero d'impulso, senza fare molti calcoli, che mi ha portato a pensare che ti sbagli (su come calcoli la complissità) è questo:

- Nei risultati che esponi i tuoi 3 algoritmi la proporzione tra quello "vecchio" e quello chiamato "KinderBueno" e circa 1,22, quindi, dato che il tuo vecchio algoritmo faceva 1700 sulla VM, quello che chiami "Kinder_Bueno" gira a circa 1700/1.22= 1310 più o meno. Dal momento che il mio algoritmo (che non conta le freq) ha stessi tempi, fa più o meno le stesse operazioni. 

- L'algoritmo che ho implementato che conta le frequenze ha tempi sulla VM di circa 986, quindi anche questo, più o meno stesse operazioni del tuo (non faccio uso nemmeno io di set{} come funzione).

- Il test_12 con l'algoritmo che non conta le frequenze sul mio pc impiega 815ms 

- Il test_12 con l'algoritmo che conta impiega circa 1000ms

Quindi è un aumento di più del 20% (che non è per niente in linea con lo 0,0005% di cui parli, e non è nemmeno il caso peggiore perchè il test ha circa il 50% delle parole che si ripetono), il risparmio si ha nei 3 test precedenti, e questo nel totale ha un'efficienza di circa 300ms.

Ora la domanda che voglio farti è: quanto tempo impiega "Kinder_Bueno" e quanto "Ferrero" solo nel test_12 ? Penso, senza sapere la risposta, che la differenza è maggiore dello 0,0005%. 

Ora o abbiamo implementato entrambi due algoritmi (1300 e 986) che per pura casualità hanno stessi tempi e fanno un numero differente di operazioni oppure il tuo calcolo della complessità è sbagliato. Fatto sta che sulla base del test_12 dai due miei algoritmi noto chiaramente una differenza di circa il 20% e non 0,0005%. 

Potresti mostrare solo i risultati del test_12 e mostrami che il tuo 0,0005% ha effettivamente senso? 

Ps: ripeto mi piace la discussione formativa, spero non prendi questo con aria di sfida perchè non è mio intento; anzi vorrei capire che mi sto sbagliando e quindi ricarico quello da 986 che ero pure primo nella leaderboard ;)

---

Il test_12 mi da come risultati:

[0.492798599996604] # Bueno, senza conteggio ripetizione
[0.38982050004415214] # Ferrero, con conteggio ripetizione

Quindi, quello che conta le ripetizioni è del 20% più veloce. Sul test_13/big.txt:

[3.016636500018649] # Bueno
[2.8116568999830633] # Ferrero

Sono molto simili, sarà un'errore della macchina, anche perché quello che conta le frequenze risulta più veloce. Se nella funzione .repeat() uso i parametri .repeat(1, 10) per il test_12

[4.584084799978882] # Bueno
[3.3964527000207454] # Ferrero

Il 25% più veloce quello che conta le ripetizioni.

Ho corretto quel 0,0005% che era frutto di un calcolo errato, sarebbe 0,5% a livello teorico (in un caso in cui tutte le parole sono distinte, quindi non si può applicare al test_12, caso in cui quello che conta le frequenze è più veloce del 20%, perché le parole univoche sono poche rispetto a quelle totali).

Devo annotare che "Bueno" non l'ho provato sulla VM, ma è più ottimizzato rispetto a quello di 1700 dell'8-10% circa (quindi posso ipotizzare che sulla VM faccia 1530...?), e non conta le frequenze.

Molto probabilmente, le nostre differenze nei risultati dipendono dall'implementazione, quindi, finché aspettiamo il termine di consegna dell'HW, andiamo a ipotesi  Se hai fatto il mio stesso tempo sulla VM, hai invertito i risultati dei due algoritmi nel test_12 nel commento precedente (quindi quello che conta le frequenze è del 20% più veloce anche nel tuo caso) altrimenti non faresti 986.

---

Devo fare un piccola rettifica. Allore il risultato dello 0,0005% hai capito pure tu che è errato. Comunque io non ho invertito i risultati nel mio commento erano proprio quelli. Però ho capito che non avevo implementato correttamente l'idea (anche se ho fatto 986), ora ho capito dove era l'errore e posso affermare che hai ragione (non so però se esattamente lo 0,5%). Faceva 986 ma eseguiva passaggi inutili e nell'ultimo test era del 20-25% più lento. Ora l'ho migliorato l'ho appena caricato sulla VM. Attendo conferma.

Comunque grazie, discussione molto formativa ;)

---

Grazie a te! Se fai meno di me so che il mio si può ancora migliorare , comunque ho scritto un sacco di materiale che sto riusando per l'algorithm.txt. 

---

Ho notato solo ora queste risposte...
Il motivo per cui consigliavo di usare try except era principalmente per le liste. In un contesto differente dove un codice pulito ha un peso maggiore rispetto ad un codice veloce, probabilmente sarebbe meglio fare un controllo sugli indici e verificare l'esistenza dell'indice, ma nel contesto attuale dove l'obiettivo è realizzare un algoritmo veloce, beh, il try..except fa il suo.

Fa il suo perché evita di fare un controllo ogni volta che bisogna operare su una lista, controllo che nella gran parte dei casi ci è superfluo dal momento che una volta che abbiamo inserito dentro la lista un dizionario, l'indice è creato. Se ora andiamo a controllare l'esistenza dell'indice ogni volta che operiamo sul dizionario, vuol dire che eseguiamo un'operazione superflua tante volte quanti sono i caratteri contenuti  in ogni lettera. Col try..except questo non succede.

L'ho consigliato anche per i dizionari perché l'operazione che si vuol fare nell'homework prevede l'accesso sia alla lista che al dizionario, quindi tanto valeva usare un except anche per il dizionario.

Non so precisamente quanto possa beneficiare l'utilizzo dell'approccio try..except sui dizionari, ma di sicuro i suoi vantaggi maggiori si vedono sulle liste.

Answer 2

Ti consiglio le list comprehension in primo luogo.

Dopodichè prova a controllare se la lunghezza della parola è più grande della parola e uguale all'indice che stai scandendo per poter lavorare solo su quelle invece che scandirle tutte

Answer 3

se con 'Pensavo di sfoltire la lista dove pesco i vari caratteri quando una parola è più corta dell'indice che stiamo scandendo per il risultato, ma senza riuscirci...' intendi "pescare" i caratteri dal file puoi benissimo usare .split()