velocizzare codice hw4

Question

finalmente sono riuscito ad unire le parole e a completare l'esercizio. la parola nascosta l'ho trovata tramite il max di count per questo procedimento mi manda in timeout tutti i test. un modo per velocizzare?

Answer 1

Da come l'hai descritto l'approccio che utilizzi non credo possa essere velocizzato, devi ripensarlo da capo.

Dopo aver composto tutte le parole presenti nel file, il modo più immediato di iniziare credo sia quello di generare tutte le possibili sottostringhe della lunghezza data presenti nella prima parola per poi procedere sapendo che sicuramente la parola segreta è una tra queste sottostringhe (dato che deve essere presente una volta in ogni parola).

Comunque come ti ha consigliato Christian, prima di porre una domanda controlla quelle simili già presenti su Q2A perché, per esempio, questa stessa risposta che ti ho dato l'avevo già scritta uguale in un altro post ;)

Comments

ho fatto come hai detto tu, ho velocizzato molto anche se alcune liste me le ritorna sbagliate. ora vedo un pò come risolvere

---

ricordati di controllare che la parola segreta sia presente una sola volta in ogni parola e di non considerare le sottostringhe che non rispettano questa condizione

inoltre per velocizzare prova ad evitare di analizzare nuovamente una parola se l'hai già analizzata all'interazione precedente

---

per esempio nel file ft2 il programma mi rileva che la parola nascosta è la w invece è la e. perche guardando il file anche la w c'è sempre

---

esattamente questo non ho tenuto in conto 'e si ripete una sola volta'

grazie davvero ora ci rifletto sopra e vedo come posso integrare questa cosa

---

La parola segreta deve trovarsi esattamente UNA SOLA VOLTA in ogni parola. 'w' non rispetta questa condizione, mentre 'e' sì

---

quindi in questo caso bisogna usare un dizionario e come valore mettere il numero di volte che viene ripetuta?

---

ci sono vari modi per implementare questo controllo, ma è necessario farlo visto che è specificato nella traccia, altrimenti ti troveresti "più di una parola segreta" in svariati test

---

e si infatti come è successo a me

---

no non riesco a fare questo controllo

---

SI può fare anche senza l'utilizzo dei dizionari utilizzando la funzione count() che credo già conosci ;)

---

che si può utilizzare anche con l'implementazione che sfrutta i dizionari ovviamente

---

si però è molto lenta

---

io faccio 115 ms

---

con count fai cosi poco?

Answer 2

Ciao, 

innanzitutto vedi se nella fase di Peer Assessment ricevi qualche consiglio utile da chi ha letto il tuo algoritmo 

Per caso hai già dato un'occhiata a queste altre domande?

Answer 3

Innanzitutto ti consiglio di capire perché va piano. Cosa fai? Dividi in sotto parole lunghe M (lunghezza della parola magica) e poi conti quante di queste sono tante quanto le parole? Pensa, se fai questo o qualcosa di simile, quando fermeresti questa conta? Abbiamo degli indizi importanti, ovvero che la parola magica c'è esattamente una volta in ogni parola.  Se non sfrutti questo sarà difficile avere un programma ottimizzato, devi pensare  1) dov'è che il tuo programma fa cose superflue 2) dov'è che impiega troppo tempo per un'operazione che potresti fare in meno. Ad esempio, se conti quante sottostringhe ci sono e mentre lo fai hanno già superato il numero di parole, dovresti fermarti; detto questo, ti consiglio un approccio più basato sugli indizi che abbiamo che una cosa super generica