# Such Algorithmus beschleunigen ?



## BlackSonic (25. Jun 2007)

Also hier ist die Aufgabenstellung
Gegeben sind :

• ein n × n-Array a, das mit Zufallszahlen aus dem Bereich 0. . .9 gefüllt ist sowie
• eine positive ganze Zahl x

Gesucht ist die Anzahl der in a enthaltenen Rechtecke, 
bei den die Summe der Zahlen von den 4 Kanten( Rand) des Rechtecks genau x ergibt.
Jedes Rechteck muss mindestens die Höhe 1 und Breite 1 haben, d.h., Rechtecke dürfen nicht zu
einer Strecke oder einem Punkt entarten.

Bsp :

8 2 1 8 4 7 5
3 0 0 0 4 9 3
7 0 3 8 7 1 8
3 2 7 8 8 0 9
5 5 2 5 3 3 4
2 8 4 6 4 7 4
0 3 9 6 8 4 2

x = 30
Ausgabe: 5


Ich habe scho ein Programm geschrieben, aber der Algo ist zu langsam. Weil wir haben die Vorraussetzung das er bei einem 250 * 250  Array unter 30 sec läuft. 
Mein Programm tut das nicht, braucht 5 min oder so 

Hier noch paar Werte

1 Zahl Array Länge 
2 Zahl Gesuchter wert X
3 Zahl zufalls zahl für den Random 

java Generator 7 30 123 data.dat -> Anzahl Rechtecke: 5
java Generator 7 30 147 data.dat -> Anzahl Rechtecke: 8
java Generator 10 30 555 data.dat -> Anzahl Rechtecke: 23
java Generator 50 150 555 data.dat -> Anzahl Rechtecke: 2922
java Generator 50 300 777 data.dat -> Anzahl Rechtecke: 3590
java Generator 100 300 975 data.dat -> Anzahl Rechtecke: 24007
java Generator 100 100 1 data.dat -> Anzahl Rechtecke: 10141
java Generator 150 500 234 data.dat -> Anzahl Rechtecke: 88949
java Generator 200 600 3434 data.dat -> Anzahl Rechtecke: 199734
java Generator 250 1000 22 data.dat -> Anzahl Rechtecke: 451879

Mein Programm :

