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

Do you need help?

Performance [HW7opt]

G
Giordano_Dionisi (3100 points)
16 41 59
in HW7 opzionale by (3.1k points)
recategorized by
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à..
590 views
closed

3 Answers

Best answer
andrea_25 (6070 points)
2 2 24
by (6.1k points)
selected by
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)
16 41 59
by (3.1k points)
Effettivamente potrei tipo portarmi dietro un dizionario con il numero di occorrenze per ciasun valore che è presente nella sequenza, me lo passo poi ricorsivamente e se ho sequenze pari di valori le elimino tutte di botto... Questo è buono come aspetto, per il primo mi fai pensare idealmente alla programmazione dinamica di Algoritmi 2, però è un ottimo consiglio veramente, dopo ti dico se sono riuscito a migliorare qualche cosina !!
G
Giordano_Dionisi (3100 points)
16 41 59
by (3.1k points)
Calcola ti voto assolutamente come miglior risposta perchè te lo stra meriti... Ho fatto come hai detto te (per il secondo punto) e ho passato altri 3 test (al momento non supero l'ultimo per timeout)... In pratica tolgo ogni volta dal dizionario tutte le occorrenze pari e così ho un risparmio di velocità che è mega galattico... Non so come ringraziarti, sei stato veramente di aiuto (ora vedo come migliorare per l'ultimo test, magari implementando proprio il tuo primo consiglio) !!!!

P.S.: Sono passato da 108 ms in un test a 2.99, per farti capire l'efficienza
andrea_25 (6070 points)
2 2 24
by (6.1k points)
Grazie a te!

Ormai ti manca davvero poco per passarli tutti =)
G
Giordano_Dionisi (3100 points)
16 41 59
by (3.1k points)
Si si guarda ti terrò lo stesso aggiornato (manderò un'altra risposta qui), anche perchè per l'ultimo il problema non è il tempo ma la correttezza (non passo il diciassettesimo test)... Si vede che il caso base va un attimo sistemato, ti terrò sicuramente aggiornato comunque sia !!!!
G
Giordano_Dionisi (3100 points)
16 41 59
by (3.1k points)
edited by
Insomma te lo ho promesso e ti aggiorno... Alla fine ho implementato anche il tuo primo consiglio (pensavo che non passassi il test 17 per correttezza e loop infinito) e praticamente sono passato dai 3 ms di prima a 9 microsecondi, perchè entravo in troppe ricorsioni totalmente inutili... Di nuovo, grazie mille veramente !!
andrea_25 (6070 points)
2 2 24
by (6.1k points)
Bene sono contento che questi consigli ti sono stati utili, ottimo lavoro!
D
Davide (650 points)
5 14 16
by (650 points)

Scusate ma che intendete per 

se un numero nella sequenza principale si ripete un numero pari di volte non comparirà mai nelle sottosequenze del risultato finale

Ad esempio con questa sequenza 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 10 9 10 9 10 1 8 1 7 1 6 1 5 1 4 1 3 1 2 1 11  il risultato è {'9 10 11', '10 9 11'}  ma 1 compare 21 volte nella sequenza principale

G
Giordano_Dionisi (3100 points)
16 41 59
by (3.1k points)
In realtà compare 16 volte l'uno, infatti un numero pari di volte.. Gli altri uni che vedi fanno parte dell'11 o del 12 che sono, appunto, numeri diversi (cioè non l'uno come singolo carattere, ma proprio come numero separato da spazi a sinistra ed a destra)
D
Davide (650 points)
5 14 16
by (650 points)
Grazie mille Giordano
e
eduard_lisnic (870 points)
0 4 11
by (870 points)
Ringrazio anche io sia Giordano che Andrea, sono riuscito ad implementare il codice correttamente grazie a questa domanda.
G
Giordano_Dionisi (3100 points)
16 41 59
by (3.1k points)
Stiamo tutti qui per imparare ragazzotti, sono felice che almeno con il mio dubbio ho risolto sia il mio problema che quello di molti altri !!
f
fabio.chiarini (2280 points)
0 0 7
by (2.3k points)
Grazie Andrea per i suggerimenti, davvero utilissimi! E complimenti per aver trovato un'idea tanto semplice da implementare quanto è efficace! Anche io avevo problemi con gli ultimi 4 test, ho implementato il tuo suggerimento n. 2 e ora ho il timeout solo su 1 test. Cercherò di usare anche il tuo suggerimento n. 1, una volta che avrò capito come fare. Grazie ancora
G
Giordano_Dionisi (3100 points)
16 41 59
by (3.1k points)
Io avevo la stessa problematica, se implementi il suggerimento numero uno, molto più facile da implementare per me, vedrai che passi anche l'ultimo test e risparmi dell'ordine di tipo 2-3 ordine di grandezza, un botto veramente !!
f
fabio.chiarini (2280 points)
0 0 7
by (2.3k points)
Stavo facendo fatica a capire cosa intedesse ma forse ci sono. Ti faccio un esempio Giordano per capire se l'intuizione è quella giusta. Partendo con una lista di questo tipo [1, 2, 3, 1, 1, 2, 2] e analizzando il numero 1 vedo che:

- togliendo gli indici 0 e 3 la sotto lista è [2, 3, 1, 2, 2]

- togliendo gli indici 0 e 4 la sotto lista è [2, 3, 1, 2, 2], ovvero la stessa e quindi il risultato prodotto sarà uguale. Perciò potrei completamente "interrompere" la ricorsione in questo caso.

Ho capito giusto?
G
Giordano_Dionisi (3100 points)
16 41 59
by (3.1k 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
by (2.3k points)
Spettacolo, implementato e passato tutti i test con un tempo decente. Approfondirò il concetto. Grazie ancora ad entrambi!
G
Giordano_Dionisi (3100 points)
16 41 59
by (3.1k 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
by (6.1k points)
Per programmazione dinamica si intende la combinazione di ricorsione e memoization?
G
Giordano_Dionisi (3100 points)
16 41 59
by (3.1k 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 (17470 points)
8 29 105
by (17.5k 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)
16 41 59
by (3.1k 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)
7 14 42
by (3.5k 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.