[Vari] Contest 5: Sottomatrici

[Vincenzo1968]

Questi sono i miei tempi su una matrice 1000x1000:



Il codice, lo ricordo, contiene ancora qualche bug

[WarDuck]

Ho portato il mio codice per il secondo punto in C++, compilatore mingw-gcc 3.4.5.

Produttore sistema   Dell Inc.
Modello sistema      XPS M1330
Tipo sistema         PC basato su X86
Processore           Intel(R) Core(TM)2 Duo CPU     T8300  @ 2.40GHz, 2401 Mhz, 2 core, 2 processori logici

Preparatevi che è un po' lungo, ho incluso tutto, anche il main:

#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <ctime>

using namespace std;

int** loadMatrix(char* fileName, int& dim) {
        int** array;
        ifstream fs;
        fs.open(fileName);

        if (fs.is_open()) {
            fs >> dim;
            
            array = new int*[dim];
            for (int i=0; i<dim; i++) {
                array[i] = new int[dim];
            }
            
            
            int i = 0;
            while (!fs.eof() && i<dim) {
                int j=0;
                while (j<dim) {
                    fs >> array[i][j];
                    j = j+1;
                }
                i = i+1;
            }
        }
        fs.close();
        return array;
}

static void findMaxSum(int** mat, int& dim) {
        int old_i;
        int old_j;

        int max = 0;
        int max_i = 0;
        int max_j = 0;
        int p = 0;
        int max_p = 0;

        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;
                
                if (sum > max) {
                    max = sum;
                    max_i = old_i;
                    max_j = old_j;
                    max_p = p;
                }
                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;
            }
        }

        cout << "Max sum is " << max << " -> matrix " << max_p << "x" << max_p << " at index " << "(" << max_i << "," << max_j << ")\n";
    }

int main(int argc, char** argv) {
    clock_t start, end;
    double diff;
    int dim = 0;
    int** array;
    
    start = clock();
    array = loadMatrix("Matrix2.txt", dim);
    end = clock();
    
    diff = (double(end)-double(start))/CLOCKS_PER_SEC;
    
    cout << "Matrix Loaded. Time elapsed: ";
    cout << diff;
    cout << "ms\n";
    
    start = clock();
    findMaxSum(array, dim);
    end = clock();
    
    diff = (double(end)-double(start))/CLOCKS_PER_SEC;
    
    cout << "Computation Done. Time elapsed: ";
    cout << diff;
    cout << "ms\n";
    
    return 0;
}

Output:


Edit: ovviamente i risultati sono in secondi, ho sbagliato io a scrivere, pardon.

[Vincenzo1968]

Ecco la versione senza bug(almeno spero):

Prova sul matricione 1000x1000:



La macchina è questa:

AMD Athlon(tm) 64 X2 Dual
Core Processor 4800+
2.50 GHz 896 MB di RAM

Microsoft Windows XP Professional
Service Pack 2

e il codice è questo:

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

