[Vari] Contest 5: Sottomatrici

[WarDuck]

Finalmente ho concluso anche la seconda parte!!!

Ora via di ottimizzazione (la parte più divertente direi ).

Ecco il codice (va ripulito):

static int findMaxSum(int[,] mat) {
            int old_i;
            int old_j;

            int max = 0;
            int max_i = 0;
            int max_j = 0;
            int p = 0;
            int max_p = 0;
            
            int dim = (int)Math.Sqrt(mat.Length);

                for (int i = 0; i < dim; i++) {
                    for (int j = 0; j < dim; j++) {
                        int sum = mat[i, j];
                        old_i = i;
                        old_j = j;
                        p = 1;
                        for (int k = p - 1; k >= 0 && i < dim - 1 && j < dim - 1; k--) {
                            sum = sum + mat[i - k, j + 1] + mat[i + 1, j - k];
                            if (k == 0) {
                                sum = sum + mat[i + 1, j + 1];
                                i++;
                                j++;
                                k = ++p;
                                if (sum > max) {
                                    max = sum;
                                    max_i = old_i;
                                    max_j = old_j;
                                    max_p = p;
                                }
                            }
                        }
                        i = old_i;
                        j = old_j;
                    }
                }
            
            Console.WriteLine("Max sum is " + max + " -> matrix "+max_p+"x"+max_p+" at index "+"("+max_i+","+max_j+")");
            return max;
        }

E l'output:

[marco.r]

Originariamente inviato da Vincenzo1968

Una risposta veloce non e' un buon sostituto di una risposta corretta .
Ho provato a sostituire in matrix2.txt 10000 nella prima casella in alto a sinistra il risultato del programma non cambia , mentre dovrebbe quantomeno darmi come valore migliore da sottomatrice di dimensione 1 nella posizione (0,0).
Tra l'altro mi da un errore quando provo a leggere la seguente matrice

--2--
0 1
2 3

con errore

Automa: Stato S1 errore sul carattere -> '
'

ovvero trova un ritorno a capo che non gli piace... cosa sbaglio

[WarDuck]

Probabilmente il suo programma (così come il mio e penso pure quello degli altri) non tiene conto dei singoli elementi, ma cerca almeno una sottomatrice da 2.

[DanieleC88]

Originariamente inviato da WarDuck

Probabilmente il suo programma (così come il mio e penso pure quello degli altri) non tiene conto dei singoli elementi, ma cerca almeno una sottomatrice da 2.

Ah ecco dov'era l'inghippo.

No, le mie soluzioni tengono sempre conto del caso generale, e quindi processano prima ogni singolo elemento, e poi le sottomatrici quadrate più larghe.

[WarDuck]

Originariamente inviato da DanieleC88

Ah ecco dov'era l'inghippo.

No, le mie soluzioni tengono sempre conto del caso generale, e quindi processano prima ogni singolo elemento, e poi le sottomatrici quadrate più larghe.

Si penso sia più giusto, ora modifico anche il mio affinché lo faccia...

Cmq sto pensando che almeno nel mio caso non dovrebbe influenzare molto il risultato, poiché si tratta solo di fare un confronto in più col massimo. I cicli restano gli stessi.

[gugoXX]

.

[Tommo]

Apposto ho finito la fase 1 dell'esercizio 2:

ecco il source... ho messo tutti e 3 i files (main, h e cpp) in una sola finestra perchè sennò diventava lunghissimo...

Cmq ho aggiunto una funzione precisa al millesimo (rippata spudoratamente dai samples di PhysX )per calcolare il tempo, e per aumentare ancora di piu' la precisione carico la matrice 20 volte e faccio la media dei tempi.

Il risultato così è di 0.00244625 secondi
magari senza usare iostream sarebbe piu rapido, ma non mi va

MAIN.CPP
#include "Matrix.h"

#include <iostream>
#include <time.h>
#include <windows.h>

using namespace std;

