Ottimizzazione HW8rec

Question

Salve a tutti, sono riuscito a far in modo che il programma mi restituisca in modo corretto la sequenza concatenata, ma non riesco ad ottimizzarlo per le tempistiche. Mi passa I primi 4 testa da li in poi i tempi di compilazione sono molto lunghi. Qualche consiglio????

Answer 1

Ti consiglio di leggere i consigli di questo post, si parla dello stesso identico problema

https://q2a.di.uniroma1.it/16277/hw8-di-recupero-qualche-consiglio?course=advices/fondamenti-di-programmazione-19-20

Comunque i consigli sono gli stessi:

• Cerca di velocizzare il programma non ripetendo sempre le stesse operazioni

Se riesci, quando chiami la ricorsione e fai un certo percorso, salvati le concatenazioni delle stringhe che usi, così la prossima volta che ti servirà quel percorso lo avrai già disponibile sotto forma di stringa e non dovrai richiamare di nuovo la ricorsione per lo stesso identico percorso.

Esempio:

pezzi_0.txt: ottuso iodato coniglio

ottuso -> None  [0 sottostringhe] |||| None

iodato ->  o -> ottuso [1 sottostringa] |||| [iodatottuso]

coniglio -> o -> ottuso | coniglio -> io -> iodato |||| [2 sottostringhe ] --> [conigliodatottuso] OPPURE [conigliottuso]

In "coniglio" ti salvi i due percorsi che può compiere la parola, e risparmi il tempo dell' overhead della chiamata di funzione per la ricorsione.

Comments

Ciao,

sto cercando di ottimizzare il programma per riuscire a passare l'ultimo test che va in timeout, ma con più tempo (3 sec) viene superato...

Riesco a passare tutti gli altri test senza salvare le concatenazioni trovate, infatti se provo a salvare tutte le combinazioni trovate, il programma spende più tempo a cercare nelle combinazioni salvate che provare ad aggiungere/scartare le combinazioni dalla sequenza in prova.

C'è un qualcosa che mi sfugge?

Grazie per l'aiuto

---

Anche io ho problemi con quel test, in particolare non mi riesce a trovare l'ultima parola poiche' tutte le parole sono connesse tra loro. Hai qualche soluzione per quel problema?

---

puoi provarle tutte

---

Vedendo che nell'ultimo test, potenzialmente tutte le parole hanno una successiva, l'unica condizione per uscire dalla funzione ricorsiva è che la successiva non sia nella sequenza e che la sequenza abbia la stessa dimensione del numero di parole totali...

Non ho trovato altro modo che farlo funzionare con la forza bruta  (ma che comunque va in timeout nel mio codice)