Consigli velocizzare es2 HW02

a
alessio.palma (1480 points)
0 34 56
asked Nov 16, 2018 in Es2 by alessio.palma (1,480 points)
recategorized Nov 17, 2018 by andrea.sterbini
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.

3 Answers

G
Gdn98 (11600 points)
1 34 101
answered Nov 16, 2018 by Gdn98 (11,600 points)
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
_andrea_ (45670 points)
2 40 297
commented Nov 16, 2018 by _andrea_ (45,670 points)
Io lo faccio ma non mi capacito di come possa andare in timeout negli ultimi due test (solo sulla VM)
G
Gdn98 (11600 points)
1 34 101
commented Nov 16, 2018 by Gdn98 (11,600 points)
Hai detto di utilizzare .count, hai anche provando con un contatore come ti ho detto?
f
francescomolinari (330 points)
0 8 11
commented Nov 16, 2018 by francescomolinari (330 points)
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?
_andrea_ (45670 points)
2 40 297
commented Nov 16, 2018 by _andrea_ (45,670 points)
È esattamente quello che faccio ma va in timeout
J
JosefZerpa (180 points)
0 0 2
commented Nov 17, 2018 by JosefZerpa (180 points)
@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.
G
Gdn98 (11600 points)
1 34 101
commented Nov 17, 2018 by Gdn98 (11,600 points)
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
Xriuk (13590 points)
0 24 116
answered Nov 16, 2018 by Xriuk (13,590 points)
Ordinare le liste è la cosa meno dispendiosa, fidati. Il grosso è scorrere i post e contare le parole, non usare count().
a.capobianco1 (16770 points)
1 54 165
answered Nov 16, 2018 by a.capobianco1 (16,770 points)

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?
_andrea_ (45670 points)
2 40 297
commented Nov 17, 2018 by _andrea_ (45,670 points)
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
a.capobianco1 (16770 points)
1 54 165
commented Nov 17, 2018 by a.capobianco1 (16,770 points)
Si. È quello che ho intenzione di fare... X hai ragione
a
alessio.palma (1480 points)
0 34 56
commented Nov 17, 2018 by alessio.palma (1,480 points)
usi .count() per trovare le occorrenze?
a.capobianco1 (16770 points)
1 54 165
commented Nov 18, 2018 by a.capobianco1 (16,770 points)
No. Scorro le parole man mano aggiorno dizionario