```
import java.io.*;

class Rectangles {

	static int countRectangles(int a[][], int zahl) {
		int summe = 0;
		int laenge = a.length;
		
		//Hier werden die Zahlen aus dem Array von hinten uebergeben.
		// Sie laufen von hinten  bis 1 durch.
		for (int x = laenge; --x>0;)
			for (int y = laenge; --y>0;)
				summe += basistest(a, zahl,laenge, x, y);
		return summe;
	}
	
//_________________________________________________________________________________________    
	// Hier ist nur eine Überprüfung auf die 3 Grundelemete jedes möglichen vierecks
	static int basistest (int a[][], int zahl, int laenge, int startx, int starty){
	int basis =a[startx][starty]+a[startx][starty-1]+a[startx-1][starty];
	if(basis > zahl)
	   return 0;
	else
	 return countrectangles(a,zahl,laenge,startx,starty);
	 //return berechnen(a,zahl,laenge,startx,starty);
	}
//_________________________________________________________________________________________
	// Hier bestimme ich die Grenze bis wohin er rechnen sollte, bringt ein kleinen Geschwindigkeits vorteil
	static int countrectangles (int a[][], int zahl, int laenge,int startx,int starty){
	int tempx=0, tempy=0,j=0, i=0, count=0;
		for(int zx = startx-1; --zx>=0;)
		    tempx +=a[zx][starty];
		
		for(int zx = starty-1; --zx>=0;)
	        tempy +=a[startx][zx];
			
		
		if(tempx > zahl || tempy > zahl){
			if(tempx > zahl)
			{
			
				while(tempx > zahl)
				{
				tempx -=a[i][starty];
				i++;
				}
				count +=berechnen(a,zahl,laenge,startx,starty,i,0);		
			}
			else
			if(tempy > zahl)
			{
			
				while(tempy > zahl)
				{
				tempy -=a[startx][j];
				j++;
				}
				count +=berechnen(a,zahl,laenge,startx,starty,0,j);
			}		
		}
		else
		count +=berechnen(a,zahl,laenge,startx,starty,0,0);
	
	return count;
	}
//__________________________________________________________________________________________	
// die Erste Idee wie ich die Vierecke berechne
static int berechnen(int a[][], int zahl,int laenge, int startx, int starty, int endx,int endy){
int count=0;


for(int x=endx; x<startx; x++)
	for(int y=endy; y<starty; y++){
    int temp=0;
		for(int zy=y; zy<=starty; zy++)
		     temp +=a[startx][zy];
	    for(int zy=y; zy<=starty; zy++)
	         temp +=a[x][zy];
		
           		
		if ((startx-x) > 1) {
			for (int zx = x+1; zx < startx ; zx++)
				temp +=a[zx][starty];

			for (int zx = x+1; zx < startx; zx++)
				temp +=a[zx][y];
		}
    if(temp == zahl)
      count++;
	
	}
	
return count;
}
//__________________________________________________________________________________________
// die zweite Idee , wie ich die Vierecke berechne, hat aber irgendwo ein logischen fehler, liefert falsche zahlen aus.
static int berechnenb(int a[][], int zahl,int laenge, int startx, int starty, int endx,int endy){
int temp=0;
if ((startx-endx) > 1) {
    for (int zx = endx; zx < startx ; zx++)
				temp +=a[zx][starty];
    if(temp > zahl)
	  return 0;
	for (int zx = endx; zx < startx; zx++)
				temp +=a[zx][endy];
    if(temp > zahl)
	  return 0;
	for(int zy=endy; zy<=starty; zy++)
		     temp +=a[startx][zy];
	if(temp > zahl)
       return 0;    
	for(int zy=endy; zy<=starty; zy++)
			temp +=a[endx][zy];
	if(temp == zahl)
       return 1;
    else
      return 0;	
}else
{		for(int zy=endy; zy<=starty; zy++)
		     temp +=a[startx][zy];
		if(temp > zahl)
        return 0;	 
	    for(int zy=endy; zy<=starty; zy++)
	         temp +=a[endx][zy];
		if(temp > zahl)
        return 0;
           		
		if ((startx-endx) > 1) {
			for (int zx = endx; zx < startx ; zx++)
				temp +=a[zx][starty];
			if(temp > zahl)
				return 0;
			for (int zx = endx; zx < startx; zx++)
				temp +=a[zx][endy];
		}
		if(temp == zahl)
			return 1;
			else
		return 0;


}
}
//__________________________________________________________________________________________
// Das Main Programm, liest aus einer Datei,  Werte aus, und packt sie in das Array.
	public static void main(String[] args) {
		try {
			DataInputStream dis = new DataInputStream(new FileInputStream(
					args[0]));
			int n = dis.readInt();
			int x = dis.readInt();
			int[][] a = new int[n][n];
			for (int i = 0; i < n; ++i) {
				for (int j = 0; j < n; ++j) {
					a[i][j] = dis.readInt();
					//Out.print(a[i][j] + "  ");
				}
				//Out.println();
			}
			Out.println();
			Out.println("Anzahl Rechtecke mit Kantensumme " + x + ": "
					+ countRectangles(a, x));
		} catch (ArrayIndexOutOfBoundsException e) {
			Out.println("Aufruf: java Simplest Dateiname");
		} catch (FileNotFoundException e) {
			Out.println("Datei existiert nicht");
		} catch (IOException e) {
			Out.println("Fehlerhafte Datei");
		}
	}

}
```



Ich hab schon eine Idee wie man das noch beschleunigen könnte, aber mir fehlt die Idee wie ich das ins Java umsetzen soll.

Und zwar geht es darum, das man ja viel rechen leistung braucht um die Kanten zu berechnen.
Und ich berechne sie jedes mal neu.
Da aber diese Kante in späteren Schritten wieder vorkommt, könnte sie man ja speichern und dann wider aufrufen.
Somit müsste rechenleistung eingespart werden, da auslesen und speichern weniger Leistung verbraucht als neu berechnen. Aber ich hab ansatz wo ich sie speichern kann/soll und wie ich sie wider zu dem benötigten Zeit punkt auslese.

