Consigli velocizzare es2 HW02

Question

Passo tutti i test del 2° esercizio ma agli ultimi vado in timeout di 1s. Consigli su come velocizzare la funzione? Ho un dizionario contenente come chiavi tutte le parole e come valori ad ogni chiave la lista di tutte le tuple (occorrenze,id). Uso .count per le occorrenze. Inoltre ordinare tutte queste liste penso sia abbastanza dispendioso, e anche alla fine per contare in totale quante volte appare una parola uso un doppio ciclo che aumenta un contatore che tiene conto delle occorrenze delle singole tuple, sommandole.

Answer 1

Ti consiglio di non utilizzare il count in quanto troppo lento, scorreresti una lista di n valori n**2 volte. Ti consiglio di aggiornare un dizionario in cui tieni conto delle occorrenze aggiungendo 1 se trovi una parola presente nel tuo dizionario. Compi lo stesso lavoro ma n volte

Comments

Io lo faccio ma non mi capacito di come possa andare in timeout negli ultimi due test (solo sulla VM)

---

Hai detto di utilizzare .count, hai anche provando con un contatore come ti ho detto?

---

Non è meno dospendioso creare un dizionario nel quale come chiave usi l’identificativo del post (30 ad esempio) e associare ad ogni chiave tutte le parole presenti in quel post? In questo modo dovrebbe essere più facile effettuare i vari controlli o sbaglio?

---

È esattamente quello che faccio ma va in timeout

---

@alessio.palma

Penso che Gdn98 ti stia consigliando di non utilizzare il count per contare quante volte una parola è presente in un determinato post, ma di scorrere il testo e mano a mano che trovi una nuova parola incrementare il valore occorrenze in id. Ovvero, come valori delle parole nel dizionario, utilizza un altro dizionario che come chiavi gli id dei post dove trovi la parola, e come valori le occorrenze, che incrementi ogni volta che trovi la parola. Così facendo potresti anche tenere un' altra variabile che si incrementa ogni volta che la parola viene trovata, independentemente dal post, e che quindi ti risparmierebbe il processo di sommare tutte le occorrenze nei diversi post. Se ci pensi un po', sviluppando il codice in questo modo troveresti anche altre scorciatoie agli altri calcoli che bisogna fare.

---

esattamente quello che intendevo, perchè leggersi qualcosa n volte per n volte, se si può scorrere 1 volta in totale, in questo modo si guadagna un buon quantitativo di tempo su controlli molto lunghi, per non parlare del lato positivo dal punto di vista della leggibilità del codice

Answer 2

Ordinare le liste è la cosa meno dispendiosa, fidati. Il grosso è scorrere i post e contare le parole, non usare count().

Answer 3

per @Alessio.Palma : il mio algoritmo è al 'limite' dei tempi richiesti perchè rientra nei timeout di tutte e 8 le istanze ma essendo troppo 'a limite' mi piacerebbe velocizzare pertanto, se qualcuno ha consigli da dare, sono ben lieto di accettarli… io ho svolto le cose in questo modo:

1. Apro file e leggo tutto il testo con il metodo 'read'
2. con 'replace' e 'split' ottengo una lista con tutte le parole del file (tutte le parole quindi non riga x riga) = tempo di trasformazione fp8 circa 300 ms in VM (calcolo presunto ma abbastanza verosimile… il mio computer di solito impiega il doppio rispetto alla VM e infatti impiego 600 ms sul mio pc)
3. itero tutta la lista e quando trovo la parola <post>  ricavo anche il numero di post.
4. Quando l'elemento è diverso da post e da identificativo memorizzo i dati direttamente nella lista di dizionari tranne per quanto riguarda la chiave 'I3' per la quale utilizzo un dizionario a parte che si azzera ad ogni nuovo post e si aggiorna.
5. Ordino il risultato e restituisco.

il mio output su esercizio è:

2.22s call     ==test_02.py==Test==test_fp8

quindi bene ma non benissimo… ho visto tempi pari alla metà del mio.. cosa potrei cambiare?

Comments

io faccio praticamente come te e ci metto pure i tuoi tempi. quanto fai in totale? se fossi in te per ora mi accontenterei di prendere 30 e un eventuale bonus, tanto c'è ancora un'intera settimana di peer assessment per migliorare, io ho fatto così e infatti ora smetto di provarci

---

Si. È quello che ho intenzione di fare... X hai ragione

---

usi .count() per trovare le occorrenze?

---

No. Scorro le parole man mano aggiorno dizionario