HW8 - Migliorare ricorsione test 100x40

B
Babby740 (1240 points)
19 35 39
asked Dec 17, 2019 in HW8 obbligatorio by Babby740 (1,240 points)
Ho già applicato la funzione 'filtro' che non controlla le parole le quali lettere non sono nella matrice,
quindi nel test 100x40 controllo solamente la seconda parola ma comunque il test va in timeout (sul mio pc ci mette 1.2 secondi).
Come posso migliorare la funzione ricorsiva in modo che sia più efficace?

La mia funzione ricorsiva fa 3 controlli:

if Caso base -> return

if Destra -> ricorsione

if Giù -> ricorsione
673 views

5 Answers

Best answer
m
mel8 (1250 points)
0 12 19
answered Dec 17, 2019 by mel8 (1,250 points)
selected Dec 18, 2019 by Babby740
Prima di chiamare le funzioni ricorsive verso destra o verso il basso, prova a controllare in anticipo se chiamare la funzione ricorsiva in una determinata direzione. Per esempio, prima di chiamare la ricorsione verso destra, controlla se a destra troverai la prossima lettera che stai cercando della parola, altrimenti è inutile chiamare la ricorsione ma restituisci direttamente -1.
B
Babby740 (1240 points)
19 35 39
commented Dec 17, 2019 by Babby740 (1,240 points)
Si il controllo lo faccio. Chiamo la ricorsione se l'elemento successivo nella matrice è uguale all'elemento succesivo della stringa.
m
mel8 (1250 points)
0 12 19
commented Dec 17, 2019 by mel8 (1,250 points)
Allora penso che la funzione ricorsiva sia ottimizzata, forse il problema è fuori. Una volta trovata la prima occorrenza della parola ti fermi o continui a cercare per tutta la matrice? Come gestisci i risultati restituiti dalla funzione ricorsiva? Che strutture dati utilizzi per i risultati? Come generi la lista finale? Forse è qui che bisogna rivedere qualcosa.
B
Babby740 (1240 points)
19 35 39
commented Dec 17, 2019 by Babby740 (1,240 points)
Appena trovo la parola nella matrice, passo alla parola successiva, metto il risultato della funzione ricorsiva in un dizionario e infine restituisco una list comprehension che mi aggiunge - 1 se la parola non è nel dizionario e se invece c'è, aggiunge il valore della chiave.
m
mel8 (1250 points)
0 12 19
commented Dec 17, 2019 by mel8 (1,250 points)
Guarda io faccio esattamente la stessa cosa ma mi ci mette 0.6 secondi a passare il test Non so, forse è da ottimizzare la parte in cui ricavi la griglia e le parole? La griglia è molto grande in quel test, magari perdi tempo lì.
plm (18850 points)
7 15 118
answered Dec 17, 2019 by plm (18,850 points)
Mi viene il seguente dubbio, dai la precedenza a destra nella ricorsione? Da come la descrivi sembra che potresti incorrere in un doppio controllo e diventa costoso tornare indietro
B
Babby740 (1240 points)
19 35 39
commented Dec 17, 2019 by Babby740 (1,240 points)
Sì, do la precedenza a destra per ottenere direttamente il primo cammino in ordine lessicografico.
Christian (15220 points)
2 4 77
answered Dec 17, 2019 by Christian (15,220 points)
Cosa fa la funzione filtro? Io per eliminare il controllo delle parole le cui lettere non sono nella matrice ho utilizzato i set, dovrebbe essere uno dei metodi più efficienti ;)
B
Babby740 (1240 points)
19 35 39
commented Dec 17, 2019 by Babby740 (1,240 points)
si, metto le lettere della matrice in un insieme e poi controllo se le lettere di ogni parola sono tutte in ins, appena ne trovo una che non è in ins -> return False
Christian (15220 points)
2 4 77
commented Dec 17, 2019 by Christian (15,220 points)
Prova ad utilizzare la funzione del set che verifica se la parola è un subset della matrice.. dovresti guadagnare qualcosina... (credo)
B
Babby740 (1240 points)
19 35 39
commented Dec 17, 2019 by Babby740 (1,240 points)
edited Dec 17, 2019 by Babby740
Ho usato issubset() e il tempo è rimasto uguale. il problema è la funzione ricorsiva che ci mette tanto perchè controlla tutti i cammini possibili.
a
a.pietroluongo (11250 points)
15 38 131
answered Dec 17, 2019 by a.pietroluongo (11,250 points)

Usa s.difference(t)  o  s - t  invece di s.issubset(t)

è più veloce

B
Babby740 (1240 points)
19 35 39
commented Dec 17, 2019 by Babby740 (1,240 points)
Ok, grazie.    .
a
a.pietroluongo (11250 points)
15 38 131
commented Dec 17, 2019 by a.pietroluongo (11,250 points)
Hai risolto?
B
Babby740 (1240 points)
19 35 39
commented Dec 18, 2019 by Babby740 (1,240 points)
edited Dec 18, 2019 by Babby740
Ho risolto. usavo il metodo len dentro la ricorsione per vedere se la posizione usciva o no dalla matrice, ma la matrice non cambia mai quindi ho passato la lunghezza delle righe e delle colonne tramite variabili.
LUPOSaymon (2730 points)
1 3 27
answered Dec 17, 2019 by LUPOSaymon (2,730 points)

Prova a fare il debugging a mano e, con un pizzico di attenzione, noterai un evento interessante