[Vari] Contest 5: Sottomatrici

[grigor91]

Originariamente inviato da Vincenzo1968

Ciao Grigor, si, è decisamente interessante! Fammi sapere il titolo del libro quando esce(che evito di comprarlo).

A dire la verità è gia uscito da 15 anni, ho detto futuro perchè sistemi ce l'ho da settembre.
comunque il titolo è :"Affrontare l'Informatica"
autori : Daniela Cappelletti Sandra Frigiolini Luigi Giacchetti
editore: Loescher

Originariamente inviato da DanieleC88

Turing!

Ahh la fretta...

Originariamente inviato da DanieleC88

Ci ha messo appena 35 minuti.

Lettura completata in 2500.54476273 millisecondi. Caricata una matrice 200x200. Inizio la ricerca... completata in 2115368.25458 millisecondi. Risultato: posizione (94, 59) larghezza 56 somma 3185

Considerando che il mio Contest 4 in Python ci ha messo 13 minuti sulla mia macchina e 38 secondi su quella di grigor91, questo mio Contest 5B dovrebbe impiegare sulla sua macchina la bellezza di 1 minuto e 42 secondi. Considerando anche che il Contest 4 tradotto in C sono riuscito a farlo scendere a 4 minuti su questo catorcio, sul PC di grigor91 il Contest 5B dovrebbe arrivare intorno a... 30 secondi.

perchè 200x200? mica era 1000x1000? comunque i miei risultati sono questi:

 Lettura completata in 120.084256519 millisecondi.Caricata una matrice 200x200. Inizio la ricerca... completata in 103166.230345 millisecondi. Risultato: posizione (94, 59) larghezza 56 somma 3185 Script terminated.

Con Psyco i risultati migliorano notevolmente:

Inizio la ricerca... completata in 5039.79835426 millisecondi.Risultato: posizione (94, 59) larghezza 56 somma 3185
Script terminated.

Senza GC i miglioramenti sono minimi:

Inizio la ricerca... completata in 4981.60464528 millisecondi.Risultato: posizione (94, 59) larghezza 56 somma 3185
Script terminated.

[cdimauro]

E' 20 volte più veloce!!!

[DanieleC88]

Lo metto subito a scaricare, anche se so che la maggior parte della colpa non è di Python, ma di questa anticaglia da cui vi scrivo.

Comunque visto che è interessante e poco invasivo, da quel che vedo, lo provo e poi rilancio il programma.

ciao

[Tommo]

Bene. Mi ci sono messo un pò, e ora dichiaro a tutti voi il vostro PWNAGE!

matrix loading, su matrix2.txt (200x200) funzionante richiede.......

3 millisecondi!

Chi ci riesce con phyton gli do la bambolina

Tuttavia c'ha solo un minimo problema, legge le cifre al contrario. Quando avrò tempo vedrò di fixarlo...

[DanieleC88]

Originariamente inviato da cdimauro

E' 20 volte più veloce!!!

È davvero pazzesco, su questo stesso PC di prima mi ha ridotto il tempo di esecuzione da 35 minuti a 4 minuti!

E dal momento che a grigor il tempo viene già così di 5 secondi, voglio provare una modifica che evita un pochino di cicli inutili. Se poi ho tempo lo traduco anche in C e vedo fin dove lo posso spingere.

Originariamente inviato da Tommo

matrix loading, su matrix2.txt (200x200) funzionante richiede.......

3 millisecondi!

EDIT: avevo capito male io...

[DanieleC88]

Aggiornamento: ho spremuto ancora un po' il codice, da 4 minuti sono sceso a poco più di 2 minuti sulla mia macchina:

Lettura completata in 1204.76541679 millisecondi.
Caricata una matrice 200x200.
Inizio la ricerca... completata in 128279.977036 millisecondi.

Risultato: posizione (94, 60) larghezza 56 somma 3185

Se la velocità è raddoppiata anche sul PC di grigor91, sono intorno ai 2.6 secondi.
Psyco è davvero forte.

[WarDuck]

Ci siamo finalmente, sono stato un po' tardo, ma per il 1° punto sembra che tutto finalmente vada per il verso giusto.

Ecco il codice (ho escluso la parte del caricamento da file) in C#:

static int findSub(int[,] mat) {
            int p = 0;
            int next_i = 0;
            int next_j = 0;
            int max_i = 0;
            int max_j = 0;
            int max = 0;

            for (int i = 0; i < dim - 1; i++) {
                for (int j = 0; j < dim - 1; j++) {

                    if (mat[i, j] == 0) {
                        next_i = i;
                        next_j = j;
                        p = 1;
                        for (int k = p - 1; k >= 0 && k <= dim && i < dim - 1 && j < dim - 1; k--) {
                            if (mat[i - k, j + 1] == 0 && mat[i + 1, j - k] == 0) {
                                if (k == 0 && mat[i + 1, j + 1] == 0) {
                                    i++;
                                    j++;
                                    k = ++p;
                                }
                            } else break;
                        }
                        i = next_i;
                        j = next_j;
                        if (p > max) {
                            max = p;
                            max_i = next_i;
                            max_j = next_j;
                        }
                    }
                }
            }
            Console.WriteLine("Max dimension found: " + max + " at index (" + max_i + ", " + max_j + ")");
            // viewMatrix(mat, max_i, max_j, max);
            return max;
        }

