velocizzare codice hw4

s
simone.lioy (1420 points)
23 30 39
asked Nov 19, 2019 in HW4 obbligatorio by simone.lioy (1,420 points)
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?
564 views

3 Answers

Best answer
AndreaGasparini (18730 points)
6 12 118
answered Nov 19, 2019 by AndreaGasparini (18,730 points)
edited Nov 19, 2019 by AndreaGasparini
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 ;)
Antares (7770 points)
5 6 41
commented Nov 20, 2019 by Antares (7,770 points)
SI può fare anche senza l'utilizzo dei dizionari utilizzando la funzione count() che credo già conosci ;)
AndreaGasparini (18730 points)
6 12 118
commented Nov 20, 2019 by AndreaGasparini (18,730 points)
che si può utilizzare anche con l'implementazione che sfrutta i dizionari ovviamente
s
simone.lioy (1420 points)
23 30 39
commented Nov 21, 2019 by simone.lioy (1,420 points)
si però è molto lenta
AndreaGasparini (18730 points)
6 12 118
commented Nov 21, 2019 by AndreaGasparini (18,730 points)
io faccio 115 ms
s
simone.lioy (1420 points)
23 30 39
commented Nov 21, 2019 by simone.lioy (1,420 points)
con count fai cosi poco?
Christian (15220 points)
2 4 77
answered Nov 19, 2019 by Christian (15,220 points)

Ciao, 

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

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

T
Trasciatti (1400 points)
10 20 34
answered Nov 19, 2019 by Trasciatti (1,400 points)
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