Aiuto per “velocizzare” l’hw6

Question

Ho fatto un programma dove nella prima parte tramite due cicli mi trova il primo punto verde e la distanza con il successivo, poi ulteriori due cicli dove all’interno tutto il procedimento che serve per controllare ogni lato di lunghezza k e faccio un ciclo per ogni lato,fino a vedere se tutti i lati non sono interrotti da pixel neri allora incrementa il totale dei quadrati, utilizzando molti cicli da quanto vedo in molti ne utilizzano ma il mio programma va in timeout, potete consigliare un modo per velocizzare? Già prendo la lunghezza tra pixel verdi e quindi passo di pixel in pixel invece di controllare tutti i pixel in mezzo e i due cicli iniziali servono per controllare tutta l’immagine,sia per trovare il punto verde da cui partire,sia per cercare tutti i quadrati nella griglia e mi sembrano indispensabili

Answer 1

Prova ad iterare sulla griglia e non sull'intera immagine.

Comments

Ma il problema principale è quando la griglia ha la stessa grandezza dell'immagine. In quel caso non vedo scorciatoie per ridurre al minimo le operazioni di controllo dei quadrati.

Answer 2

io come prima idea avevo pensato a trovarmi tutta la griglia e poi cercare i quadrati, ma con la convinzione di essere troppo lento (dovendo scorrere 1 volta l'immagine intera e poi di nuovo la griglia e nel momento in cui si ha dimensione griglia=dimensione immagine equivarebbe a scorrere tutta l'immagine 2 volte) ho abbandonato l'idea, scoprendo che in realtà questa cosa va benissimo in quanto si riescono a passare tutti i test

Answer 3

Trovati pure l'ultimo pixel verde nella riga e l'ultima riga della griglia, da quello che ho capito continui ad iterare pure quando non c'è il bisogno di farlo perchè stai fuori dalla griglia.

In caso hai messo un if per controllare quando sei fuori dalla griglia, ricordati che un if per controllare se saltare una riga/colonna all'interno del for è comunque pesante e quindi sapere tra quali valori deve iterare il for può salvarti più o meno tempo a seconda dell'immagine

Answer 4

Ricordati che mentre iteri sulla griglia, non è necessario arrivare fino alla fine. Se hai ad esempio un k= 3, sai già che trovare un quadrato che ha come vertice iniziale la posizione del penultimo pixel verde è impossibile.

Answer 5

Anche io ho difficoltà a velocizzare il programma e mi va in timeout per un test.

Io ho pensato di trovarmi la griglia cercando il primo pixel e poi scorrere l'immagine al contrario per trovare l'ultimo.
Ottenuta la griglia, avvio due cicli interni per scorrerla e a ogni quadrato faccio partire un terzo cicli  per controllarne i lati, dato che devono essere controllati k volte.

La parte più lenta è sicuramente il controllo dei lato per verificare se c'è un quadrato ma non trovo tecniche più veloci che mi permettono di superare tutti i test, sebbene seguo tutti i consigli che ho letto nel forum: nella griglia salto di nodo in nodo, controllo se esiste il pixel rosso solo a quello immediatamente adiacente al nodo ed eseguo il controllo solo per la porzione di griglia che ha la possibilità di controllare un quadrato.

Answer 6

Ti conviene trovare prima di tutto la fine della griglia (è un'operazione che non costa praticamente niente e ti rende più efficiente la parte di ricerca dei quadrati).

Dopo di che ti consiglio di fare dei controlli ( per i lati di lunghezza k ) nei quali vedi quali potrebbero essere dei possibili lati in modo da non perdere tempo quando vai a cercare i quadrati

Infine controlli che i possibili lati siano effettivamente parte di dei quadrati.

Questi ultimi due punti possono essere uniti per rendere il tutto più efficiente.

Buon lavoro

Answer 7

Guarda questi topic, sono stati trattati argomenti che ti potranno interessare in quanto inerenti alla tua domanda:

• https://q2a.di.uniroma1.it/14838/aiuto-come-svolgere-hw6?course=hw6obb/homework/fondamenti-di-programmazione-19-20
• https://q2a.di.uniroma1.it/14588/hw6-pixel-verde?course=hw6obb/homework/fondamenti-di-programmazione-19-20
• https://q2a.di.uniroma1.it/14750/hw6-testo-foto10-17871?course=hw6obb/homework/fondamenti-di-programmazione-19-20