Ottimizzazione HW8rec

S
Samiti (190 points)
0 1 3
asked Feb 13, 2020 in Recupero HW8 by Samiti (190 points)
reshown Feb 13, 2020 by Samiti
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????
243 views

1 Answer

Alexei_Pozidriv (1580 points)
0 4 14
answered Feb 13, 2020 by Alexei_Pozidriv (1,580 points)

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. angry

EffeGi (1530 points)
0 1 5
commented May 22, 2020 by EffeGi (1,530 points)

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

DGreat (1210 points)
7 11 23
commented May 26, 2020 by DGreat (1,210 points)
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?
andrea.sterbini (172780 points)
513 935 1789
commented May 26, 2020 by andrea.sterbini (172,780 points)
puoi provarle tutte
EffeGi (1530 points)
0 1 5
commented May 26, 2020 by EffeGi (1,530 points)

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)