void FindSubMatrix(char *szFileName, int *row, int *col, int *size, int *sum)
{
	int **m;
	int x, y, k;
	int array_size;
	int subarray_size;
	Stati stato;

	int riga_sub, colonna_sub;

	int riga, colonna;
	int dim;
	int somma;

	clock_t c_start, c_end;

	int fibDim = 10;
	int fibRange;

	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;
			}
		}
	}
	else
	{
		printf("Memoria insufficiente.\n");
		return;
	}

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

	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 -> 0 secondi\n");

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

		return;
	}
	else if ( array_size == 2 )
	{
		dim = 1;
		riga = colonna = 0;
		somma = m[riga][colonna];
		if ( m[0][1] > somma )
		{
			riga = 0;
			colonna = 1;
			somma = m[riga][colonna];
		}

		if ( m[1][0] > somma )
		{
			riga = 1;
			colonna = 0;
			somma = m[riga][colonna];
		}

		if ( m[1][1] > somma )
		{
			riga = 1;
			colonna = 1;
			somma = m[riga][colonna];
		}

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

		printf("\nRiga       -> %d\nColonna    -> %d\nDimensione -> %d\nSomma      -> %d\n", riga, colonna, dim, somma);
		printf("\nTempo impiegato per la ricerca -> 0 secondi\n");

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

		return;
	}

	*sum = m[0][0] + m[0][1];
	*row = 0;
	*col = 0;
	*size = 2;

	for ( k = fibDim - 1; k >= 0; 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 > *sum )
				{
					*sum = somma;
					*row = riga;
					*col = colonna;
					*size = dim;
				}				
				x = y = 0;
				somma = 0;
			}
		}
	}

	fibRange = Fibonacci[3];
	subarray_size = *size + fibRange;
	dim = subarray_size;
	x = y = 0;
	riga_sub = *row;
	colonna_sub = *col;
	somma = 0;

	riga_sub -= fibRange;
	if ( riga_sub < 0 )
		riga_sub = 0;
	colonna_sub -= fibRange;
	if ( colonna_sub < 0 )
		colonna_sub = 0;

	while ( dim >= 2 )
	{
		for ( riga = riga_sub; riga <= *row*2 && riga + dim <= array_size; riga++ )
		{
			for ( colonna = colonna_sub; colonna <= *col*2 && colonna + dim <= array_size; colonna++ )
			{
				for( y = riga; y < riga + dim; y++ )
				{
					for( x = colonna; x < colonna + dim; x++ )
					{
						somma += m[y][x];
					}
				}
				if ( somma > *sum )
				{
					*sum = somma;
					*row = riga;
					*col = colonna;
					*size = dim;
				}				
				x = y = 0;
				somma = 0;
			}
		}
		dim--;
	}

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

int main()
{
	clock_t c_start, c_end;
	int row, col, size, sum;

	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix2.txt";
	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix3.txt";
	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix4.txt";
	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix5.txt";
	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix6.txt";
	//char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix7.txt";
	char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix8.txt";


	c_start = clock();

	FindSubMatrix(szFileName, &row, &col, &size, &sum);

	c_end = clock();

	printf("\nRiga       -> %d\nColonna    -> %d\nDimensione -> %d\nSomma      -> %d\n", row, col, size, sum);

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

	return 0;
}

[gugoXX]

Aggiusto i bug e tiro l'ultimo colpo di coda.
Rulla il C#, rulla. (In realta' no, ma ci stava bene)

Risultato 200x200

Coordinate: 94,60   - Dimensione 56   - Somma 3185
Time: 68ms
Test: 3185

Risultato 1000x1000

Coordinate: 232,565   - Dimensione 410   - Somma 2419
Time: 11148ms
Test: 2419

Codice