Wäre für Hilfe sehr dankbar
und für andere vorschläge


----------



## blackson1c (25. Jun 2007)

Hier der Code für den Generator, der die Datei erstellt. Falls jemand Testen Will
Mit dem Aufruf 
java Generator 100 100 1 data.dat


```
import java.util.*;
import java.io.*;

class Generator {

  public static void main(String[] args) {
    try {
      int n = Integer.parseInt(args[0]);
      int x = Integer.parseInt(args[1]);
      int seed = Integer.parseInt(args[2]);
      DataOutputStream dos 
        = new DataOutputStream(new FileOutputStream(args[3]));
      dos.writeInt(n);
      dos.writeInt(x);
      int[][] a = new int[n][n];
      Random random = new Random(seed);
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
          a[i][j] = random.nextInt(10);
          dos.writeInt(a[i][j]);
        }
      } 
      dos.close();
    } catch (Exception e) {
      Out.println("Aufruf: java Generator n x seed Dateiname");
      System.exit(1);
    }
  }
```


----------



## Marco13 (25. Jun 2007)

Erstmal kurz zu dem Code:

```
static int berechnen(int a[][], int zahl,int laenge, int startx, int starty, int endx,int endy){
int count=0;


for(int x=endx; x<startx; x++)
   for(int y=endy; y<starty; y++){
    int temp=0;
      for(int zy=y; zy<=starty; zy++)
           temp +=a[startx][zy];
       for(int zy=y; zy<=starty; zy++)
            temp +=a[x][zy];
      
                 
      if ((startx-x) > 1) {
         for (int zx = x+1; zx < startx ; zx++)
            temp +=a[zx][starty];

         for (int zx = x+1; zx < startx; zx++)
            temp +=a[zx][y];
      }
    if(temp == zahl)
      count++;
   
   }
   
return count;
}
```
Wenn dort innerhalb der inneren Schleifen (oder _zwischen_ den inneren Schleifen) 'temp' schon den Wert von 'zahl' überschreitet, kann abgebrochen werden. Das könnte schonmal was bringen.

Und sonst... spontaner Gedanke: Da kann man doch bestimmt irgendwas praktisches vorberechnen ... ???:L 

Wenn man ein Rechteck der Größe 5 x 5 hat

```
4 1 6 2 5
2 5 2 7 8 
2 6 2 7 1
0 3 6 2 6
1 8 3 8 3
```
Dann könnte es hilfreich sein, schonmal vorab "aufsummierte intervalle" zu berechnen... (im Prinzip das, was du jeweils lokal mit den inneren for-Schleifen berechnest). Für die erste Zeile also 

```
4 5 11 13 18
  1 7 9 14
    6 8 13
      2 7
        5
```
Für die zweite dann

```
2 7 9 16 24
  5 7 14 22
...
```

allerdings muß man sich überlegen, OB und WIE man das gewinnbringend einsetzen kann, und das geht bei 250x250 schon gewaltig auf den Speicher. Aber wenn man für das gleiche Rechteck mehrere Anfragen sendet (also für ein gegebenes Rechteck jeweils die Quadrate mit den Summen 5, 10, 50 und 100 anzeigen will) KÖNNTE das schneller gehen, als wenn man jedesmal alles neu berechnet.

Naja. Wirklich nur eine spontane Idee. Wenn ich mal mehr Zeit habe, überleg' ich vielleicht nochmal.

Aber über ~~"irgendwelche Vorberechnungen"~~ könntest du dir auf jeden Fall mal Gedanken machen...


----------



## Marco13 (25. Jun 2007)

BlackSonic hat gesagt.:
			
		

> Also hier ist die Aufgabenstellung
> Ich habe scho ein Programm geschrieben, aber der Algo ist zu langsam. Weil wir haben die Vorraussetzung das er bei einem 250 * 250  Array unter 30 sec läuft.
> Mein Programm tut das nicht, braucht 5 min oder so


... du kannst dir das Überlegen auch sparen, und einfach nen schnelleren Rechner kaufen  :bae: :wink:


----------



