homework3opz,consigli su come ottimizzare?

Question

vado in timeout in quasi tutti i test per 0.005/7 secondi,non riesco a capire se effettivamente è il tempo reale impiegato dai vari test oppure in qualche modo viene interrotto dopo 1s(il che spiegherebbe i risultati molto simili).In ogni caso non so come ottimizzare i tempi,utilizzo un solo ciclo per creare o aggiornare il dizionario,e poi un altro per convertirlo in lista di tuple da stampare.

p.s: per la questione dei tempi ho provato ad usare anche pytest test_01.py -v -rA --durations 0 ma niente...mi da gli stessi tempi.

Answer 1

Sì praticamente con i nuovi test appena il programma raggiunge 1 secondo di esecuzione, viene interrotto (per vedere il tempo di esecuzione reale puoi andare a modificare test_01.py riga 24 e 25, metti un valore grande).

Come consiglio, prova a restituire il valore una volta che hai finito di crearti il dizionario leggendo tutta la stringa (ovviamente tutti i test falliranno, ma serve a capire se la parte della lettura è fatta correttamente). Rientri nei tempi?
Se sì allora probabilmente rallenti nella generazione dell'output. Il mio consiglio è di partire dalla fine, e di fermarti una volta raggiunto il n.

Comments

partire dalla fine e fermarmi ad n intendi per dare come ouput le n tuple più grandi? perchè in questo caso io ho pensato che conviene non ordinare ma iterare n volte il dizionario disordinato e ad ogni iterazione usare una funzione per trovare il massimo,in tal modo mi ricavo la lista finale da ordinare che sarà sicuramente minore dell'intero dizionario e quindi dovrei metterci meno tempo,ma è una mia supposizione,non so se sia corretta,grazie comunque della risposta.

---

partire dalla fine e fermarmi ad n intendi per dare come ouput le n tuple più grandi?

Sì, partire ossia generare prima quelle più frequenti.

Non credo iterare troppe volte sul dizionario sia una buona idea. Inoltre ricordati di ordinare una sola volta per lista, fare troppi ordinamenti è costoso.

---

non riesco a capire in che modo potrei individuare le sottostringhe più frequenti...anche perchè i metodi basilari come count non contano le sovrapposizioni e farebbero sballare tutto.

per quanto riguarda le iterazioni sulle liste,non ne faccio,le ordino e basta(con sorted)

---

ovviamente intendo individuarle prima di iterare così da poter generare il dizionario solo con quelle più frequenti come dici tu

---

Devi cercarti tutte le sottostringhe di quella lunghezza, e contarle. Per fare questo ti consiglio un dizionario.

---

oddio in che senso? io creo il dizionario iterando su slice della stringa quindi il dizionario lo creo solo con sottostringhe di giusta lunghezza,non spreco iterazioni

---

Sìsì certo, questo è il procedimento corretto. Forse mi sono spiegato male io

Answer 2

Come detto da @Edward una delle ottimizzazioni da fare è sicuramente il fatto di smettere di ciclare sul dizionario una volta generate n tuple nel risultato, ma un'altra cosa importante è non leggere l'intero file.

Spero di non fare una gaffe azzardando questa supposizione sul tuo programma, ma... 
Se tutti i test ti vengono giusti ma vai in timeout immagino tu abbia letto l'intero file.
Cosa che ti permette sicuramente di fare un ciclo per i da 0 a alla lunghezza della stringa del file, e all'interno farne un altro per j da a a b in modo da fare uno slice a partire da i, fino a i+j.

Questo metodo per quanto chiaro e concettualmente funzionante ti costringe a creare delle stringhe enormi, la cui gestione (es: slice) in python è decisamente lenta.

---

Un metodo alternativo può essere leggere solo b caratteri invece di leggere tutta la stringa.
Tenendo un buffer di b caratteri, puoi fare un ciclo per j da a fino a b per fare uno slice poi da 0 a j, questo ti permette di trovare le sottosequenze (a-b) tagliando una sequenza di massimo b caratteri invece di farlo tagliando l'intera stringa.

Ma una volta trovate le sottosequenze della prima sequenza di b caratteri come vai avanti?
Semplicemente togli il primo carattere dal buffer e aggiungi un altro in coda letto dal file, e a quel punto fai di nuovo il ciclo.

Comments

Però come smetto di ciclare sul dizionario se non so quali sottostringhe sono le più ripetute? Cioè devo prendere le n sottostringhe più frequenti,quindi devo per forza creare tutto il dizionario e poi controllare quali siano più frequenti.

Io ciclo e prendo ogni volta pezzi di stringa che vanno da 0 ad "a" fino a che "a" non coincide con "b",a quel punto elimino il primo elemento della stringa e ripeto il ciclo finché la stringa originale non è più lunga di 1.
Non so se intendevi questo, sinceramente non ho ben capito

---

Elimini il primo elemento dalla stringa... ? intendi che elimini la prima sequenza lunga b dalla stringa?

Comunque il dizionario devi per forza crearlo tutto, quello che credo Edward intedesse era che quando poi converti il dizionario in una lista di tuple puoi fermarti appena generi la n-esima tupla.

Però se fai modifiche su una stringa di più di 100MB direi che il problema è quello...

---

Se non ho capito male intendi che fare le slices di stringhe molto grandi è molto più lento di fare le slices di stessa dimensione di una stringa più piccola?

---

Se non ho capito male intendi che fare le slices di stringhe molto grandi è molto più lento di fare le slices di stessa dimensione di una stringa più piccola?

EDIT:
Calcola che file di 100MB non ce ne sono, il json molto grande serve solo per generare gli input e gli expected.

Ho provato a creare una stringa da 10 miliardi di caratteri, che una volta salvata sul disco occupa 9GB, ed i tempi per farne le slices erano uguali di quella di una di 100 caratteri.

L'ho anche letta direttamente da file, ma il tempo si aggira sempre sui 63 ns (lì per la stringa più piccola il fatto che sia leggermente più lenta credo sia solo un caso...)

 lol

---

Dalla stringa del file elimino solo il primo elemento, cioè io prendo la slice che va da 0 ad "a",poi da 0 ad "a"+1 ecc finché questa "a" non diventa "b" a quel punto resetto "a" ed elimino dalla stringa il primo elemento e così via... È questo il problema?

Per quanto riguarda la conversione ci sono due.possibile casi,se n è maggiore di len(dizionario) o viceversa.Nel primo caso devo prenderlo tutto quindi semplicemente lo trasformo se invece è minore itero n volte e prendo ogni iterazione il massimo dal dizionario, così da non sprecare iterazioni anche qui.Dove sbaglio?

---

Ho provato a creare una stringa da 10 miliardi di caratteri, che una volta salvata sul disco occupa 9GB, ed i tempi per farne le slices erano uguali di quella di una di 100 caratteri

@Edward, wow, davvero interessante, in effetti se python a basso livello parte semplicemente dal puntatore della stringa + il valore di inizio dello slice il tempo che ci mette dovrebbe essere lo stesso...

In effetti ho appena provato a rifare il programma in entrambi i modi e... la differenza è poca anche su file di dimensioni notevoli.
(Resto comunque del parere che non sia una grande idea caricare interi file in memoria senza avere la minima idea di quanto possano essere grandi)

Arrivato a questo punto però non ho più idea di quale possa essere il motivo del timeout di @gian.uni (escludendo l'interruzione della la generazione della lista di tuple)