Ecco l'output:

Matrix dimensions: 1000
Max dimension found: 10 at index (110,257)
Elapsed: 26,7577ms

[VICIUS]

Giuro che questa è l'ultima versione del primo punto che posto. Tempo impiegato circa 1/3 della precedente

require 'tools'

def min(a,b,c)
  a < b ? a < c ? a : c : b < c ? b : c
end

def contest5a(matrix)
  best = best_row = best_col = 0
  
  c = r = matrix.size - 1
  while c >= 0 do
    matrix[r][c] = matrix[r][c] == 0 ? 1 : 0
    c -= 1
  end
  
  c = r = matrix.size-1
  while r >= 0 do
    matrix[r][c] = matrix[r][c] == 0 ? 1 : 0
    r -= 1
  end
  
  c = r = matrix.size - 2
  while r >= 0 do
    while c >= 0 do
      matrix[r][c] = matrix[r][c] == 0 ? 1 + min(matrix[r+1][c], matrix[r][c+1], matrix[r+1][c+1]) : 0
      if matrix[r][c] > best
        best, best_row, best_col = matrix[r][c], r, c
      end
      c -= 1
    end
    c = matrix.size - 2
    r -= 1
  end
  
  return "best:#{best}  row:#{best_row}  col:#{best_col}"   
end

test_function :contest5a, 'Matrix1.txt'

mirco@Macintosh:Contest5> ruby contest-a.rb 
carico la matrice... fatto (1.064655 secondi)
trovo la sottomatrice... fatto (0.611063 secondi)
best:10  row:110  col:257

[VICIUS]

Originariamente inviato da Tommo

3 millisecondi!

Chi ci riesce con phyton gli do la bambolina

Tuttavia c'ha solo un minimo problema, legge le cifre al contrario. Quando avrò tempo vedrò di fixarlo...

require 'tools.rb'


start = Time.now()
matrix = fast_load_matrix()
puts "Carico la matrice.... ok. (" + (Time.now - start).to_s + " secondi)"

mirco@Macintosh:Contest5> ruby prova.rb 
Carico la matrice.... ok. (0.000311 secondi)

Aspetto la bambolina

[DanieleC88]

Ah ma lui intendeva il solo caricamento! Pensavo la ricerca, LOL.

E comunque quello non è Python...

[VICIUS]

Originariamente inviato da DanieleC88

Ah ma lui intendeva il solo caricamento! Pensavo la ricerca, LOL.

E comunque quello non è Python...

Ruby è più lento di Python quindi la mia soluzione vale ancora di più.

[DanieleC88]

Originariamente inviato da VICIUS

Giuro che questa è l'ultima versione del primo punto che posto. Tempo impiegato circa 1/3 della precedente

Solo un dubbio: sbaglio o modifichi la matrice? (è ammessa la modifica?)

[VICIUS]

Originariamente inviato da DanieleC88

Solo un dubbio: sbaglio o modifichi la matrice? (è ammessa la modifica?)

Penso di si. Al massimo si può allocare una matrice di appoggio su cui scrivere. La memoria richiesta raddoppia e le prestazioni ridursi di pochissimo per via di qualche cache miss in più.

[DanieleC88]

Portata in C anche la soluzione al secondo punto:

Lettura completata in 380 millisecondi.
Inizio la ricerca...
Ricerca completata in 21.42000 secondi.

Sottomatrice quadrata di somma massima:
	-> index: 12094
	-> side: 56
	-> sum: 3185

Devo stampare il sottoquadrato (94; 60)-(150; 116).
[...]

Sul PC di grigor91 la versione Python, che da me impiegava 4 minuti, girava in 5 secondi, questa dovrebbe essere più veloce, anche considerando che al momento uso TCC come compilatore, quindi l'eseguibile non dovrebbe nemmeno essere ottimizzato.

Per comodità allego un file .zip con le soluzioni, postarle qui occuperebbe troppo spazio.

[banryu79]

Originariamente inviato da VICIUS

Giuro che questa è l'ultima versione del primo punto che posto. Tempo impiegato circa 1/3 della precedente
[...cut...]