## blackson1c (25. Jun 2007)

Naja, das ist ja meine Idee, da die summen sich in regenmässigen abständen widerholen
sie dann einfach irgendwo zwischen zu speichern

aber ich kriegs nicht hin bzw keine Idee wo ich das vorrächnen soll und wie ich dann die benötige summe
erst dann aufrufe wenn sie gebraucht wird.

Ich habe schon testergebnise gesehen, wo die leute geschaft habe bei einem 500*500 array es unter 30 sec zumachen. ohne sich ein neueren Rechner zuzulegen


----------



## blackson1c (25. Jun 2007)

```
static int berechnen(int a[][], int zahl,int laenge, int startx, int starty, int endx,int endy){
int count=0;


for(int x=endx; x<startx; x++)
   for(int y=endy; y<starty; y++){
    int temp=0;
      for(int zy=y; zy<=starty; zy++)
           temp +=a[startx][zy];
       for(int zy=y; zy<=starty; zy++)
            temp +=a[x][zy];
      
                 
      if ((startx-x) > 1) {
         for (int zx = x+1; zx < startx ; zx++)
            temp +=a[zx][starty];

         for (int zx = x+1; zx < startx; zx++)
            temp +=a[zx][y];
      }
    if(temp == zahl)
      count++;
   
   }
   
return count;
}
```

Ich kann da schläch ein Break oder Return reinmachen als abbruch bedinung wenn temp > zahl da
ich in diesen Forschleifen gleichzeitig mein Rechteck verkleinere.


----------



## Gast (25. Jun 2007)

das sieht nach uni-kassel aus... habe die gleiche aufgabe zu lösen 

aber im moment andere probleme.
mein algorithmus braucht für das geforderte array "nur" 12 sek. (andere teilnehmer sind schneller), macht aber komischerweise bei:
java Generator 200 600 3434 data.dat -> Anzahl Rechtecke: 199734 
nen fehler und errechnet 201331 Rechtecke...
ist wohl irgendein spezialfall... muss noch weiter suchen.


----------



## blackson1c (25. Jun 2007)

Dann kannst mir ja helfen
und sagen wieso bei mir der solange braucht ???
was ich da ändern /einfügen muss.


----------



## mephi (25. Jun 2007)

wie wärs mit dynamischer programmierung? errechnete werte einfach speichern..? man muss ja nix im voraus ausrechnen

nur mal n tip von einem anfänger was algos angeht..
wenns müll is einfach überlesen =)


----------



## Gast (25. Jun 2007)

es läuft so langsam, da du zig for-schleifen benutzt... eigentlich reicht einegeschachtelte for-schleife und noch eine while-schleife. (in meinem code)
und probiere es mit allen beispielen durch, sonst kann es immer noch einen fehler enthalten...

die idee von Marco geht auch schon in eine gute richtung, damit kannst du eine menge Zeit einsparen.


----------



## Marco13 (26. Jun 2007)

Die Anzahl der for-Schleifen ist ziemlich egal. Entscheidend ist wohl eher die allgemeine Strategie. Und die scheint bei dir schon ziemlich "ausgefeilt" zu sein, weil es ja eigentlich keine "Spezialfälle" gibt - die entstehen vermutlich durch Optimierungen, die auf Annahmen basieren, die nicht immer stimmen. Hab's gestern abend mal "brute-force" hingeschrieben, wie ich es in der ersten Antwort skizziert hatte, und bin (einschließlich Dateierzeugung!) jetzt ca. 33 Sekunden, allerdings habe ich mir über echte Optimierungen der eigentlichen Suche noch nicht viele Gedanken gemacht. Würde aber auch mal versuchen, die "such-grenzen" vorher schon einzuschränken - wenn man das bei der äußersten (von vier) for-Schleifen macht, bringt das bestimmt schon was...


----------



## blackson1c (26. Jun 2007)

wie sieht den die bruteforce code aus ???

könntest du ihn mal posten ???


----------



## Marco13 (26. Jun 2007)

Wirklich Brute-Force, zum Testen hingehackt ("main" per Hand aufrufen? :shock: ) unkommentiert und un-optimiert... Aber alleine lauffähig. 

