Do you need any help?

Performance [HW7opt]

G
Giordano_Dionisi (3100 points)
12 38 58
asked Nov 27, 2020 in HW7 opzionale by Giordano_Dionisi (3,100 points)
recategorized Nov 27, 2020 by Giordano_Dionisi
Salve ragazzuoli,

Sto facendo l'hw7 opzionale e in poco tempo sono giunto alla risoluzione con un algoritmo veramente fighissimo ricorsivo che passa 14 test su 18... Inizialmente ho pensato che sforassi il tempo degli ultimi 4, ma ho notato che tipo il quindicesimo test ci impiega addirittura 30 secondi e passa, insomma per quanto posso aumentare le prestazioni del codice non riuscirò mai ad abbattere i tempi di così tanto... Ora la mia domanda è: avete qualche idea su come risolverlo, perchè io non riesco a capire come migliorare ulteriormente, in realtà..
334 views

3 Answers

Best answer
andrea_25 (6070 points)
2 2 24
answered Nov 27, 2020 by andrea_25 (6,070 points)
selected Nov 27, 2020 by Giordano_Dionisi
Ti posso dare principalmente due dritte:

1. Per evitare chiamate ricorsive inutili, tieni in considerazione le sottosequenze che hai già analizzato, in modo tale da risparmiare millisecondi (o secondi) sul tempo di esecuzione totale;

2. Hai notato che se un numero nella sequenza principale si ripete un numero pari di volte non comparirà mai nelle sottosequenze del risultato finale?
G
Giordano_Dionisi (3100 points)
12 38 58
commented Dec 2, 2020 by Giordano_Dionisi (3,100 points)
Assolutamente si e se vuoi approfondire questa è l'idea alla base della programmazione dinamica proprio, perchè la ricorsione molto spesso va chiamate ricorsive inutili proprio e quindi si possono saltare, perchè il risultato già lo conosco (e puoi bypassare tipo saltare una marea di passi in questo modo !!
f
fabio.chiarini (2280 points)
0 0 7
commented Dec 2, 2020 by fabio.chiarini (2,280 points)
Spettacolo, implementato e passato tutti i test con un tempo decente. Approfondirò il concetto. Grazie ancora ad entrambi!
G
Giordano_Dionisi (3100 points)
12 38 58
commented Dec 2, 2020 by Giordano_Dionisi (3,100 points)

E di che, qua Andrea ci ha risolto i problemi a tutti direi !!!

Comunque per quanto riguarda la programmazione dinamica considera che tanto la farai con il corso di Algoritmi 2, quindi prima o poi la dovrai approfondire per forza yes

andrea_25 (6070 points)
2 2 24
commented Dec 2, 2020 by andrea_25 (6,070 points)
Per programmazione dinamica si intende la combinazione di ricorsione e memoization?
G
Giordano_Dionisi (3100 points)
12 38 58
commented Dec 2, 2020 by Giordano_Dionisi (3,100 points)
Si si esatto, la memoizzazione praticamente... Negli ultimi anni questa parte era fatta in modo più approfondito dal prof. Monti, mentre il prof. Wollan di solito si concentrava più sulla parte dei grafi e poco sulla programmazione dinamica
twgever (15190 points)
7 27 105
answered Nov 27, 2020 by twgever (15,190 points)
-Hai provato a usare il line profiler per vedere quali sono le parti che ti succhiano via più tempo?, concentrati su quelle, vedrai che qualche idea ti viene fuori.

-non so come sia l'hw7, ma se devi vedere se qualcosa è presento dentro una lista, ti conviene tramutare la lista in un insieme e di fare la ricerca lì
G
Giordano_Dionisi (3100 points)
12 38 58
commented Nov 27, 2020 by Giordano_Dionisi (3,100 points)
Infatti ho fatto proprio questo, cioè per fare la ricerca ho tramutato in insieme, tanto bisogna vedere se ci sono doppioni o meno e quindi stavo una bomba... Usando il line profiler mi escono fuori cose come che certi if sono troppo lenti, addirittura i return in proporzione ci mettono troppo tempo e via dicendo... Ho l'impressione che ho proprio usato la struttura dati sbagliata... Comunque per il momento grazie mille, vediamo come va la storia
1
1937764 (3520 points)
6 14 42
answered Nov 27, 2020 by 1937764 (3,520 points)

Osserva il file test_01.py

In alcuni test non è necessario usare ricorsione. Sono proprio i test dove la risposta è un set con 1 solo elemento.

Da qui si intuisce che la parte ricorsiva non è trovare i numeri che compaiono o meno, ma è trovare le combinazioni compatibili con la stringa iniziale.