Please ignore secret bonuses. Secret tests do NOT award bonus. Max hw grade is 30+2 bonus efficiency

Do you need help?

HW8 - Migliorare ricorsione test 100x40

B
Babby740 (1240 points)
24 35 39
in HW8 obbligatorio by (1.2k 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
878 views
closed

5 Answers

Best answer
m
mel8 (1250 points)
1 12 19
by (1.3k points)
selected by
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)
24 35 39
by (1.2k 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)
1 12 19
by (1.3k 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)
24 35 39
by (1.2k 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)
1 12 19
by (1.3k 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)
13 15 118
by (18.9k 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)
24 35 39
by (1.2k points)
Sì, do la precedenza a destra per ottenere direttamente il primo cammino in ordine lessicografico.
Christian (15220 points)
3 4 77
by (15.2k 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)
24 35 39
by (1.2k 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)
3 4 77
by (15.2k 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)
24 35 39
by (1.2k points)
edited by
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)
20 39 131
by (11.3k points)

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

è più veloce

B
Babby740 (1240 points)
24 35 39
by (1.2k points)
Ok, grazie.    .
a
a.pietroluongo (11250 points)
20 39 131
by (11.3k points)
Hai risolto?
B
Babby740 (1240 points)
24 35 39
by (1.2k points)
edited by
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)
2 3 27
by (2.7k points)

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