```
import java.io.*;
import java.util.*;


class Rectangles
{

    static int n = 0;

    static int countRectangles(int a[][], int zahl)
    {
        n = a.length;

        //System.out.println("a");print(a);

        int rows[][][] = new int[n][n][n];
        int cols[][][] = new int[n][n][n];
        fill(a, rows, cols);
        System.out.println("Counting..");
        return countRectangles(rows, cols, zahl);
    }

    static int countRectangles(int rows[][][], int cols[][][], int zahl)
    {
        int count = 0;
        for(int r0 = 0; r0 < n; r0++)
        {
            for(int c0 = 0; c0 < n; c0++)
            {
                if(rows[r0][c0][0] > zahl)
                {
                    break;
                }
                if(cols[c0][r0][0] > zahl)
                {
                    break;
                }
                for(int r1 = r0 + 1; r1 < n; r1++)
                {
                    int sumC = cols[c0][r0 + 1][r1 - 1];
                    if(sumC > zahl)
                    {
                        break;
                    }
                    for(int c1 = c0 + 1; c1 < n; c1++)
                    {
                        int sumD = cols[c1][r0 + 1][r1 - 1];
                        if (sumD > zahl)
                        {
							break;
						}
                        int sumA = rows[r0][c0][c1];
                        int sumB = rows[r1][c0][c1];
                        int sum = 0;
                        sum += sumA;
                        sum += sumB;
                        sum += sumC;
                        sum += sumD;
                        if(sum == zahl)
                        {
                            count++;
                        }
                    }
                }
            }
        }
        return count;
    }


    static void fill(int a[][], int rows[][][], int cols[][][])
    {
        for(int i = 0; i < n; i++)
        {
            fillRow(a, i, rows[i]);
            fillCol(a, i, cols[i]);

            //System.out.println("row "+i); print(rows[i]);
            //System.out.println("col "+i); print(cols[i]);
        }
    }

    static void fillRow(int a[][], int rowIndex, int row[][])
    {
        int sum = 0;
        for(int j = 0; j < n; j++)
        {
            sum = 0;
            for(int k = j; k < n; k++)
            {
                sum += a[rowIndex][k];
                row[j][k] = sum;
            }
        }
    }

    static void fillCol(int a[][], int colIndex, int col[][])
    {
        int sum = 0;
        for(int j = 0; j < n; j++)
        {
            sum = 0;
            for(int k = j; k < n; k++)
            {
                sum += a[k][colIndex];
                col[j][k] = sum;
            }
        }
    }


    private static void print(int array[][])
    {
        for(int i = 0; i < array.length; i++)
        {
            for(int j = 0; j < array[i].length; j++)
            {
                System.out.print(String.format("%4d", array[i][j]));
            }
            System.out.println("");
        }
    }


    public static void main(String[] args)
    {
        long before = System.currentTimeMillis();

        //test7A();
        //test7B();
        //test10();
        //test50A();
        //test50B();
        test100A();
        test100B();
        //test150();
        //test200();
        //test250();

        System.out.println("Duration " + (System.currentTimeMillis() - before) / 1000.0);
    }


    private static void test7A()
    {
        Generator.main(new String[]
                        {"7", "30", "123", "data.dat"});
        mainx(new String[]
              {"data.dat"});
        System.out.println("Expected: 5");
    }

    private static void test7B()
    {
        Generator.main(new String[]
                        {"7", "30", "147", "data.dat"});
        mainx(new String[]
              {"data.dat"});
        System.out.println("Expected: 8");
    }

    private static void test10()
    {
        Generator.main(new String[]
                        {"10", "30", "555", "data.dat"});
        mainx(new String[]
              {"data.dat"});
        System.out.println("Expected: 23");
    }

    private static void test50A()
    {
        Generator.main(new String[]
                        {"50", "150", "555", "data.dat"});
        mainx(new String[]
              {"data.dat"});
        System.out.println("Expected: 2922     ");
    }

    private static void test50B()
    {
        Generator.main(new String[]
                        {"50", "300", "777", "data.dat"});
        mainx(new String[]
              {"data.dat"});
        System.out.println("Expected: 3590");
    }

    private static void test100A()
    {
        Generator.main(new String[]
                        {"100", "300", "975", "data.dat"});
        mainx(new String[]
              {"data.dat"});
        System.out.println("Expected: 24007");
    }

    private static void test100B()
    {
        Generator.main(new String[]
                        {"100", "100", "1", "data.dat"});
        mainx(new String[]
              {"data.dat"});
        System.out.println("Expected: 10141");
    }

    private static void test150()
    {
        Generator.main(new String[]
                        {"150", "500", "234", "data.dat"});
        mainx(new String[]
              {"data.dat"});
        System.out.println("Expected: 88949");
    }

    private static void test200()
    {
        Generator.main(new String[]
                        {"200", "600", "3434", "data.dat"});
        mainx(new String[]
              {"data.dat"});
        System.out.println("Expected: 199734 ");
    }

    private static void test250()
    {
        Generator.main(new String[]
                        {"250", "1000", "22", "data.dat"});
        mainx(new String[]
              {"data.dat"});
        System.out.println("Expected: 451879 ");
    }


    public static void mainx(String[] args)
    {
        try
        {
            DataInputStream dis = new DataInputStream(new FileInputStream(args[0]));
            int n = dis.readInt();
            int x = dis.readInt();
            int[][] a = new int[n][n];
            for(int i = 0; i < n; ++i)
            {
                for(int j = 0; j < n; ++j)
                {
                    a[i][j] = dis.readInt();
                    //System.out.print(a[i][j] + "  ");
                }
                //System.out.println();
            }
            System.out.println();
            System.out.println("Anzahl Rechtecke mit Kantensumme " + x + ": " + countRectangles(a, x));
        }
        catch(ArrayIndexOutOfBoundsException e)
        {
            e.printStackTrace();
            System.out.println("Aufruf: java Simplest Dateiname");
        }
        catch(FileNotFoundException e)
        {
            System.out.println("Datei existiert nicht");
        }
        catch(IOException e)
        {
            System.out.println("Fehlerhafte Datei");
        }
    }

}


class Generator
{

    public static void main(String[] args)
    {
        try
        {
            int n = Integer.parseInt(args[0]);
            int x = Integer.parseInt(args[1]);
            int seed = Integer.parseInt(args[2]);
            DataOutputStream dos
                = new DataOutputStream(new FileOutputStream(args[3]));
            dos.writeInt(n);
            dos.writeInt(x);
            int[][] a = new int[n][n];
            Random random = new Random(seed);
            for(int i = 0; i < n; ++i)
            {
                for(int j = 0; j < n; ++j)
                {
                    a[i][j] = random.nextInt(10);
                    dos.writeInt(a[i][j]);
                }
            }
            dos.close();
        }
        catch(Exception e)
        {
            System.out.println("Aufruf: java Generator n x seed Dateiname");
            System.exit(1);
        }
    }
}
```