#ifdef __cplusplus
extern "C" {
#endif


	double deltaTime()
	{
		double d;
#ifndef LINUX
		static __int64 gTime,gLastTime;
		__int64 freq;
		QueryPerformanceCounter((LARGE_INTEGER *)&gTime);  // Get current count
		QueryPerformanceFrequency((LARGE_INTEGER *)&freq); // Get processor freq
		d = (double)(gTime - gLastTime)/(double)freq;
		gLastTime = gTime;
#else
		struct timeval tv;
		static struct timeval lasttv = { 0 , 0 };
		if (lasttv.tv_usec == 0 && lasttv.tv_sec == 0)
			gettimeofday(&lasttv, NULL);
		gettimeofday(&tv, NULL);
		d = (tv.tv_usec - lasttv.tv_usec)/1000000.f
			+ (tv.tv_sec - lasttv.tv_sec);
		lasttv = tv;
#endif
		return d;
	}

	int main(int argc, char *argv[])
	{
		double delta;

		//Creiamo il gioco con la configurazione specifica
		Matrix* m = new Matrix( 200 );

		//init
		deltaTime();

		//va fatto 20 volte e poi mediato
		unsigned int rep = 20;

		for(unsigned int i = 0; i < rep; ++i)
			m->load( "Matrix2.txt" );
		//delta
		delta = deltaTime()/rep;

		
#ifdef _DEBUG
		m->listNumbers();
#endif
		
		cout << "Tempo impiegato per caricare: " << delta << " secondi!" << endl;

		Matrix::MaxSum s = m->searchMaxSum();

		std::cout << s.value << ", posizione:" << s.x << "," << s.y << endl << "dimensioni: " << s.sizeX << "," << s.sizeY;
		return 0;
	}

#ifdef __cplusplus
}
#endif



MATRIX.H

#include <string>

class Matrix
{
public:

	struct MaxSum
	{
		float value;
		unsigned int x, y, sizeX, sizeY;
	};

	Matrix( unsigned int declaredSide )
	{
		side = declaredSide;
		//alloca l'indice
		matrix = (float**)malloc( side*sizeof(float*) );

		//alloca l'intera matrice
		for( unsigned int i = 0; i < side; ++i)
			matrix[i] = (float*)malloc( side*sizeof(float) );
	}

	~Matrix()
	{
		//dealloca l'intera matrice
		for( unsigned int i = 0; i < side; ++i)
			free( matrix[i] );

		free(matrix);
	}

	void listNumbers();

	void load( std::string path );

	MaxSum searchMaxSum() { return sum; }

protected:
	unsigned int side;

	MaxSum sum;

	float** matrix;
};

MATRIX.CPP

#include "matrix.h"

#include <fstream>
#include <iostream>

using namespace std;

typedef unsigned int uint;

void Matrix::load( string path )
{
	uint chars;
	char* buffer;

	fstream f;

	//apri e trova la lunghezza
	f.open( path.c_str(), ios::in | ios::ate );
	chars = f.tellg();
	f.seekg(0);

	//schiaffa tutto nel buffer
	buffer = (char*)malloc(chars* sizeof(char));
	f.read(buffer, chars);

	//a questo punto si puo' convertire i caratteri in numeri
	float number = 0;
	uint digitIndex = 1;
	uint digit;

	int X = side-1;
	int Y = side-1;

	int i = chars-1;
	for(; i != -1; i--)
	{
		if( buffer[i] == '-')
			number *= -1;
		
		//e' uno spazio, terminare e salvare

		else if ( buffer[i] == ' ')
		{
			//salva nel buffer 
			matrix[Y][X] = number;

			//scorri la matrice
			X--;
			if( X < 0 )
			{
				X = side-1;
				Y--;
			}

			//e resetta
			number = 0;
			digitIndex = 1;
		}
		else
		{
			digit = 0;

			if( buffer[i] == '1' )		digit = 1;
			else if( buffer[i] == '2' )	digit = 2;
			else if( buffer[i] == '3' )	digit = 3;
			else if( buffer[i] == '4' )	digit = 4;
			else if( buffer[i] == '5' ) digit = 5;
			else if( buffer[i] == '6' )	digit = 6;
			else if( buffer[i] == '7' )	digit = 7;
			else if( buffer[i] == '8' )	digit = 8;
			else if( buffer[i] == '9' )	digit = 9;
			//una cifra, inserirla nel numero

			number += digit * digitIndex;
			digitIndex *= 10;
		}
	}
	//salva nel buffer il primo numero, cioe' l'ultimo, prima del quale non c'e' lo spazio
	matrix[0][0] = number;

	free(buffer);
}

