Do you need any help?

Notice Board

Per partecipare al corso di Fondamenti di programmazione 2021-22 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 2021-22 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.

VIDEOLEZIONI DEL CORSO DI FONDAMENTI DI PROGRAMMAZIONE AA20-21

PROGRAMMING COURSE VIDEOCONFERENCES AY20-21

Aiuto per “velocizzare” l’hw6

A
AleXio (240 points)
3 4 5
asked Dec 1, 2019 in HW6 obbligatorio by AleXio (240 points)
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
564 views

7 Answers

a
a.pietroluongo (11250 points)
15 38 131
answered Dec 1, 2019 by a.pietroluongo (11,250 points)
edited Dec 1, 2019 by a.pietroluongo
Prova ad iterare sulla griglia e non sull'intera immagine.
The Electrician (800 points)
5 7 11
commented Dec 1, 2019 by The Electrician (800 points)
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.
plm (18850 points)
7 15 118
answered Dec 1, 2019 by plm (18,850 points)
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
l
lucapla3 (650 points)
0 0 9
answered Dec 1, 2019 by lucapla3 (650 points)
edited Dec 1, 2019 by lucapla3
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
c
chiarag (10160 points)
3 5 13
answered Dec 1, 2019 by chiarag (10,160 points)
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.
The Electrician (800 points)
5 7 11
answered Dec 1, 2019 by The Electrician (800 points)
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.
Andrea Sanchietti (3100 points)
4 7 40
answered Dec 1, 2019 by Andrea Sanchietti (3,100 points)
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