----------



## blackson1c (26. Jun 2007)

Frage wieso sagt mir dein Programm bei einer eingabe von java Generator 250 1000 22 data.dat
das

Excemption in thread "main" java.lang.OutofMemoryError: Java heap space
at Rectangles.countRectangles<Rectangles.java: 15)
at Rectangles.main(Rectangles.java: 127)

hab die Classen wider aufgetrennt, in einzelne Dateien.


Und in deinem Original Code :

kommen die Fehler in 
Excemption in thread "main" java.lang.OutofMemoryError: Java heap space
at Rectangles.countRectangles<Rectangles.java: 19)
at Rectangles.mainx<Rectangles.java: 255)
at Rectangles.test250<Rectangles.java: 231)
at Rectangles.main<Rectangles.java: 140)


----------



## Marco13 (26. Jun 2007)

Mit 
java -Xmx1300m Rectangles
wird's gehen. Hab ja gesagt: Es ist recht speicheraufwändig :roll:


----------



## Marco13 (26. Jun 2007)

Man könnte das ganze bestimmt auch so formulieren, dass man die Informationen, die ich da in den n^3-Arrays speichere nur dann (und dort) vorberechnet, wo man sie braucht (und nachher wieder wegwirft), aber habe ja gesagt: Das war nur brute force und ganz pragmatisch hingeschrieben.... Alles schönere (weniger speicheraufwändige, effizientere) wäre vermutlich entsprechend aufwändiger.