void Matrix::listNumbers()
{	
	{
		for(unsigned int y = 0; y < side; ++y)
		{
			for(unsigned int x = 0; x < side; ++x)
				std::cout << matrix[y][x] << " ";

			std::cout << std::endl;
		}
	}
}

[marco.r]

Originariamente inviato da WarDuck

Probabilmente il suo programma (così come il mio e penso pure quello degli altri) non tiene conto dei singoli elementi, ma cerca almeno una sottomatrice da 2.

Dovrebbe cmq tornarmi almeno la sottomatrice di dimensione 2 sita in (0,0) e con valore totale 10021. Probabilmente non e' solo quello.

Per inciso, se non e' chiedere troppo, proporrei che le soluzioni postate contengano un minimo di codice per farle funzionare (un main che carica la matrice ad esempio), in modo che gli altri che vogliono provarle possano farlo senza tanti sbattimenti (in modo simile a quello che hanno gia' fatto vincenzo e gugo, tanto per capirsi). Prometto che lo faro' anche io

[WarDuck]

Originariamente inviato da marco.r

Dovrebbe cmq tornarmi almeno la sottomatrice di dimensione 2 sita in (0,0) e con valore totale 10021. Probabilmente non e' solo quello.

Per inciso, se non e' chiedere troppo, proporrei che le soluzioni postate contengano un minimo di codice per farle funzionare (un main che carica la matrice ad esempio), in modo che gli altri che vogliono provarle possano farlo senza tanti sbattimenti (in modo simile a quello che hanno gia' fatto vincenzo e gugo, tanto per capirsi). Prometto che lo faro' anche io

Allora col codice che avevo postato, modificandolo per fargli controllare anche i singoli elementi, ti posso dire che a me viene:

Matrix dimensions: 200
Max sum is 11190 -> matrix 27x27 at index (0,0)
Elapsed: 1133,9412 milliseconds.

Questo mettendo 10000 al primo elemento (al posto del -42 iniziale):

