Ottimizzare algoritmo Hw3 Esercizio 1

S
SkyLion (1020 points)
5 15 24
asked Nov 15, 2017 in Es1 by SkyLion (1,020 points)
closed Nov 21, 2017 by andrea.sterbini

Ho provato a svolgere il primo esercizio dell'Homework3 andando a scorrere pixel per pixel l'ìimmagine, e se trova un pixel del colore cercato, cerca di costruirsi il quadrato più grande possibile senza andare ad incappare in un pixel di colore diverso, andando a controllare prima i lati e poi le digonali (in questo modo).

Nel caso in cui tutti i pixel controllati risultato dello stesso colore, procede a controllare tutto l'interno del quadrato perchè potrebbero essercene degli altri all'interno... Così facendo però nell'ultima istanza di test l'algoritmo impiega ben 34 secondi... Come posso ottimizzarlo?

340 views
closed with note: deadline expired

2 Answers

answered Nov 15, 2017 by Anon1 (9,920 points)
Basandomi sul tuo algoritmo, perché controlli le diagonali? Hai provato a vedere i tempi se controlli nessuna diagonale e poi una sola prima di controllare l'interno?
S
SkyLion (1020 points)
5 15 24
commented Nov 15, 2017 by SkyLion (1,020 points)
Si, inizialmente il mio algoritmo controllava solo due lati, poi aggiungendone altri due ho visto che il tempo si è dimezzato... aggiungendo una diagonale ho ancora diminuito il tempo e aggiungendo anche l'altro ho dimezzato un'altra volta.
commented Nov 15, 2017 by Anon1 (9,920 points)
A questo punto potresti "tagliare" il quadrato in altri modi, però stai attento perché arriverà un punto dove non conviene più "tagliare", ossia ci metteresti più tempo a fare i controlli preliminari che quelli completi.
Gianluigi (1420 points)
7 17 30
answered Nov 17, 2017 by Gianluigi (1,420 points)
Potresti pensare di cercare i pixel di colore diverso e salvarti la loro posizione. In questo modo saprai la posizione degli "ostacoli", e saprai se vale la pena continuare a cercare il quadrato piu' grande in una determinata posizione.