[Vari] Contest 5: Sottomatrici

[DanieleC88]

Originariamente inviato da Vincenzo1968

E il bello è che utilizzando un automa a stati finiti, al posto della scanf, si scende sotto il decimo di secondo anche per leggere la matrice dal file.

Cioè circa 3 volte più veloce? Cavoli, non pensavo che la scanf() avesse un tale impatto.

Come no, posta pure che è interessante.

[DanieleC88]

Tra l'altro ho appena escogitato una possibile soluzione al secondo punto del problema, ma ho ancora un po' di dubbi sulla sua efficienza. Appena posso butto giù del codice e incrocio le dita.

[cdimauro]

Originariamente inviato da DanieleC88

Cioè circa 3 volte più veloce? Cavoli, non pensavo che la scanf() avesse un tale impatto.

Mi sembra normale: scanf è una soluzione "generica", mentre l'automa a stati finiti è una soluzione "custom".

[Vincenzo1968]

In ritardo(causa condivisione dell'unico portatile tra parenti e amici ) ma ecco il codice.

Nella macchina menzionata nel post precedente, impiega 0.02400 secondi.

#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
} 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;

	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:
			num = 0;
			if ( c >= '0' && c <= '9' )
			{
				num = c - '0';
				stato = S1;
			}
			else if ( c == '-' )
			{
				c = *(buffer + k++);
				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;
					c = *(buffer + k++);
					x++;
				}
				else if ( c < '0' || c > '9' )
				{
					printf("Automa: Stato S0 errore sul carattere -> '%c'\n", c);
					return S_ERROR;
				}
				num = (c - '0') * -1;
				stato = S1;
			}
			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;
				num = 0;
				colonna++;
				stato = S0;
			}
			else if ( c == '-' )
			{
				k--;
				stato = S0;
			}
			else 
			{
				printf("Automa: Stato S1 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 x;
	int **m;
	int array_size;
	Stati stato;

	c_start = clock();

	array_size = GetArraySize("matrix1.txt");
	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("matrix1.txt", m, array_size);
	if ( stato == S_ERROR )
	{
		printf("L'automa ha restituito un errore.\n");
		return -1;
	}

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

	printf("\ngli ultimi dieci elementi  della matrice:\n");
	for ( x = 989; x < 1000; x++ )
		printf("m[999][%d] -> %d\n", x, m[999][x]);
	printf("\n");

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

	return 0;
}

[Vincenzo1968]

Originariamente inviato da DanieleC88

Tra l'altro ho appena escogitato una possibile soluzione al secondo punto del problema, ma ho ancora un po' di dubbi sulla sua efficienza. Appena posso butto giù del codice e incrocio le dita.

E io, non avendo intenzione di passare il resto delle ferie a programmare, vi leggo e faccio il tifo per te(e per il linguaggio C ).

[cdimauro]

Originariamente inviato da DanieleC88

Tra l'altro ho appena escogitato una possibile soluzione al secondo punto del problema, ma ho ancora un po' di dubbi sulla sua efficienza. Appena posso butto giù del codice e incrocio le dita.

Puoi sempre modellare velocemente la soluzione, testarne la consistenza, e poi pensare a velocizzarla.

[ercand]

Originariamente inviato da cdimauro

Mi sembra normale: scanf è una soluzione "generica", mentre l'automa a stati finiti è una soluzione "custom".

Salve a tutti, volevo partecipare ( o almeno provare ) ma vedo che voi siete anni luce avanti a me, ad esempio questo "automa a stati finiti" in cosa consiste?

Grazie.

[ndakota]

Originariamente inviato da ercand

Salve a tutti, volevo partecipare ( o almeno provare ) ma vedo che voi siete anni luce avanti a me, ad esempio questo "automa a stati finiti" in cosa consiste?

Grazie.

lo stesso per me.. io in java mi sono bloccato al caricamento della matrice da file

[DanieleC88]

Originariamente inviato da cdimauro

Mi sembra normale: scanf è una soluzione "generica", mentre l'automa a stati finiti è una soluzione "custom".

Questo lo so, e infatti mi aspettavo che la lettura "manuale" fosse più rapida, però la scanf(), a parte l'interpretazione della stringa di formato, un cast e poco altro, cosa fa in più oltre a leggere il numero? Non mi aspettavo che ci impiegasse 3 volte (anzi, anche di più a vedere dal risultato che ha postato ora Vincenzo ) il tempo normalmente necessario.

Originariamente inviato da Vincenzo1968

In ritardo(causa condivisione dell'unico portatile tra parenti e amici ) ma ecco il codice.

Nella macchina menzionata nel post precedente, impiega 0.02400 secondi.

[...]

Mamma mia, sia per il risultato che per la quantità di codice: gugoXX ha ragione, devi essere un amanuense.

Originariamente inviato da Vincenzo1968

E io, non avendo intenzione di passare il resto delle ferie a programmare, vi leggo e faccio il tifo per te(e per il linguaggio C ).

Grazie, proverò a fare del mio meglio

Originariamente inviato da cdimauro

Puoi sempre modellare velocemente la soluzione, testarne la consistenza, e poi pensare a velocizzarla.

Ovvero... provarla in Python?
Be' sì, perché no?

Originariamente inviato da ercand

Salve a tutti, volevo partecipare ( o almeno provare ) ma vedo che voi siete anni luce avanti a me, ad esempio questo "automa a stati finiti" in cosa consiste?

Grazie.

Tranquillo, posta la soluzione senza problemi (l'ultima soluzione che ho postato io ci metteva 13 minuti ).

Un automa a stati finiti è un modello di macchina che reagisce a degli input portandosi da uno stato iniziale ad uno stato finale e dando determinati output (diversi a seconda degli stati di destinazione o delle transizioni effettuate). Almeno io è così che la conosco per quel poco che ho fatto, se vuoi maggiori dettagli su come implementarle in C rivolgiti a Vincenzo che saprà consigliarti letture utili.

[Vincenzo1968]

Originariamente inviato da ercand

Salve a tutti, volevo partecipare ( o almeno provare ) ma vedo che voi siete anni luce avanti a me, ad esempio questo "automa a stati finiti" in cosa consiste?

Grazie.

Ciao ercand,

come prima cosa volevo incoraggiarti(anzi, incoraggiarvi; l'invito è rivolto anche a ndakota) a partecipare ugualmente. L'accento è posto sugli algoritmi e non sulla velocità di esecuzione; non è detto quindi che il tuo algoritmo non possa risultare interessante.

Per quanto riguarda gli automi a stati finiti puoi vedere questo mio articolo e, se sei particolarmente interessato, ti consiglio caldamente questo libro:

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
Automi, linguaggi e calcolabilità
ADDISON-WESLEY

Non lasciarti impressionare dalle definizioni matematiche. È più facile a farsi che a dirsi. Nel senso che, anche non possedendo elevate nozioni matematiche, l'implementazione di un automa a stati finiti è davvero molto semplice(se ci sono riuscito io col mio misero diploma di ragioniere...).

P.S.
ndakota, c,è un accenno agli automi a stati finiti anche sul Cormen(capitolo 32, 'string matching')

[grigor91]

[OT]
E' interessante notare come il mio futuro libro di sistemi riesca a trattare la macchina di Touring senza citare gli automi a stati finiti
[/OT]

[NickerX]

La prima riga di ogni file indica la dimensione della matrice giusto??
Quindi per il primo esercizio la matrice è 1000 * 1000 vero??

Scusate le domande banali!!

[Vincenzo1968]

Originariamente inviato da NickerX

La prima riga di ogni file indica la dimensione della matrice giusto??
Quindi per il primo esercizio la matrice è 1000 * 1000 vero??
...

Ciao Nicher,

giusto, si. Si tratta di una matrice 1000x1000.

Originariamente inviato da grigor91

E' interessante notare come il mio futuro libro di sistemi riesca a trattare la macchina di Touring senza citare gli automi a stati finiti

Ciao Grigor,
si, è decisamente interessante!
Fammi sapere il titolo del libro quando esce(che evito di comprarlo).
Ho postato quel codice non perché voglia dimostrare chissà cosa, ma perché lo ritengo interessante. Anche se l'esercizio specifica che i tempi di lettura dal file non debbono rientrare nel computo, nella vita reale uno non si può presentare dal cliente e dirgli: "l'algoritmo di ricerca è velocissimo; tuttavia, il programma impiega mezz'ora di tempo a causa della lettura del file".

[ercand]

Per ho scritto il codice per memorizzare la matrice, questo è il codice

// Contest5.cpp : Defines the entry point for the console application.
//

#include <Windows.h>
#include <stdio.h>
#include <stdlib.h>
#include <fstream>
#include <iostream>
#include <ctime>



#define SRCFILE "Matrix1.txt"
#define FILEBUFER 4096

int matrixSize = 1000;
char matrix[1000][1000];

bool OpenContestFile(char* pFileName)
{
	char buffer[FILEBUFER + 1];

	std::ifstream inputFile;
	inputFile.open(pFileName);

	if (inputFile.fail())
	{
		printf("Impossibile aprire il file %s", pFileName);
		return false;
	}

	
	inputFile.getline(buffer, FILEBUFER, '\n');

/*	int lenghtFirstLine = inputFile.tellg();
	
	std::string textRecord;
	textRecord.insert(0, buffer + 2, lenghtFirstLine - 4);
	matrixSize = atoi(textRecord.c_str());*/
	matrixSize = atoi(buffer+1);


	// Legge tutti i valori della matrice
	int Row = 0;
	char* tempBuffer;
	
	while (inputFile.eof() == false)
	{
		inputFile.getline(buffer, FILEBUFER, '\n');
		tempBuffer = buffer;


		for (int i = 0; i < matrixSize; i++)
		{
			matrix[Row][i] = atoi(tempBuffer);

			while ((*tempBuffer >= '0' && *tempBuffer <= '9') || *tempBuffer == '-')
			{
				++tempBuffer;
			}
		//	if (*tempBuffer == ' ' && *tempBuffer != '\n' && *tempBuffer != '\r')
			{
				++tempBuffer;
			}
		}
		++Row;
	}

	inputFile.clear();
	inputFile.close();

	return true;
}
int main()
{
	clock_t t1;
	clock_t t2;

	// Lettura file
	t1 = clock();
	bool staus = OpenContestFile(SRCFILE);
	t2 = clock();

	char text[512];
	sprintf(text, "Lettura file completata in %5.5f secondi", float(t2-t1) / CLOCKS_PER_SEC);
	OutputDebugStr(text);

	return 0;
}

E' scritto con visual studio 2008, compilato in modalità release impiega tra i 0.04300 e i 0.05200 secondi a caricare la matrice.
Pensavo peggio , son soddisfatto.

[gugoXX]

Provo a gettare una prima soluzione per il punto 2.
Completamente funzionale

Coordinate: 94,60 - Dimensione 55 - Somma 3185
Time: 8529ms
Test: 3185

Ho evidenziato in BLU il cuore, l'algoritmo di ricerca vero e proprio.

class Program
{
    static void Main(string[] args)
    {            
        Matrix mat = new Matrix("Matrix2.txt");
        Stopwatch sw = new Stopwatch();
        sw.Start();
        var toprint = mat.Ex2();
        sw.Stop();
        Console.WriteLine("Coordinate: {0},{1}   - Dimensione {2}   - Somma {3}", toprint.Coords.x, toprint.Coords.y, toprint.Coords.z, toprint.val);
        Console.WriteLine("Time: {0}ms", sw.ElapsedMilliseconds);

        int x=toprint.Coords.x;
        int y=toprint.Coords.y;
        int z=toprint.Coords.z;

        int test = (from yy in Enumerable.Range(y, z+1)
                    from xx in Enumerable.Range(x, z+1)
                    select mat.Mat[xx, yy]).Sum();
        Console.WriteLine("Test: {0}", test);

        Console.ReadKey();
    }
}

public class Matrix
{
    public int Dim;
    public int[,] Mat;

    public void Save(string fname)
    {
        StreamWriter sw = new StreamWriter(@"C:\temp\" + fname);            
        sw.WriteLine("--{0}--", Dim);
        for (int y = 0; y < Dim; y++)
        {
            for (int x = 0; x < Dim; x++)
            {
                sw.Write("{0} ", Mat[x, y].ToString());
            }
            sw.WriteLine();
        }
        sw.Close();
    }

    public Matrix(string fname)
    {
        Load(fname);
    }

    public Matrix(int[,] vals)
    {
        Mat = vals;
        Dim = vals.GetLength(0);
    }

    public void Load(string fname)
    {
        StreamReader sr = new StreamReader(@"C:\temp\" + fname);
        string fline = sr.ReadLine();
        string mds = fline.Substring(2, fline.Length - 4);
        Dim = int.Parse(mds);
        Mat = new int[Dim, Dim];
        for (int y = 0; y < Dim; y++)
        {
            string line = sr.ReadLine();
            string[] valss = line.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
            var valis = valss.Select(t => int.Parse(t)).ToArray();
            Enumerable.Range(0, Dim).ForAll(x => Mat[x, y] = valis[x]);
        }
        sr.Close();            
    }        

    public struct CoordsStruct
    {
        public int x;
        public int y;
        public int z;
        public CoordsStruct(int ix, int iy, int iz)
        {
            x = ix;
            y = iy;
            z = iz;
        }
    }

    public struct Ex2Result
    {                        
        public CoordsStruct Coords;
        public int val;

        public Ex2Result(CoordsStruct ics,int ival)
        {
            Coords = ics;
            val = ival;
        }
    }

    public Ex2Result Ex2()
    {            
        int parsum = 0;
        var domgrp =  from y in Enumerable.Range(0, Dim)
                      from x in Enumerable.Range(0, Dim)
                      let min = Math.Min(Dim - y, Dim - x)                          
                      from z in Enumerable.Range(1, min - 1)
                      select new Ex2Result(
                             new CoordsStruct(x,y,z),
                             parsum = (z == 1 ? Mat[x, y] : parsum) + Mat[x + z, y + z] +
                                    (from t in Enumerable.Range(0, z)
                                     select Mat[x+t,y+z]+Mat[x+z,y+t]).Sum()
                      );
              
        var orig = from y in Enumerable.Range(0, Dim)
                   from x in Enumerable.Range(0, Dim)
                   select new Ex2Result(new CoordsStruct(x, y, 0), Mat[x, y]);

        var complete = domgrp.Concat(orig);
                                                                  
        Ex2Result res = complete.Max(t => t.val);
        return res;
    }
}

public static class Extensor
{
    public static void ForAll<T>(this IEnumerable<T> domain,Action<T> act)
    {
        foreach (T t in domain) act(t);
    }

    public static T Max<T, U>(this IEnumerable<T> domain, Func<T, U> elem) where U:IComparable<U>
    {
        T CurmaxRow = default(T);
        U CurMax=default(U);
        foreach (T t in domain)
        {
            U CurVal=elem(t);
            if (CurVal.CompareTo(CurMax) > 0)
            {
                CurmaxRow = t;
                CurMax = CurVal;
            }
        }
        return CurmaxRow;
    }
}

[cdimauro]

Originariamente inviato da DanieleC88

Questo lo so, e infatti mi aspettavo che la lettura "manuale" fosse più rapida, però la scanf(), a parte l'interpretazione della stringa di formato, un cast e poco altro, cosa fa in più oltre a leggere il numero? Non mi aspettavo che ci impiegasse 3 volte (anzi, anche di più a vedere dal risultato che ha postato ora Vincenzo ) il tempo normalmente necessario.

Io sì e, anzi, pensavo si guadagnasse qualcosa di più.

Considera che un automa a stati finiti fa veramente "il minimo indispensabile", mentre la scanf ha numerosi controlli in più che esegue sempre.

Ovvero... provarla in Python?

Matteo 26,25

"Tu l'hai detto."

Be' sì, perché no?

"Make it work, make it right, make it fast" - Kent Beck

[Vincenzo1968]

Ho snellito un po' il codice dell'automa con l'aggiunta di uno stato che rende più agevole la gestione dei numeri negativi:

#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 x;
	int **m;
	int array_size;
	Stati stato;
	char *szFileName = "matrix1.txt";

	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;
	}

	//c_start = clock();

	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);

	printf("\ngli ultimi dieci elementi  della matrice:\n");
	for ( x = array_size - 10; x < array_size; x++ )
		printf("m[%d][%d] -> %d\n", array_size - 1, x, m[array_size - 1][x]);
	printf("\n");

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

	return 0;
}

[DanieleC88]

Originariamente inviato da grigor91

[OT]
E' interessante notare come il mio futuro libro di sistemi riesca a trattare la macchina di Touring senza citare gli automi a stati finiti
[/OT]

Turing!

[DanieleC88]

Comunque alla fine ho tradotto in Python l'idea che avevo, ma sembra dannatamente lenta...
In fondo era solo un metodo "velocizzato" per analizzare tutti i possibili sottoquadrati, ma l'ho lanciato oltre venti minuti fa ed è ancora lì che gira, quindi non so se vale la pena di tradurlo anche in C: dubito di riuscire anche lontanamente a raggiungere gugoXX, pure su un computer serio.
Magari dopo provo a farlo lo stesso e vediamo che schifezza ne esce fuori.

ciao

EDIT: come non detto, ha appena finito...
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, 60) larghezza 56 somma 3185

Il codice è il seguente:

from time import clock

def read(filename):
	f = open(filename)

	list = []
	first = f.readline()
	side = int(first[2 : len(first)-3])
	for line in f:
		tmp = []
		for w in line.split():
			tmp.append(int(w))
		list.append(tmp)
	f.close()
	return side, list

def sumrange(a, x1, y1, x2, y2):
	s = 0
	for y in xrange(y1, y2):
		for x in xrange(x1, x2):
			s += a[y][x]
	return s

def contest5b(w, a):
	max_side = 1
	max_coord = (0, 0)
	max_sum = 0

	side = 1
	while side <= w:
		x = 0
		while (x + side) <= w:
			tmp = sumrange(a, x, 0, x + side, side)

			if (tmp > max_sum):
				max_coord = (x, 0)
				max_side = side
				max_sum = tmp

			y = 0
			while (y + side) < w:
				for i in xrange(side):
					tmp += (a[y+side][x+i] - a[y][x+i])

				if (tmp > max_sum):
					max_coord = (x, y+1)
					max_side = side
					max_sum = tmp
				y += 1
			x += 1
		side += 1
	return max_coord, max_side, max_sum

t1 = clock()
w, a = read("Matrix2.txt")
t2 = clock()
print "Lettura completata in", (t2-t1)*1000.0, "millisecondi."

print "Caricata una matrice %dx%d." % (w, w)
print "Inizio la ricerca...",
t1 = clock()
coord, side, sum = contest5b(w, a)
t2 = clock()
print "completata in", (t2-t1)*1000.0, "millisecondi."
print
print "Risultato: posizione", coord, "larghezza", side, "somma", sum

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.

[cdimauro]

Daniele, perché non provi Psyco?

Installalo, e all'inizio del tuo programma Python scrivi le seguenti 2 righe:

import psyco
psyco.full()

Eventualmente puoi anche disabilitare il garbage collector. In questo caso il codice di cui sopra diventa così:

import psyco, gc
psyco.full()
gc.disable()

Vedrai che con queste tre righe otterrai un buon miglioramento delle prestazioni.