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

Do you need help?

Notice Board

Per partecipare al corso di Fondamenti di programmazione 2023-24 loggatevi e attivatelo nella vostra pagina dei corsi preferiti. A quel punto il corso appare nel menù personale cliccando sul proprio avatar. Per i materiali degli anni precedenti seguite lo stesso metodo.

To join the Programming/Lab 2023-24 course, log-on and select it on the my courses page. It will appear on the personal menu of your avatar. For earlier years use the same method.

Trovare i vertici dei rettangoli in modo efficiente. HW6

M
Matteo Benvenuti (370 points)
3 8 9
in HW6 obbligatorio by (370 points)
recategorized by
Ho finito HW6 e ora sto provando a renderlo più efficiente, e ho notato che le funzioni che impiegano più tempo nel mio programma sono quelle che utilizzo per trovare i vertici in alto a sinistra ed in basso a destra di ogni rettangolo.

Alle mie funzioni passo un insieme chiamato "insieme_colori" che inizialmente contiene tutti i diversi colori presenti nell'immagine (tranne il nero) , scorrendo le righe , se nella riga sono presenti colori che sono nell'insieme_colori la scorro pixel per pixel inserendo in una lista  la posizione dei  primi pixel dei colori in questione e rimuovo il colore da "insieme_colori". Ovviamente per gli angoli in basso scorro sia la matrice che le righe al contrario .

Ho provato a migliorare queste funzioni inserendo più controlli per cercare  di scorrere meno  pixel possibili , ma il tempo che guadagno evitando i pixel inutili è meno di quello che perdo a fare i controlli .

Vorrei sapere se avete qualche consiglio da darmi per velocizzare il processo . Spero di aver fatto capire il funzionamento delle mie funzioni , se avete domande sarò lieto di rispondervi.

2 Answers

d
davide.marincione (1380 points)
0 5 14
by (1.4k points)
Quindi, prima di controllare per i pixel, hai un qualche modo per trovare ciascun colore presente nell'immagine (credo qualcosa come un set creato dal sommare tutte le righe della matrice-lista). Non è un po' inefficiente? Dopotutto in questo modo stai andando attraverso la matrice due volte, il che sicuramente rallenta-
Perché non provi a pensarla in modo differente? Vai attraverso la matrice una sola volta controllando i pixel che ti interessano (ovvero scartando i pixel neri) e, per ciascuno di essi, fai i dovuti calcoli al rispettivo rettangolo- se è un colore nuovo allora lo registri e fai le dovute cose che fai quando hai un rettangolo nuovo, se è un colore che hai già "visto" allora fai altro: così dovresti teoricamente arrivare a sapere "tutto" dei rettangoli e l'unica cosa che ti rimarrà da fare è l'immagine codificata.
M
Matteo Benvenuti (370 points)
3 8 9
by (370 points)
In realtà per trovare l'insieme dei colori non ci metto un tempo eccessivo e questo mi risparmia molti controlli successivamente , permettendomi di fermarmi una volta trovati tutti gli angoli alti senza dover scorrere tutta la lista.

Comunque proverò a seguire il tuo consiglio progettando una funzione che trova i nuovi colori insieme agli angoli alti.
AdSum (16290 points)
9 20 134
by (16.3k points)
Da come lo descrivi il tuo procedimento sembra un macigno. "tutti i diversi colori presenti nell'immagine" come li ottieni? Suppongo scorrendo l'intera matrice, quindi la scorri due volte? Una per i colori e una per i vertici? In tal caso è piuttosto pesante. Pensala cosi: tu non sai che colori ci sono, tranne per uno che fa eccezione, ovvero il nero, tu sai che devi ignorare il nero e considerare tutto il resto. Parti da questo concetto e vedi che velocizzi il programma!
M
Matteo Benvenuti (370 points)
3 8 9
by (370 points)
Come ho già risposto ad un atro commento la ricerca dei colori , fatta con un insieme , ci mette relativamente  poco tempo a trovare i colori , e ciò mi risparmia di dover scorrere tutta la lista permettendomi di fermarmi una volta esauriti i colori evitandi di eseguire molti controlli.

Comunque proverò a seguire il tuo consiglio progettando una funzione che trova i nuovi colori insieme agli angoli.