----------



## blackson1c (26. Jun 2007)

Ich versuche gerade das Irgendwie zubegreifen, und zugucken wo ich den Speicher aufwand reduzieren kann. Aber durch mein ansatz bekomme ich falsche werte raus.


----------



## Marco13 (26. Jun 2007)

Kannst dir ja mal von Hand ein Beispiel basteln

```
0 0 0 0 0 
0 1 1 1 0
0 1 0 1 0
0 1 1 1 0
0 0 0 0 0
```
Und darin alle Rechtecke suchen, die eine Summe von 8 haben. Vielleicht hast du ja eine Summe von 12, wenn du die "Ecken" doppelt zählst? (Sooo weit habe ich deinen Code nicht nachvollzogen - und du solltest auch schwer überlegen, ob du dich an meinen Code orientieren willst - das mit dem n^3 ist wirklich nicht schön!)


----------



## blackson1c (26. Jun 2007)

Nu ok, dann wie kann ich teile deines Codes bzw den Prinzip der Speicherung, in meinen Integrieren, weil diese Speicherung, ist das was bei mir den vorteil bringen würde. Da in meinem Code jedesmal neu berechnet wird


----------



## Marco13 (26. Jun 2007)

Das erfordert einige Aktionen. Unter anderem: Nachdenken.  :shock:  

Mal im Ernst: Wenn man das richtig gut und effizient machen will, kann das schon kompliziert werden. Das schüttelt man (auch nach etlichen Jahren Programmiererfahrung) nicht einfach so aus dem Ärmel (vermutlich (!!!) nichtmal dann, wenn man _zufällig_(!!!) die geniale, zündende Idee hat). 

In dem, was ich da (auf Basis einer _spontanen_ (d.h. nicht gut durchdachten) Idee) an einem Abend schnell hingeschrieben hatte, wird ja am Anfang einmal ALLES vorberechnet. (Und das haut einem dann auch den Speicher voll). Man braucht aber zu jedem Zeitpunkt nur einen geringen Teil dieser Informationen. Die spannende Frage ist, WAS man WANN berechnen muß, damit man möglichst wenig "Müll" im Speicher mit sich rumschleppt, und möglichst wenig doppelt berechnen muß. 

Die "Grundidee" (die in meinem Code allerdings schlechtestens umgesetzt ist) ist: 
Man hat (etwa) 
- n*n Positionen, wo die obere linke Ecke des Rechtecks sein kann und
- n*n Positionen, wo die untere rechte Ecke des Rechtecks sein kann
Ein Rechteck besteht also aus
- zwei gleichlangen Zeilen-Teilen (die in der gleichen Spalte anfangen und enden) und 
- zwei gleichlangen Spalten-Teilen (die in der gleichen Zeile anfangen und enden)
Jetzt ist die Frage, wie man die (n*n)*(n*n) möglichen Rechtecke so überprüft, dass man bereits berechnete Zeilen- und Spalten-Teile möglichst oft wiederverwenden kann. ALLE Zeilen- und Spalten-Teile am Anfang zu berechnen, und dann nurnoch drauf zuzugreifen (wie in meiner Lösung) ist zwar relativ effizient (wenn auch noch weit weg von optimal) aber zu speicherfressend. Und eine bessere Lösung zu finden - ist deine Aufgabe :roll:


----------



## Gast (4. Jul 2007)

wenn der heap space mit einer größeren speicherzuweisung bei 250 nicht abstürzt, dann wird es bei 500 oder mehr sicher tun.

man kann ja einige summen zwischenspeichern, doch sollten es eben nicht zuviel sein, damit das programm auf für sehr große summen noch funktionsfähig bleibt.

ich werde meinen source hier übermorgen posten, wenn es noch jemanden interressiert. ist zwar nicht super schnell, aber dafür supers chlank programmiert.


----------



## Gast (6. Jul 2007)