class Program
{
    static void Main(string[] args)
    {
        //int[,] vals = Randomizer.GetRandom2(5);
        //Matrix mat = new Matrix(vals);
        
        Matrix mat = new Matrix("Matrix2.txt");            
        Stopwatch sw = new Stopwatch();
        sw.Start();
        var toprint = mat.Ex8();
        sw.Stop();

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

        Console.WriteLine("Coordinate: {0},{1}   - Dimensione {2}   - Somma {3}", x, y, z, toprint.val);
        Console.WriteLine("Time: {0}ms", sw.ElapsedMilliseconds);
       
        int test = mat.Test(x, y, z);
        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 Result
    {
        public int x;
        public int y;
        public int z;
        public int val;
        public Result(int ix, int iy, int iz, int ival)
        {
            x = ix;
            y = iy;
            z = iz;
            val = ival;
        }
    }       

    public int Test(int x, int y, int d)
    {
        var dom = from ty in Enumerable.Range(y, d)
                  from tx in Enumerable.Range(x, d)
                  select Mat[tx, ty];
        return dom.Sum();                        
    }
    
    public Result Ex8()
    {           
        int[][,] Compl = new int[(Dim/2)+2][,];
        Compl[1]=Mat;

        var dom00 = from y in Enumerable.Range(0, Dim)
                    from x in Enumerable.Range(0, Dim)
                    select new Result(x, y, 1, Mat[x, y]);

        Result rer = dom00.Max(t => t.val);
        int rerval = rer.val;

        for (int z = 2; z <= Dim; z++)
        {
            int mda = (z >> 1);
            int ze1 = z & 1;
            int md = mda + ze1;
            bool ze1u1 = ze1 == 1;
            int dimmz = Dim - z;

            int[,] Complcur = null;
            bool tobemem = z < ((Dim >> 1) + 1);
            if (tobemem)
            {
                Complcur = Compl[z] = new int[dimmz, dimmz];
            }
            int[,] Complmda = Compl[mda];
            int[,] Complmd = Compl[md];
            for (int y = 0; y < dimmz; y++)
            {
                int ymda = y + mda;
                int ymd = y + md;
                for (int x = 0; x < dimmz; x++)
                {
                    int cur = Complmd[x, y]
                               + Complmda[x, ymd]
                               + Complmda[x + md, y]
                               + Complmd[x + mda, ymda];

                    if (ze1u1)
                    {
                        cur -= Mat[x + mda, ymda];
                        Compl[mda] = null;
                    }

                    if (tobemem)
                    {
                        Complcur[x, y] = cur;
                    }
                    if (cur > rerval)
                    {
                        rerval = cur;
                        rer = new Result(x, y, z, cur);
                    }
                }
            }
        }
        return rer;
    }
}

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)||(CurMax.CompareTo(default(U))==0))
            {
                CurmaxRow = t;
                CurMax = CurVal;
            }
        }
        return CurmaxRow;
    }        
}

[WarDuck]

Siete mostri ragazzi, complimenti...

PS: se allegate anche il vostro "principio di funzionamento" (cioè il ragionamento che avete fatto) è anche più educativo

[DanieleC88]

Originariamente inviato da WarDuck

Siete mostri ragazzi, complimenti...