Bello è migliorata molto anche la "strutturazione" del codice e il suo valore estetico (almeno a me piace molto: non saprei bene come spiegarlo a parole però la sensazione che ho al colpo d'occhio è che ci sia una "bella ritmica". Certo questo non è direttamente correlato alla logica dell'algortimo, ed è soggettivo)
Bravo Vicius!

[Vincenzo1968]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <time.h>

#define BUFFER_SIZE 4096

typedef enum tagStati
{
	S_ERROR = -1, S0, S1, S2
} Stati;

int GetArraySize(const char *szFileName)
{
	int array_size;
	FILE *fp;
	char buffer[BUFFER_SIZE + 1];
	int numread;
	int k;
	char c;

	fp = fopen(szFileName, "rb");
	if ( fp == NULL )
	{
		printf("Errore nell'apertura del file %s\n", szFileName);
		return S_ERROR;
	}

	numread = fread(buffer, 1, BUFFER_SIZE, fp);
	if (numread == 0)
	{
		fclose(fp);
		printf("Errore 4 nella lettura del file %s\n", szFileName);
		return S_ERROR;
	}
	*(buffer + numread + 1) = '\0';

	k = 0;
	c = *(buffer + k);
	array_size = 0;
	while ( c != '\n' )
	{
		if ( c >= '0' && c <= '9' )
		{
			array_size = array_size * 10 + c - '0';

		}
		c = *(buffer + k++);
	}

	fclose(fp);

	return array_size;
}

Stati DFA(const char *szFileName, int **a, int array_size)
{
	Stati stato = S0;
	FILE *fp;
	unsigned char buffer[BUFFER_SIZE + 1];
	int numblocks;
	int numread;
	char c;
	int k, x;
	int riga, colonna;
	int num;
	int segno;

	fp = fopen(szFileName, "rb");
	if ( fp == NULL )
	{
		printf("Errore nell'apertura del file %s\n", szFileName);
		return S_ERROR;
	}

	if ( fseek(fp, 0, SEEK_END) )
		return 0;

	numblocks = ftell(fp)/BUFFER_SIZE;
	if ( numblocks == 0 )
	{
		numblocks = 1;
	}
	else
	{
		if ( ftell(fp) % BUFFER_SIZE != 0 )
			numblocks++;
	}

	fseek(fp, 0, SEEK_SET);
	numread = fread(buffer, 1, BUFFER_SIZE, fp);
	if (numread == 0)
	{
		fclose(fp);
		printf("Errore 1 nella lettura del file %s\n", szFileName);
		return S_ERROR;
	}

	k = 0;
	c = *(buffer + k++);
	while ( c != '\n' )
	{
		if (c == '\0')
		{
			printf("Errore 2 nella lettura del file.\n");
			fclose(fp);
			return S_ERROR;
		}
		c = *(buffer + k++);
	}

	riga = colonna = 0;
	num = 0;
	x = 0;
	while ( x < numblocks )
	{
		c = *(buffer + k++);

		switch ( stato )
		{
		case S0:
			segno = 1;
			if ( c >= '0' && c <= '9' )
			{
				num = c - '0';
				stato = S1;
			}
			else if ( c == '-' )
			{
				num = 0;
				stato = S2;
			}
			else if ( c == '\r' )
			{
			}
			else if ( c == '\n' )
			{
				colonna = 0;
				riga++;
				if (riga >= array_size)
					return stato;
			}
			else
			{
				printf("Automa: Stato S0 errore sul carattere -> '%c' k -> %d\n", c, k);
				return S_ERROR;
			}
			break;
		case S1:
			if ( c >= '0' && c <= '9' )
			{
				num = num * 10 + c - '0';
			}
			else if ( c == ' ' )
			{
				a[riga][colonna] = num * segno;
				num = 0;
				colonna++;
				stato = S0;
			}
			else 
			{
				printf("Automa: Stato S1 errore sul carattere -> '%c'\n", c);
				return S_ERROR;
			}
			break;
		case S2:
			if ( c >= '0' && c <= '9' )
			{
				num = c - '0';
				segno = -1;
				stato = S1;
			}
			else 
			{
				printf("Automa: Stato S2 errore sul carattere -> '%c'\n", c);
				return S_ERROR;
			}
			break;
		}

		if ( k >= BUFFER_SIZE )
		{
			numread = fread(buffer, 1, BUFFER_SIZE, fp);
			if (numread == 0)
			{
				fclose(fp);
				printf("Errore 3 nella lettura del file %s\n", szFileName);
				return S_ERROR;
			}
			k = 0;
			x++;
		}
	}

	fclose(fp);

	return stato;
}

