Test HW6REC non eseguiti correttamente?

m
mattia.regina (190 points)
0 2 4
asked Jun 17, 2020 in Recupero HW6 by mattia.regina (190 points)
Buonasera,

da stamattina sto caricando diverse versioni dell'HW6 di recupero ottenendo però sempre la stessa valutazione e passando sempre solo 4 test (gli altri vanno in timeout). Però se testo il programma sul mio PC supero tutti i test in circa 5.5 secondi, quindi senza problemi di timeout. A questo punto non so come risolvere questa problematica.

Vi ringrazio in anticipo per la disponibilità
167 views

3 Answers

Tommaso Sgroi (12990 points)
6 11 91
answered Jun 17, 2020 by Tommaso Sgroi (12,990 points)
Probabilmente il tuo pc è più veloce e potente della VM su cui vengono eseguiti i test.
EffeGi (1530 points)
0 1 5
answered Jun 17, 2020 by EffeGi (1,530 points)
Nell'esercizio è indicato il timeout di 1 secondo per test, quindi controlla quanto impiega ciascun test sul pc.

Non vedere il tempo totale, basta che siano 1 millisecondo più lento a test per andare in timeout e non passare. Ad esempio i miei primi 4 test sono sotto i 100ms e i restanti a circa 750ms (per avere un riferimento) e non ho avuto problemi.

Ottimizza il codice per tenerti un pò di tempo extra per il calcolo sulla macchina virtuale.
m
mattia.regina (190 points)
0 2 4
commented Jun 17, 2020 by mattia.regina (190 points)
Ho controllato ora un po' di volte e solo gli ultimi due test ci mettono circa 900ms, mentre i restanti da 750ms in giù. Se non passassi solo gli ultimi due lo capirei, ma 4 su 10 mi sembra strano.

Per quanto riguarda l'ottimizzazione hai pienamente ragione, ma ora come ora non mi viene in mente altro da migliorare
EffeGi (1530 points)
0 1 5
commented Jun 17, 2020 by EffeGi (1,530 points)
Se ci illustri la tua implementazione, possiamo vedere cosa si può ottimizzare. Che idea di fondo hai adottato e che strutture hai applicato?

A parte i soliti consigli di utilizzo di set() invece che list() laddove possibile e referenziare i dati in un dizionario,  controlla il codice per non fare o cose superflue o cose ripetute più volte!
m
mattia.regina (190 points)
0 2 4
commented Jun 18, 2020 by mattia.regina (190 points)
Allora, la funzione carica l'immagine e apre in scrittura il file di testo, inizializza a zero tutte le variabili necessarie. In seguito con un WHILE  (con la condizione che la variabile y sia diversa dal numero di righe) inizio a scorrere i valori della matrice. Il primo IF  verifica se il valore in quel punto della matrice sia uguale o a se' stesso o al nero.

Se almeno una delle due condizioni risulta vera, x (variabile riferita al numero di colonne) viene incrementata di 1 ( un altro IF verifica che x sia diversa dal numero di colonne, se risulta vero allora x viene associata al valore della x del vertice in alto a sinistra (all'inizio 0 quindi) e y viene incrementata di 1).

Se almeno una delle due condizioni risulta falsa, si passa all'ELSE che associa la variabile colore al valore della matrice in quel punto, aggiunge il colore all'insieme z (che contiene inizialmente solo il nero) , memorizza le coordinate del vertice in alto a sinistra e incrementa un contatore. Con i due WHILE successivi trovo la x del vertice in alto a destra e la y del vertice in basso a sinistra. Memorizza questi due valori come le coordinate del vertice in basso a destra, scrive su file il tutto e associo a x la x del vertice in basso a destra e a y la y del vertice in alto a sinistra. Ricomincia il primo WHILE.

Una volta finito tutto, chiudo il file di testo e ritorno il contatore
EffeGi (1530 points)
0 1 5
commented Jun 18, 2020 by EffeGi (1,530 points)
Perchè imponi che la variabile y (che presumo scorra lungo le colonne) deve essere diversa dal numero di righe?

Io mi sono concentrato sulla ricerca dei vertici dei rettangoli, ovvero quei punti in cui i pixel adiacenti (a croce) sono almeno 2 diversi dal colore del rettangoli. Questi punti sono stati messi in un dizionario con colori come chiavi e poi tra tutti ho scelto i minimi (x,y) e massimi (x,y) per trovare i vertici opposti.

Così non ho utilizzato alcun WHILE e ho scansionato la lista di liste una sola volta
m
mattia.regina (190 points)
0 2 4
commented Jun 18, 2020 by mattia.regina (190 points)
Molto interessante il modo in cui l'hai fatto, non ci avevo pensato. Comunque sia y è la variabile associata alle righe, quindi ponendola diversa da len(numero di righe) il ciclo finisce nel momento in cui l'immagine non ha più pixel da controllare.
EffeGi (1530 points)
0 1 5
commented Jun 18, 2020 by EffeGi (1,530 points)
Ho capito l'utilizzo del ciclo while per scorrere all'interno dell'immagine, ma credo che con gli altri due cicli aumenti molto la complessità dell'algoritmo e potrebbe essere la causa del fallimento dei test...

Il mio consiglio è di ridurre ad una sola scansione dei prixel, essendo rettangoli sovrapposti in modo ortogonale, possono assumere solo determinate configurazioni e questo gioca a tuo vantaggio per limitare i casi di ricerca dei vertici.

Tieni sempre a mente che il programma esegue una scansione a righe (o colonne) quindi il pixel "passato" può darti informazione in merito al "nuovo" pixel, ossia se è un colore diverso o già visto.
andrea.sterbini (172780 points)
513 935 1789
answered Jun 17, 2020 by andrea.sterbini (172,780 points)
Penso che debba essere migliorata l'efficienza. La VM è un po' più lenta del tuo PC.
m
mattia.regina (190 points)
0 2 4
commented Jun 18, 2020 by mattia.regina (190 points)
Guardando i tempi dei test della VM e quelli sul mio PC c'è una differenza di circa 300ms. Per adesso non passo solo l'ultimo test sulla VM, però gli ultimi 3 sono comunque molto borderline come tempistiche. Continuerò a migliorare il programma come mi consiglia, grazie mille