Concordo pienamente, ad ogni Contest mi tocca scappare con la coda fra le gambe... (leggiti l'intervento di repne scasb per il Contest 3, se non ricordo male)

[banryu79]

Con repne scab non c'è confronto, solo apprendimento

[gugoXX]

Originariamente inviato da WarDuck

Siete mostri ragazzi, complimenti...

PS: se allegate anche il vostro "principio di funzionamento" (cioè il ragionamento che avete fatto) è anche più educativo

E' giusto.
Si tratta di calcolare tutte le possibili sottomatrici quadrate presenti sul matricione.
Nella mia implementazione (come penso finora tutte le altre), per ciascuna coordinata quindi occorre calcolare tutte le sottomatrici quadrate che hanno come vertice proprio quella coordinata.
Parto con il calcolare tutte le matrici quadrate di dimensione pari a 1, ovvero la matriciona originale stessa.
Poi salgo, e cerco tutte quelle di dimensione pari a 2
poi 3,... e cosi' via fino ad N.

Per ottenere la sottomatrice di dimensione Z, partendo dal presupposto che ho memorizzato e calcolato tutte le sottomatrici precedenti, ho diviso il problema in 2.
Se Z e' un numero pari, allora sommo fra di loro 4 sottomatrici di lato z/2
Se Z e' un numero dispari invece sommo fra di loro 2 sottomatrici di lato z/2 arrotondato inferiore e 2 sottomatrici di lato z/2 arrotondato superiore, posizionate come in figura.
In questo modo pero' l'elemento centrale lo considero 2 volte, che verra' quindi tolto se del caso.



Inoltre, non e' necessario tenere in memoria tutte le matrici.
Innanzitutto quelle con dimensione superiore a DIM/2 non le memorizzeremo, in quanto non verranno mai utilizzate
In piu', mano a mano che si prosegue, possiamo inziare a rimuovere sottomatrici precedenti che non si useranno piu'.
Es: Quando ho terminato di calcolare le sottomatrici lato 9, posso rimuovere tutte le sottomatrici lato 4, in quanto non verranno piu' usate.
Nel calcolo delle sottomatrici lato 10 si useranno le sottomatrici lato5, e non torneremo mai piu' indietro.

Cosi' ho trovato lo spazio per calcolare la 1000x1000.

L'algoritmo e' quindi un O(5N*N^2) = O(N^3)
Per la memoria richiesta massima invece devo calcolare il volume di un tronco di piramide sghemba, e ad Agosto non ho proprio voglia.
Comunque e' O(N^3) anche lui, ma con coefficienti bassi.

[DanieleC88]

Metodo molto ingegnoso, complimenti.

[WarDuck]

Sto sviluppando una teoria, per tentare di prevedere se continuare o meno il calcolo delle sottomatrici in base alle somme già trovate e alla media dei valori positivi, vediamo se funziona...

[DanieleC88]

Però fermare il calcolo in base alla media dei numeri positivi presuppone che questi siano distribuiti in modo più o meno uniforme attraverso la matrice, mentre è perfettamente legale ricevere in input una matrice piena di zeri o di numeri negativi e trovare poi una serie di interi positivi molto grandi nell'angolo in basso a destra, per esempio. Non trovi?

[Vincenzo1968]

Ogni volta che correggo qualche bug, ne spuntano altri mille.
Io mi fermo qui, mi arrendo.

[WarDuck]

Originariamente inviato da DanieleC88

Però fermare il calcolo in base alla media dei numeri positivi presuppone che questi siano distribuiti in modo più o meno uniforme attraverso la matrice, mentre è perfettamente legale ricevere in input una matrice piena di zeri o di numeri negativi e trovare poi una serie di interi positivi molto grandi nell'angolo in basso a destra, per esempio. Non trovi?

Si infatti sto cercando di risolvere la questione usando la media dei numeri calcolati nello stesso passo.

Chiaramente il problema della distribuzione c'è... La mia idea è qualcosa del tipo "se ad un certo punto tutte le somme degli elementi fatte finora sono inferiori alla media evita di andare avanti".

Il problema è capire se possa funzionare con la maggior parte delle distribuzioni possibili (dovrei tirare fuori qualcosa di matematicamente valido da poter essere dimostrato, non una cosa facile insomma) e soprattutto capire qual è il famoso "punto" di cui parlo al paragrafo precedente (finora ho fatto delle prove legandolo alla dimensione della matrice, calcolandomi un fattore ad esempio dim/2 ).

Cmq è solo una idea, il problema come dice einstein sono i nostri "pregiudizi". Bisognerebbe ragionare fuori dagli schemi (per quanto sia possibile), magari provare a ristendere il programma da capo, tentando qualche altra soluzione.

[gugoXX]

Corretto un BUG.
Iniettato il parallelismo
e chiudo qui anche io.

Per poter compliare occorre scaricare le parallel extension (PLINQ)
e includere la reference appena scaricata: system.threading nel progetto.

Matrice 1000x1000

Coordinate: 232,565   - Dimensione 410   - Somma 2419
Time: 6844ms
Test: 2419

class Program
{
    static void Main(string[] args)
    {
        //int[,] vals = Randomizer.GetRandom2(5);
        //Matrix mat = new Matrix(vals);
        
        Matrix mat = new Matrix("Matrix1.txt");            
        Stopwatch sw = new Stopwatch();
        sw.Start();
        var toprint = mat.Ex8();
        sw.Stop();

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

        Console.WriteLine("Coordinate: {0},{1}   - Dimensione {2}   - Somma {3}", x, y, z, toprint.val);
        Console.WriteLine("Time: {0}ms", sw.ElapsedMilliseconds);
       
        int test = mat.Test(x, y, z);
        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 Result
    {
        public int x;
        public int y;
        public int z;
        public int val;
        public Result(int ix, int iy, int iz, int ival)
        {
            x = ix;
            y = iy;
            z = iz;
            val = ival;
        }
    }       

    public int Test(int x, int y, int d)
    {
        var dom = from ty in Enumerable.Range(y, d)
                  from tx in Enumerable.Range(x, d)
                  select Mat[tx, ty];
        return dom.Sum();                        
    }
    
    public Result Ex8()
    {           
        int[][,] Compl = new int[(Dim/2)+2][,];
        Compl[1]=Mat;

        var dom00 = from y in Enumerable.Range(0, Dim)
                    from x in Enumerable.Range(0, Dim)
                    select new Result(x, y, 1, Mat[x, y]);

        Result rer = dom00.Max(t => t.val);
        int rerval = rer.val;

        int limmem=((Dim >> 1) + 1);
        for (int z = 2; z <= Dim; z++)
        {
            int mda = (z >> 1);
            int ze1 = z & 1;
            int md = mda + ze1;
            bool ze1u1 = ze1 == 1;
            int dimmz = Dim - z;

            int[,] Complcur = null;
            bool tobemem = z < limmem;
            if (tobemem)
            {
                Complcur = Compl[z] = new int[dimmz, dimmz];
            }
            int[,] Complmda = Compl[mda];
            int[,] Complmd = Compl[md];
            Parallel.For(0, dimmz, y =>
            {
                int ymda = y + mda;
                int ymd = y + md;
                for (int x = 0; x < dimmz; x++)
                {
                    int cur = Complmd[x, y]
                            + Complmda[x, ymd]
                            + Complmda[x + md, y]
                            + Complmd[x + mda, ymda];

                    if (ze1u1)
                    {
                        cur -= Mat[x + mda, ymda];
                    }

                    if (tobemem)
                    {
                        Complcur[x, y] = cur;
                    }
                    if (cur > rerval)
                    {
                        mut.WaitOne();
                        if (cur > rerval)
                        {
                            rerval = cur;
                            rer = new Result(x, y, z, cur);
                        }
                        mut.ReleaseMutex();
                    }
                }
            });
            if (ze1u1) Compl[mda] = null;
        }            
        return rer;
    }    

    private Mutex mut = new Mutex();        
}

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)||(CurMax.CompareTo(default(U))==0))
            {
                CurmaxRow = t;
                CurMax = CurVal;
            }
        }
        return CurmaxRow;
    }        
}

