Idee e spunti per ridurre i tempi di esecuzione?

Question

Salve, ho consegnato il mio HW (passando tutti i test) ma ho scoperto di essere lento nel calcolo di cAB e cBA. Così ho iniziato a provare varie soluzioni ma risultano tutte molto simili come tempi di esecuzione. Come posso migliorare questo punto?

Answer 1

non so che idea hai sviluppato. io di getto ho fatto cosi: scorro con un ciclo for la prima riga; se trovo un 1 in A[i], comincio a scorrere la seconda riga al contrario selezionando slice via via piu grandi (con un ciclo while che controlla che sono ancora nella riga e che non supero la lunghezza di tau), che finiscono sempre in B[i]. appena trovo un 1, break e aggiornamento del count, altrimenti allargo la slice e ricontrollo.

non ho ancora pensato a grandi ottimizzazioni, quindi in realtà seguo la tua domanda.

Comments

Io faccio semplicemente quello che dice la traccia. Scorro A, se trovo un '1', controllo la porzione utile di B. Se c'è un '1' anche lì, allora cAB aumenta di 1. E così al contrario per cBA.

Ma così passi tutti i test?

---

si. credo che facciamo piu o meno la stessa cosa, ma invece di controllare tutta la porzione utile subito, se trovo un 1 in A[i],

controllo prima B[j:i+1] (ovvero B[i])

poi [j-1:i+1],

poi [j-2;i+1]...

il tutto finché non trovo un 1 oppure finche la slice è più lunga di tau oppure finche non "slitto" fuori dalla sequenza (quindi la porzione non è più utile)

Ripeto, magari si può fare meglio, l'ho finito ieri sera

---

Ho appena testato questo tuo metodo ma è anche più lento del mio.

---

A nessuno è venuto in mente di lavorare direttamente su liste di indici invece che stare a combattere con liste di 0 ed 1 e gli slice?

La butto li! Senza scendere nei dettagli....

---

Il problema è che creare liste di indici porta via circa lo stesso tempo.

---

dipende da quando le crei

---

@S3b4stian82  esattamente quello che ho fatto io, pensavo fosse troppo lenta come cosa, ma forse no (?)

sto aspettando che la vm del terrore riparta e testi il mio hw...

---

Facci sapere come và rispetto all'altra soluzione!

Answer 2

ciao, io scorro accento per accento, verificando la prima riga con la seconda, seconda con prima (ad ogni accento), poi prima con terza, terza con prima etc, per poi seconda con terza, terza con seconda e così via, quindI:

per ogni accento in A, controlla anche in B, se in uno dei due trovi un 1, esegui, poi alla fine della riga non aumento A ma bensì B, quando ho finito tutto il testo con B aumento A e B e ricomincio

Answer 3

Un'altra cosa che ho provato sta sera è questa: memoization

Ho provato a mettere in cache le rappresentazioni fonetiche delle parole che vengono prodotte da pronouncing.phones_for_word, purtroppo non ho notato miglioramenti prestazionali apprezzabili per via dei test fatti con campioni di testo troppo brevi e/o nella quale non vi sono tante parole che si ripetono. Da tenere a mente che sta cosa mangia memoria.

Condivido perchè può essere utile in altri casi.

Answer 4

io calcolo cAB e cBA in un unico ciclo che itera i valori di entrambe le righe e man mano che confronta aggiorna la posizione dell'ultimo accento incontrato su ciascuna riga.

Inizialmente facevo due passaggi per calcolare prima cAB e poi cBA, poi ho integrato tutto in un unico passaggio, ma non ho misurato le prestazioni.

Altra cosa evito di confrontare la stessa coppia di righe più di una volta, ad esempio se confronto la riga 3 con la 5 non ripeto il confronto per la riga 5 con la 3.

Ho passato tutti i test.

Comments

Confermo che calcolare cAB e cBA contemporaneamente aumenta l'efficienza, anche se si parla di poco tempo (ovviamente dipende dal modo in cui viene implementato il tutto)

---

posso chiederti come eviti di iterare sulle coppie opposte?
Hai usato uno stratagemma simile a quello che di base andava utilizzato nell'hw2?

---

confronto sole le coppie dove l'indice della prima riga è inferiore a quello della seconda, ad esempio, avendo dieci righe: (0, 1), (0, 2), ... (0, 9), (1, 2), (1, 3), ... (1, 9), (2, 3), (2, 4), e così via.

Ho ottenuto questo iterando le righe con due cicli annidati.

Answer 5

effettivamente anche a me il grosso del tempo è preso dal calcolo di cAB e cBA. Qualcuno ha trovato un modo di renderlo più efficiente?