(non l'ho testato a fondo quindi nn so se funziona esattamente)

Cmq ora sto lavorando su come ottimizzarlo usando 2 indici (si potrebbe fare a 4 partendo da ogni "vertice" della matrice ma è meglio provare prima con 2), facendo quindi più somme contemporaneamente, ma ancora non funge bene perchè si mangia 4 cicli non so dove (si ferma cioè prima del previsto).

Se ci riesco posto soluzione e main

[Vincenzo1968]

Originariamente inviato da DanieleC88

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

[Vincenzo1968]

Originariamente inviato da marco.r

Una risposta veloce non e' un buon sostituto di una risposta corretta .
Ho provato a sostituire in matrix2.txt 10000 nella prima casella in alto a sinistra il risultato del programma non cambia , mentre dovrebbe quantomeno darmi come valore migliore da sottomatrice di dimensione 1 nella posizione (0,0).
Tra l'altro mi da un errore quando provo a leggere la seguente matrice

--2--
0 1
2 3

con errore

ovvero trova un ritorno a capo che non gli piace... cosa sbaglio

Vedo(spero presto ) di trovare il bug.
Per il secondo problema, l'automa assume che i numeri siano separati da uno spazio, compreso l'ultimo. Si può facilmente modificare in modo che l'ultimo numero sia separato, indifferentemente, da uno spazio o da un newline.

[DanieleC88]

Originariamente inviato da Vincenzo1968

Grazie

Cavoli mi batti di oltre 10 volte... Mi arrendo!

[WarDuck]

Che computer hai vincenzo, per curiosità?

[Vincenzo1968]

Originariamente inviato da DanieleC88

Grazie

Cavoli mi batti di oltre 10 volte... Mi arrendo!

No, non ti batto per niente. Il codice che ho postato è velocissimo in certi casi ma, in altri, dà dei risultati del tutto sballati.

Ciao WarDuck,

il computer è questo:

AMD Turion(tm) 64 X2 Mobile Technology TL-58 1.90 GHz
RAM: 3.00 GB
Sistema operativo: Windows Vista Home Premium - Service Pack 1

[WarDuck]

Chiaro

[gugoXX]

650ms in C#
E ho pure usato il crivello di Eratostene per calcolare i numeri primi (e il divisore piu' grande di ciascuno dei compositi).
La parte in blu e' sempre l'algoritmo principale.
Provero' a mettere il parallelismo, per vedere cosa succede, anche se e' difficile inserirlo efficientemente.

La versione funzionale e' sempre li' sotto, giusto come paragone (Scesa a 6 secondi, ma effettivamente non paragonabile)

Ora, fatto salvo che per testare eventuali differenze algoritmiche dobbiamo scalare piu' in alto,
a nessuno e' venuto in mente o ha provato a risolvere il problema con un algoritmo greedy?
Gli algoritmi greedy non hanno la pretesa di fornire il risultato migliore. Ne forniscono uno molto buono, ma sono in genere velocissimi. Idee?

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

class Program
{
    static void Main(string[] args)
    {
        //int[,] vals = Randomizer.GetRandom2(10);
        //Matrix mat = new Matrix(vals);
        Stopwatch sw = new Stopwatch();
        sw.Start();
        Matrix mat = new Matrix("Matrix2.txt");
        long ll = sw.ElapsedMilliseconds;
        sw.Reset();
        sw.Start();
        var toprint = mat.Ex4();
        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 Ex4()
    {       
        int[,][] Compl = new int[Dim, Dim][];
        for (int y = 0; y < Dim; y++)
        {
            for (int x = 0; x < Dim; x++)
            {
                int mxy = Dim - ((x > y) ? x : y);
                int[] st = Compl[x, y] = new int[mxy];
                st[0] = Mat[x, y];
                if (mxy > 1) st[1] = Mat[x, y] + Mat[x, y + 1] + Mat[x + 1, y] + Mat[x + 1, y + 1];
            }
        }

        int[] Eratost = Eratostene();

        Ex2Result rer = new Ex2Result();
        int rerval = int.MinValue;
        for (int z = 2; z < Dim; z++)
        {
            int era = Eratost[z + 1];
            for(int y=0;y<Dim;y++)                
            {
                for (int x = 0; x < Dim; x++)
                {
                    int mxy = Dim - ((x > y) ? x : y);
                    if (z < mxy)
                    {
                        int[] ToCalc = Compl[x, y];

                        int cur;
                        if (era == -1)
                        {
                            //OldStyle se e' primo
                            int sum = ToCalc[z - 1];
                            for (int u = 0; u < z; u++)
                            {                                
                                sum += Mat[x + u, y + z] + Mat[x + z, y + u];
                            }
                            cur = sum + Mat[x + z, y + z];
                        }
                        else
                        {
                            //NewStyle se e' composito
                            int div = (z + 1) / era;
                            int divm1 = era - 1;
                            int divdivm1 = div * divm1;
                            int ydivdivm1 = y + divdivm1;
                            int xdivdivm1 = x + divdivm1;
                            int sum = ToCalc[divdivm1 - 1];
                            int divmm1 = div - 1;
                            for (int u = 0, xu=x,yu=y; u < divm1; u++, xu+=div, yu+=div)
                            {
                                int s1 = Compl[xu, ydivdivm1][divmm1];
                                int s2 = Compl[xdivdivm1, yu][divmm1];
                                sum += s1 + s2;
                            }
                            int s3 = Compl[xdivdivm1, ydivdivm1][divmm1];
                            cur = sum + s3;
                        }
                        ToCalc[z] = cur;
                        if (cur > rerval)
                        {
                            rer=new Ex2Result(new CoordsStruct(x, y, z), cur);
                            rerval = cur;
                        }
                    }
                    else break;
                }                
            }
        }
        return rer;
    }
      
    private int[] Eratostene()
    {
        int[] ret = new int[Dim+1];
        int ms=((int)Math.Sqrt(Dim))+1;            
        int t;
        for (t = 2; t < ms; t++)
        {
            if (ret[t] == 0)
            {
                ret[t] = -1;
                for (int u = t+t; u <= Dim; u += t)
                {
                    if (ret[u]==0) ret[u] = t;
                }
            }
        }
        for (; t <= Dim; t++)
        {
            if (ret[t] == 0) ret[t] = -1;
        }
        return ret;
    }
    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;
    }
}

[DanieleC88]

Non li conosco nemmeno di nome... nessuna idea al riguardo.

[Vincenzo1968]

Ho risolto(grazie a Fibonacci ):



Col valore 10000 al posto del primo numero(-42):


Adesso è molto più lento ma sembra funzionare bene(ho provato con l'inserimento del valore 10000 in più punti del file).
Ho sistemato anche l'automa in modo da fargli accettare il carattere di ritorno a capo per l'ultimo numero della riga.

#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 == ' ' || c == '\r' || c == '\n' )
			{
				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 riga_temp, colonna_temp;
	int dim_temp;
	int somma_temp;

	int fibDim = 10;

	int Fibonacci[] = {2,3,5,8,13,21,34,55,89,144};

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

	if ( array_size == 1 )
	{
		c_end = clock();
		printf("\nRiga       -> 0\nColonna    -> 0\nDimensione -> 1\nSomma      -> %d\n", m[0][0]);
		printf("\nTempo impiegato per la ricerca -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);
		return 0;
	}
	else if ( array_size == 2 )
	{
		riga = colonna = 0;
		dim = 1;
		somma = m[riga][colonna];
		colonna++;
		if ( m[riga][colonna] > somma )
			somma = m[0][1];
		colonna = 0;
		riga++;
		if ( m[riga][colonna] > somma )
			somma = m[riga][colonna];
		colonna++;
		if ( m[riga][colonna] > somma )
			somma = m[1][1];

		if ( m[0][0] + m[0][1] + m[1][0] + m[1][1] > somma )
		{
			dim = 2;
			riga = 0;
			colonna = 0;

			somma = m[0][0] + m[0][1] + m[1][0] + m[1][1];
		}

		c_end = clock();
		printf("\nRiga       -> %d\nColonna    -> %d\nDimensione -> %d\nSomma      -> %d\n", riga, colonna, dim, somma);
		printf("\nTempo impiegato per la ricerca -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);
		return 0;
	}

	somma_temp = m[0][0] + m[0][1];
	riga_temp = 0;
	colonna_temp = 0;
	dim_temp = 2;

	for ( k = 0; k < fibDim; k++ )
	{
		dim = Fibonacci[k];
		x = y = 0;
		riga = colonna = 0;
		somma = 0;
		for ( riga = 0; riga <= array_size - dim; riga++ )
		{
			for ( colonna = 0; colonna <= array_size - dim; colonna++ )
			{
				for( y = riga; y < riga + dim; y++ )
				{
					for( x = colonna; x < colonna + dim; x++ )
					{
						somma += m[y][x];
					}
				}
				if ( somma > somma_temp )
				{
					somma_temp = somma;
					riga_temp = riga;
					colonna_temp = colonna;
					dim_temp = dim;
				}
				x = y = 0;
				somma = 0;
			}
		}
	}

	dim = dim_temp + 1;
	colonna = colonna_temp;
	while ( dim < array_size - dim )
	{
		x = y = 0;

		riga = riga_temp - 1;
		if ( riga < 0 )
			riga = 0;

		somma = 0;

		if ( riga + dim > array_size - 1 )
			break;
		if ( colonna + dim > array_size - 1 )
			break;

		for( y = riga; y < riga + dim; y++ )
		{
			for( x = colonna; x < colonna + dim; x++ )
			{
				somma += m[y][x];
			}
		}
		if ( somma > somma_temp )
		{
			somma_temp = somma;
			riga_temp = riga;
			colonna_temp = colonna;
			dim_temp = dim;
		}

		dim++;
	}

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

[Vincenzo1968]

Originariamente inviato da gugoXX

650ms in C#
E ho pure usato il crivello di Eratostene per calcolare i numeri primi (e il divisore piu' grande di ciascuno dei compositi).
La parte in blu e' sempre l'algoritmo principale.
Provero' a mettere il parallelismo, per vedere cosa succede, anche se e' difficile inserirlo efficientemente.

La versione funzionale e' sempre li' sotto, giusto come paragone (Scesa a 6 secondi, ma effettivamente non paragonabile)
...

Ciao Gugo,

intanto grazie per le nottate(e, per giunta, in ferie) passate a programmare per i tuoi contest(ovviamente, scherzo , quella dei contest la trovo un'idea fantastica).

Ho provato a compilare il tuo codice ma ho questo errore:

'System.Collections.Generic.IEnumerable<int>' non contiene
una definizione di 'ForAll' e non è stato trovato alcun metodo
di estensione 'ForAll'che accetta un primo argomento di tipo
'System.Collections.Generic.IEnumerable<int>'.
Probabilmente manca una direttiva using o un riferimento a un assembly.

che direttive debbo usare?

[cdimauro]

La direttiva 4.