[Vincenzo1968]

Originariamente inviato da gugoXX

Corretto un BUG.
Iniettato il parallelismo
e chiudo qui anche io.

Per poter compliare occorre scaricare le parallel extension (PLINQ)
e includere la reference appena scaricata: system.threading nel progetto.
...

Mi dispiace scassarti ancora i cabasisi, ma ho, purtroppo, trovato un altro errore nel tuo programma.
Sostituendo, nel file matrix1, i numeri agli indici [0][0] e [999][999] con il numero 1.000.000, l'output del tuo programma è:



mentre, come mostra il programma di Daniele, dovrebbe essere:


Daniele è dunque, fino a questo momento, il vincitore. Vero è che il suo programma è più lento, ma fornisce sempre i risultati corretti(e ha il pregio di utilizzare solo la memoria strettamente necessaria).

Ciao.

P.S.
Daniele, ho modificato, nel tuo programma, il modo di visualizzare l'output. Spero non ti dispiaccia. Ciao.

[WarDuck]

Qualcuno per caso ha matrici più grosse delle 1000x1000? Dovrei farci delle prove...

[DanieleC88]

Originariamente inviato da Vincenzo1968

P.S.
Daniele, ho modificato, nel tuo programma, il modo di visualizzare l'output. Spero non ti dispiaccia. Ciao.

No, ma figurati, è più chiaro così in effetti.

[marco.r]

Originariamente inviato da Vincenzo1968

Mi dispiace scassarti ancora i cabasisi, ma ho, purtroppo, trovato un altro errore nel tuo programma.
Sostituendo, nel file matrix1, i numeri agli indici [0][0] e [999][999] con il numero 1.000.000, l'output del tuo programma è:

