Migliorare l'efficienza HW4

Question

Buongiorno ragazzi,ho creato il programma per l'HW04 ma non riesco a superare un test per 0.088 sec.Avete suggerimenti per migliorare ancor di più questo tempo.

PREMESSA: non ho usato dizionari ,e volevo sapere se ci fosse un modo senza dizionari per migliorare quei millisecondi che mancano

Answer 1

Come trovi scritto nelle regole del corso, l'argomento di questo homework sono proprio i dizionari (oltre a i file) perciò io personalmente ti consiglio di provare ad implementare una soluzione con essi, sia perché sarà nettamente più efficiente, sia perché il senso di suddividere gli Homework per argomenti è proprio quello di approfondirli tutti, se così facendo non prendi confidenza con i dizionari molto probabilmente avrai problemi all'esame quando sarà necessario usarli e non sarà specificato come in questo caso.

L'obiettivo che dovresti raggiungere dovrebbe essere quello di vedere un problema del genere e capire subito che la soluzione migliore implica l'utilizzo di dizionari. Ti sarà molto utile più avanti, soprattutto ai fini di questo corso.

Comments

Condivido assolutamente,  infatti sto già pensando a come risolvere con i dizionari, però è diventata una sorta di sfida per risolverla anche sole con le liste :)

---

Su una soluzione efficiente con solo non saprei aiutarti, personalmente ho iniziato subito con i dizionari una volta analizzato il problema (questo non precludo anche l'utilizzo di liste oltre al dizionario ovviamente)

---

A differenza dell'HW2 dove con i dizionari il guadagno in performance era notevole e permetteva di superare tutti i test, a mio avviso nell'hw4 senza utilizzare dizionari già si ottengono dei timings eccezionali rispetto al timeout

---

in realtà per il precedente homework, essendo che le chiavi erano numeriche si poteva utilizzare una lista al posto di un dizionario, con i piloti che invece di essere delle chiavi erano gli indici della lista, in questo modo si realizzava ancora più efficientemente in quanto l'accesso ad un indice di una lista è più rapido rispetto al calcolo dell'hash per accedere tramite chiave ad un elemento di un dizionario

---

Si infatti sono riuscito a concludere anche con un buon tempo,per ora

Answer 2

Premesso che, come già consigliato, sia più indicato l'utilizzo dei dizionari (non tanto per il tipo di problema, quanto per l'importanza di saperli maneggiare bene), c'è modo di passare i test anche con le liste. Quando prendi in esame una sottostringa, passa direttamente alla successiva se non rispetta le caratteristiche che deve avere ed evita controlli inutili (es.: se la stringa che segue è identica a quella prima a cosa serve ricontrollare le sue caratteristiche?).
Ah, ed evita il metodo count.
Buona ottimizzazione!

Comments

Grazie per la chicca, non avevo valutato questo particolare caso per risparmiare ancora più tempo.

Answer 3

Potresti creare un insieme di elementi che non devono essere presi. In questo modo dovresti riuscire a saltare molte parole che sai per certo non vadano cercate.

Comments

Ho risolto pensando  grazie al suggerimento si zanna,mi è venuto più semplice pensarla come lui..

---

Ho letto, alla fine sono metodi simili che ti abbiamo consigliato. In ogni caso l'importante è che hai risolto.

Buon HW