int main()
{
	clock_t c_start, c_end;
 
	int **m;
	int x, y, k;
	int array_size;
	Stati stato;
	char *szFileName = "matrix2.txt";

	int riga, colonna;
	int dim;
	int somma;

	int riga2, colonna2;

	int riga_temp, colonna_temp;
	int dim_temp;
	int somma_temp;

	c_start = clock();

	array_size = GetArraySize(szFileName);
	if ( array_size <= 0 )
		return;

	m = (int**)malloc(sizeof(int*)*array_size);
	if ( m != NULL )
	{
		for ( x = 0; x < array_size; x++ )
		{
			m[x] = (int*)malloc(sizeof(int)*array_size);
			if ( m[x] == NULL )
			{
				printf("Memoria insufficiente.\n");
				return S_ERROR;
			}
		}
	}
	else
	{
		printf("Memoria insufficiente.\n");
		return S_ERROR;
	}

	stato = DFA(szFileName, m, array_size);
	if ( stato == S_ERROR )
	{
		printf("L'automa ha restituito un errore.\n");
		return;
	}

	c_end = clock();
	printf("\nTempo impiegato per la lettura del file -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

	c_start = clock();

	x = y = 0;
	while ( x < array_size - x && y < array_size - y )
	{
		somma = somma_temp = 0;
		dim = array_size/2;
		while ( dim > 1 )
		{
			for ( riga = y; riga <= y + dim; riga++ )
			{
				for ( colonna = x; colonna <= x + dim; colonna++ )
				{
					somma += m[riga][colonna];
				}
				if ( somma > somma_temp )
				{
					riga_temp = riga - dim;
					colonna_temp = colonna - dim;
					dim_temp = dim;
					somma_temp = somma;
				}
			}
			somma = 0;
			--dim;
		}
		x++;
		y++;
	}

	riga = riga_temp - 1;
	colonna = colonna_temp - 1;
	dim = dim_temp + 1;
	k = 0;
	somma = somma_temp;
	while ( riga >= 0 )
	{
		y = riga--;
		x = colonna--;

		for ( k = 0; k < dim; k++ )
		{
			somma += m[y][x+(k+1)];

			if ( somma > somma_temp )
			{
				riga_temp = riga;
				colonna_temp = colonna;
				dim_temp = dim;
				somma_temp = somma;
			}
		}
		dim++;
	}

	riga = riga_temp + 1;
	colonna = colonna_temp + 1;
	dim = dim_temp;
	somma = 0;

	for ( y = riga; y <= riga + dim; y++ )
	{
		for ( x = colonna; x <= colonna + dim; x++ )
		{
			somma += m[y][x];
		}
	}

	if ( somma > somma_temp )
	{
		riga_temp = riga;
		colonna_temp = colonna;
		dim_temp = dim;
		somma_temp = somma;
	}

	c_end = clock();

	printf("\nRiga       -> %d\nColonna    -> %d\nDimensione -> %d\nSomma      -> %d\n", riga_temp, colonna_temp, dim_temp, somma_temp);

	printf("\nTempo impiegato per la ricerca -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

	for ( x = 0; x < array_size; x++ )
		free(m[x]);
	free(m);

	return 0;
}

[WarDuck]

Incredibile Complimenti Vincenzo... io ancora sto cercando di capire perché non funziona sulla matrice grande (o meglio non mi tornano i vostri risultati), con una matrice di prova 4x4 funziona (anche logicamente sembra) ma con quella da usare no.

In sostanza parto dall'origine (0,0) sommando tutti gli elementi della 2x2 dopodiché vi aggiungo quelli della 3x3, poi quelli della 4x4 e così via facendo sempre confronti col massimo attuale... poi cambio posizione (0,1), (0,2) e così via...

[DanieleC88]

Originariamente inviato da Vincenzo1968

Tu mi fai paura.

A parte scherzi, ottimo risultato.
Già che ci sei proveresti anche a lanciare la mia soluzione per il punto? Sono curioso di vedere quanto tempo impiega su un computer degno di tale nome.

ciao

[DanieleC88]

Comunque, sbaglio io o la sottomatrice è 56x56, e non 55x55? Ho visto l'output stampato dal mio programma (che è 56x56) una volta terminata la ricerca e sommando i numeri mi viene effettivamente 3185...

[Tommo]

Originariamente inviato da VICIUS

require 'tools.rb'


start = Time.now()
matrix = fast_load_matrix()
puts "Carico la matrice.... ok. (" + (Time.now - start).to_s + " secondi)"

mirco@Macintosh:Contest5> ruby prova.rb 
Carico la matrice.... ok. (0.000311 secondi)

Aspetto la bambolina

"Ma questo è un mostro" (cit.)

Beh davvero complimenti... lo sospettavo che le versioni migliori sarebbero uscite più in là...
cmq come diavolo hai fatto? Io ho tolto qualsiasi cosa, cioè la conversione in float la faccio con un elenco di else if
Dev'essere iostream che non è esattamente velocissimo. Magari una macchina a stati andrebbe di più. Peccato che non abbia idea di come si fa

Cmq niente bambolina, l'hai fatto in Ruby, non in Phyton