Uhm, strano, ho provato a riportare il codice di gugo in C++ (non ho un compilatore C# decente sulla mia macchina per provare direttamente il codice originale) e sembra dare risultati corretti

[gugoXX]

Originariamente inviato da Vincenzo1968

Mi dispiace scassarti ancora i cabasisi, ma ho, purtroppo, trovato un altro errore nel tuo programma.

Ma che sono i cabasisi??? Immagino...
Quel che e' giusto e' giusto.
Ma perche' non debuggi il tuo? Non mi sembrava tanto distante.

Ecco l'indice corretto comunque.

class Program
{
    static void Main(string[] args)
    {
        //int[,] vals = Randomizer.GetRandom2(5);
        //Matrix mat = new Matrix(vals);

        Matrix mat = new Matrix("Matrix1.txt");
        Stopwatch sw = new Stopwatch();
        sw.Start();
        var toprint = mat.Ex8();
        sw.Stop();

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

        Console.WriteLine("Coordinate: {0},{1}   - Dimensione {2}   - Somma {3}", x, y, z, toprint.val);
        Console.WriteLine("Time: {0}ms", sw.ElapsedMilliseconds);

        int test = mat.Test(x, y, z);
        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 Result
    {
        public int x;
        public int y;
        public int z;
        public int val;
        public Result(int ix, int iy, int iz, int ival)
        {
            x = ix;
            y = iy;
            z = iz;
            val = ival;
        }
    }

    public int Test(int x, int y, int d)
    {
        var dom = from ty in Enumerable.Range(y, d)
                  from tx in Enumerable.Range(x, d)
                  select Mat[tx, ty];
        return dom.Sum();
    }

    public Result Ex8()
    {
        int limmem = ((Dim >> 1) + 2);
        int[][,] Compl = new int[limmem][,];
        Compl[1] = Mat;

        var dom00 = from y in Enumerable.Range(0, Dim)
                    from x in Enumerable.Range(0, Dim)
                    select new Result(x, y, 1, Mat[x, y]);

        Result rer = dom00.Max(t => t.val);
        int rerval = rer.val;
        
        for (int z = 2; z <= Dim; z++)
        {
            int mda = (z >> 1);
            int ze1 = z & 1;
            int md = mda + ze1;
            bool ze1u1 = ze1 == 1;
            int dimmz = Dim - z;

            int[,] Complcur = null;
            bool tobemem = z < limmem;
            if (tobemem)
            {
                Complcur = Compl[z] = new int[dimmz+1, dimmz+1];
            }
            int[,] Complmda = Compl[mda];
            int[,] Complmd = Compl[md];               
            Parallel.For(0, dimmz+1, y =>
            {
                int ymda = y + mda;
                int ymd = y + md;
                for (int x = 0; x <= dimmz; x++)
                {
                    int cur = Complmd[x, y]
                            + Complmda[x, ymd]
                            + Complmda[x + md, y]
                            + Complmd[x + mda, ymda];

                    if (ze1u1)
                    {
                        cur -= Mat[x + mda, ymda];
                    }

                    if (tobemem)
                    {
                        Complcur[x, y] = cur;
                    }
                    if (cur > rerval)
                    {
                        mut.WaitOne();
                        if (cur > rerval)
                        {
                            rerval = cur;
                            rer = new Result(x, y, z, cur);
                        }
                        mut.ReleaseMutex();
                    }
                }
            });
            if (ze1u1) Compl[mda] = null;
        }
        return rer;
    }

    private Mutex mut = new Mutex();
}

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) || (CurMax.CompareTo(default(U)) == 0))
            {
                CurmaxRow = t;
                CurMax = CurVal;
            }
        }
        return CurmaxRow;
    }
}

Per quanto riguarda la memoria massima occupata, essa dovrebbe essere il volume del tronco di piramide quadrata di
base maggiore: (3/4Dim)(3/4Dim)
base minore: (1/2Dim)(1/2Dim)
altezza: (1/4Dim)

Ho trovato un metodo che garantirebbe prestazioni paragonabili e consumo di memoria molto piu' basso.
Nel calcolare le sottomatrici di dimensione Z, si puo' far uso delle sole sottomatrici di dimensione Z-1 e Z-2, con quindi
O(Z^2) sul consumo memoria e O(Z^3) sulle prestazioni.

[DanieleC88]

Originariamente inviato da gugoXX

Ma che sono i cabasisi???

I cog**oni (ayin docet)