```
import java.io.*;

class Rectangles {

  static int countRectangles(int[][] a, int s) {
    int rectangles = 0;
    int n = 4;
    double q = s / 9D;
    while ( q > n ) {
      n += 2;
    }
    int n2 = n / 2;
    int[][] xArray = new int[a.length][a.length];
    int[][] yArray = new int[a.length][a.length];
    for ( int i = 0; i < a.length; ++i ) {
      for ( int j = 0; j < a.length; ++j ) {
        if ( i > 0 && j > 0 ) {
          xArray[i][j] = xArray[i][j-1] + a[i][j];
          yArray[i][j] = yArray[i-1][j] + a[i][j];
          int points = ((i - 1) * 2) + ((j + 1) * 2);
          if ( points >= n ) {
            // starte Suche
            rectangles += rectanglesSearch(yArray, xArray, a, i, j, s, n, n2);
          }
        }
        else if ( i == 0 && j == 0 ) {
          xArray[i][j] = a[i][j];
          yArray[i][j] = a[i][j];
        }
        else if ( j == 0 ) {
          xArray[i][j] = a[i][j];
          yArray[i][j] = yArray[i-1][j] + a[i][j];
        }
        else if ( i == 0 ) {
          xArray[i][j] = xArray[i][j-1] + a[i][j];
          yArray[i][j] = a[i][j];
        }
      }
    }
    return rectangles;
  }

  static int rectanglesSearch(
         int yArray[][], int xArray[][], int a[][], int y, int x, int s, int n, int n2) {
    int rectangles = 0;
    int yy = y - 1;
    int xx = x - 1;
    int x1 = x + 1;
    if ( x1 >= n2 ) {
      xx = x1 - n2;
      yy = y - 1;
    } else if ( x1 < n2 ) {
      xx = 0;
      yy = y - ( ((n - (x1 * 2)) / 2 ) - 1 );
    }
    while ( true ) {
      int sum = 0;
      int sum_l = 0;
      if ( xx == 0 ) {
        sum += xArray[yy][x];
        sum += xArray[y][x];
      } else {
        sum += xArray[yy][x] - xArray[yy][xx-1];
        sum += xArray[y][x] - xArray[y][xx-1];
      }
        sum += yArray[y-1][x] - yArray[yy][x];
        sum_l = yArray[y-1][xx] - yArray[yy][xx];

      if ( sum + sum_l == s ) { ++rectangles; }

      if ( yy == 0 && xx == 0 ) { break; }

      if ( sum > s ) {
        if ( yy == 0 || xx + 1 == x ) { break; }
          --yy;
          xx = x - 1;
          int q = y - yy + 1;
          if ( q < n2 ) {
            xx = x - ( n2 - q );
          }
      } else {
        if ( xx != 0 ) {
          --xx;
        } else {
          --yy;
          xx = x - 1;
          int q = y - yy + 1;
          if ( q < n2 ) {
            xx = x - ( n2 - q );
          }
        }
      }
    }
    return rectangles;
  }

  public static void main(String[] args) {
    try {
      DataInputStream dis =
        new DataInputStream(new FileInputStream(args[0]));
      int n = dis.readInt();
      int x = dis.readInt();
      int[][] a = new int[n][n];
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
          a[i][j] = dis.readInt();
        }
      }
      Out.println(countRectangles(a, x));
      //Out.println("Anzahl Rechtecke mit Kantensumme " + x + ": "
      //            + countRectangles(a, x));
    } catch (ArrayIndexOutOfBoundsException e) {
      Out.println("Aufruf: java Simplest Dateiname");
    } catch (FileNotFoundException e) {
      Out.println("Datei existiert nicht");
    } catch (IOException e) {
      Out.println("Fehlerhafte Datei");
    }
  }

}
```


----------



## Marco13 (6. Jul 2007)

Jo ist ja dann recht flott....


----------



## Guest (6. Jul 2007)

Es geht aber auch 9x schneller, nur bin ich leider nicht drauf gekommen. Dazu hätte ich wohl einen komplett neuen Ansatz finden müssen.


----------



## Gast (9. Jul 2007)

source und ergebnisse der gewinner:
http://www.plm.eecs.uni-kassel.de/AD2007


----------

