Performance [HW7opt]

Question

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

Answer 1

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?

Comments

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 !!

---

Spettacolo, implementato e passato tutti i test con un tempo decente. Approfondirò il concetto. Grazie ancora ad entrambi!

---

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 

---

Per programmazione dinamica si intende la combinazione di ricorsione e memoization?

---

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

Answer 2

-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ì

Comments

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

Answer 3

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.