Exception in der metode

Gregor

JavaNewbie schrieb:

Hallo an alle, erstmal vielen dank dass ihr mir versucht zu helfen.
Mein problem ist einfach folgendes. ich will von 49 zahlen alle möglichen 6er kombinationen haben. also: 1,2,3,4,5,6 dann 1,2,3,4,5,7 und so weiter. dann sind bei 49 zahlen fast 14000000 kombinationen. Jetzt brauche ich halt eine lösung um diese zu berechnen und irgendwo abzulegen. Ein Array oder sonst etwas. Jedoch muß es variabel sein da ich vieleicht morgen schon nur 30 zahlen testen will. Das ergebnis will ich dann ausdrucken oder analysieren. mehr nicht. Gibt es da eine schönere lösung als meine?

@Gregor
Das ich das in c++ besser gelöst habe, liegt daran dass ich c++ ein bißchen besser kann als Java. In java kannte ich nur so eine lösung für einen mehrdimensionalen Vektor. Du sagst aber dass man dass noch besser lösen könnte. Ich wäre echt neugierig wie man dass noch besser machen kann. Kannst du mir einen Tip geben?

1. Ich habe schon längst angegeben, wie du deinen Speicherverbrauch auf etwa 300MB runterkriegst. Realisieren mußt du das schon selbst, ich bin nicht dein "Coder".

2. Ob es eine wirklich bessere Lösung gibt, hängt sehr davon ab, was genau du mit den Daten machen möchtest. Zum Beispiel wäre es interessant zu wissen, ob du deine "Analyse" vielleicht durchführen kannst, bevor die Zahlen in den Vektor kommen. Angenommen, du willst zum Beispiel in der Analyse Kombinationen herausfiltern, die von Lottospielern häufig genommen werden: Dann könntest du die Analyse für eine Kombination durchführen, bevor du sie in einem Vektor oder so speicherst. Die Kombinationen, die übrigbleiben würden, könntest du nach der Analyse abspeichern (oder drucken oder was auch immer). Das würde den Speicherverbrauch vermutlich um Größenordnungen senken.

Sgt. Nukem

JavaNewbie schrieb:

wie schön dass ihr auf so ein blödsinn immer eine antwort habt.

JavaNewbie schrieb:

Mein problem ist nicht das papier sondern dass ich es zum laufen bekomme.

Du willst das Papier zum Laufen bekommen..?!

Hallo Leute!

Tja einen Speicher Überlauf muss man einfach in Java mal geschaft haben! Nur dann weiß man das man einen Fehler im Aufbau des Programmes hat.

Du benötigt nach meiner Rechnung ein Array, zum berechnen der Kominationen, ein Array für die Zuordung Ziffern zu den abzubildente Ziffern und einen Vektor für die Endablage.

Die Brute Fore Erzeugung der Kombinationen erledigen einige Schleifen und gut ist.

Der Speicher wird hauptsächlich nur zum Endlagern benutzt und das wars.

cu Codehure

PS: Code? Nö keine Lust. Aber denke doch mal an einen Tacho!

Sgt. Nukem

Hi.

Hatte gerade Langeweile und da ist mir Dein Problem nochmal eingefallen.

Hab' mir Deinen C++-Code geschnappt und versucht 1:1 nach Java umzusetzen.

Also bei mir läuft das ohne irgendwelche Heap-Tricksereien.

import java.util.ArrayList;

public class Permutation
{

	static class Zahl
	{
		int z1;
    	int z2;
    	int z3;
    	int z4;
    	int z5;
    	int z6;
    }

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

    	System.out.println("Beginne mit Rechnen\n");

		ArrayList<Zahl> vVollSys = new ArrayList<Zahl>(14000000);
		ArrayList<Integer> vZahl = new ArrayList<Integer>();

		for(int i = 1; i < 50; i++) vZahl.add(i);

		int a = 0;
 	    int b = 1;
    	int c = 2;
  		int d = 3;
  		int e = 4;
  	  	int f = 5;

  		Zahl z = new Zahl();

    	z.z1 = ((Integer)vZahl.get(a)).intValue();
    	z.z2 = ((Integer)vZahl.get(b)).intValue();
    	z.z3 = ((Integer)vZahl.get(c)).intValue();
    	z.z4 = ((Integer)vZahl.get(d)).intValue();
    	z.z5 = ((Integer)vZahl.get(e)).intValue();
    	z.z6 = ((Integer)vZahl.get(f)).intValue();
    	vVollSys.add(z);

    while(vZahl.get(a) != vZahl.get(vZahl.size()-6)){

        if((Integer)vZahl.get(f)<(Integer)vZahl.get(vZahl.size()-1))
               f=f+1;
            else
            {
                if((Integer)vZahl.get(e)<(Integer)vZahl.get(vZahl.size()-2))
               {
                  e=e+1;
                  f=e+1;
               }
               else
               {
                   if((Integer)vZahl.get(d)<(Integer)vZahl.get(vZahl.size()-3))
                  {
                     d=d+1;
                     e=d+1;
                     f=e+1;
                  }
                  else
                  {
                      if((Integer)vZahl.get(c)<(Integer)vZahl.get(vZahl.size()-4))
                     {
                        c=c+1;
                        d=c+1;
                        e=d+1;
                        f=e+1;
                     }
                     else
                     {
                         if((Integer)vZahl.get(b)<(Integer)vZahl.get(vZahl.size()-5))
                        {
                           b=b+1;
                           c=b+1;
                           d=c+1;
                           e=d+1;
                           f=e+1;
                        }
                        else
                        {
                           a=a+1;
                           b=a+1;
                           c=b+1;
                           d=c+1;
                           e=d+1;
                           f=e+1;
                        }
                     }
                  }
               }
            }

    z.z1 = ((Integer)vZahl.get(a)).intValue();
    z.z2 = ((Integer)vZahl.get(b)).intValue();
    z.z3 = ((Integer)vZahl.get(c)).intValue();
    z.z4 = ((Integer)vZahl.get(d)).intValue();
    z.z5 = ((Integer)vZahl.get(e)).intValue();
    z.z6 = ((Integer)vZahl.get(f)).intValue();
    vVollSys.add(z);
    }

    	System.out.println("Rechnen Fertig\n");
    	System.out.println("Das Ergebnis lautet: " + vVollSys.size());

    	long Ende = System.currentTimeMillis();

    	System.out.println("\nBenoetigt: " + (Ende - Start) + " Millisekunden");
	    System.in.read();

	}

}

Bei C++ hab' ich auch mal ein "long Start = timeGetTime()" eingebunden.

Ergebnis:

C++: (einfaches cl.exe)

Beginne mit Rechnen
Rechnen Fertig
Das Ergebnis lautet: 13983816
Benoetigt: 14260 Millisekunden

Speicherauslastung: 329.300 KByte (laut TaskManager)

Mit Optimierungen (/Ox /O2):
1346 Millisekunden

Am Speicherverbrauch ändert sich quasi nichts.

Java:
C:\Tools\JCreator\MyProjects\Permutation>java Permutation
Beginne mit Rechnen

Rechnen Fertig

Das Ergebnis lautet: 13983816

Benoetigt: 3685 Millisekunden

Speicherverbrauch: 63.056 KByte

Viele Vielen Dank Sgt. Nukem. Du hast mir das Leben gerettet. Ich habe das Theman fast schon abgeschrieben und haben es mit C++ weitergemacht. Jetzt hast du mich aber auf etwas neugierig gemacht. Wie hast du es denn geschafft den C++ code so zu optimieren dass du so eine wahnsinnsgeschwindigkeit bekommen hast. Das ist ja enorm an zeit die du sparst. Könntest du mir einen tip geben wir du das gemacht hast?

Hi,
da fällt mir ein. Wie komme ich denn an die Werte ran in dem Vektor. Wie soll ich zum beispiel aus der ersten Zeile den Wert der zahl2 bekommen?

Gregor

@Sgt. Nukem: lol! Gib mal die ersten 20 Permutationen (nach der gesamten Berechnung) unter Java aus. Dann weißt du, warum der Speicherverbrauch so gering ist.

EDIT: War das gar beabsichtigt? Könnte man ja bei dem " " glatt denken.

Sgt. Nukem

ROTFL

Hahaha... zugegebenermassen war das _nicht_ beabsichtigt!!
Ich hatte mich sogar gestern selber gewundert und mir gedacht, daß irgendwas nicht stimmt, aber war dann zu faul noch weiter nachzuforschen...

Es fehlt natürlich ein "new Zahl()" in jeder while-Iteration, was nicht ganz unerheblich auf den Speicherverbrauch aufschlägt... :p
Der Speicherverbrauch wird dann nahezu identisch zu C++ (und ist nur mit -Xmx benutzbar). Die Ausführungszeit wird aber beachtlich länger...

P.S.: Ähhh... doch, NATÜRLICH war der Fehler beabsichtigt! Schließlich soll der Code-Leser noch was lernen! Genauso wie die 1337en Hacker auch in ihre Exploits immer kleine Fehler einbauen... :p

Gregor

Ich habe das nochmal geringfügig überarbeitet. Vielleicht arbeitet es sogar noch korrekt:

import java.util.ArrayList;

public class Permutation
{

   private static class Zahl
   {
      public Zahl(byte z1, byte z2, byte z3, byte z4, byte z5, byte z6)
      {
         this.z1=z1;
         this.z2=z2;
         this.z3=z3;
         this.z4=z4;
         this.z5=z5;
         this.z6=z6;
      }

      final byte z1;
      final byte z2;
      final byte z3;
      final byte z4;
      final byte z5;
      final byte z6;
   }

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

      System.out.println("Beginne mit Rechnen\n");

      ArrayList<Zahl> vVollSys = new ArrayList<Zahl>(14000000);

      byte a = 0;
      byte b = 1;
      byte c = 2;
      byte d = 3;
      byte e = 4;
      byte f = 5;

      final byte max = 49;

      vVollSys.add(new Zahl((byte)(a+1),(byte)(b+1),(byte)(c+1),(byte)(d+1),(byte)(e+1),(byte)(f+1)));

      while(a != max-6)
      {

         if(f < max-1) 
         {
            f=(byte)(f+1);
         }
         else
         {
            if(e < max-2)
            {
               e=(byte)(e+1);
               f=(byte)(e+1);
            }
            else
            {
               if(d < max-3)
               {
                  d=(byte)(d+1);
                  e=(byte)(d+1);
                  f=(byte)(e+1);
               }
               else
               {
                  if(c < max-4)
                  {
                     c=(byte)(c+1);
                     d=(byte)(c+1);
                     e=(byte)(d+1);
                     f=(byte)(e+1);
                  }
                  else
                  {
                     if(b < max-5)
                     {
                        b=(byte)(b+1);
                        c=(byte)(b+1);
                        d=(byte)(c+1);
                        e=(byte)(d+1);
                        f=(byte)(e+1);
                     }
                     else
                     {
                        a=(byte)(a+1);
                        b=(byte)(a+1);
                        c=(byte)(b+1);
                        d=(byte)(c+1);
                        e=(byte)(d+1);
                        f=(byte)(e+1);
                     }
                  }
               }
            }
         }
         vVollSys.add(new Zahl((byte)(a+1),(byte)(b+1),(byte)(c+1),(byte)(d+1),(byte)(e+1),(byte)(f+1)));
      }

      System.out.println("Rechnen Fertig\n");
      System.out.println("Das Ergebnis lautet: " + vVollSys.size());

      long Ende = System.currentTimeMillis();

      System.out.println("\nBenoetigt: " + (Ende - Start) + " Millisekunden");
      System.out.println("ENTER erwartet.");
      System.in.read();
   }

}

Output:

Beginne mit Rechnen

Rechnen Fertig

Das Ergebnis lautet: 13983816

Benoetigt: 7997 Millisekunden
ENTER erwartet.

Die C++-Version schafft es ohne Optimierungen in 13,787s, mit Optimierung "-O3" in 1,206s.

Sgt. Nukem

Mit Byte hatte ich's heut' nachmittag auch schon probiert...

Ändert aber nur geringfügig was am Speicherverbrauch.

Ich denke mal zeitlich am meisten frisst die Objekt-Erstellung, was?!

Denke ich nicht, weil das Erstellen eines Objekts in Java nicht viel mehr als dem Erhöhen eines Pointers entspricht (vergleichbar mit dem Stack).
Allerdings machen viele lebende Objekte dem GC zu schaffen. Viele temporäre sind nicht schlimm, aber bei dem Speicherverbrauch gehe ich davon aus, dass es viele lebende gibt und die muss der GC alle rumschieben.

Gregor

Optimizer schrieb:

Allerdings machen viele lebende Objekte dem GC zu schaffen. Viele temporäre sind nicht schlimm, aber bei dem Speicherverbrauch gehe ich davon aus, dass es viele lebende gibt und die muss der GC alle rumschieben.

Scheint zu stimmen. Wenn ich meinen Profiler richtig interpretiere, dann geht für den GC etwa 90% der Zeit drauf.

Fällt einem etwas ein, wie man das optimieren kann?

Man könnte vielleicht insgesamt ein großes byte-Array mit 6*14000000 Elementen nehmen und das als Speicher verwenden.

Gregor

Joar, das bringt was:

import java.util.ArrayList;

public class Permutation2
{
   public static void main(String[] args) throws Exception
   {
      long Start = System.currentTimeMillis();

      System.out.println("Beginne mit Rechnen\n");

      byte[] numbers = new byte[6*14000000];

      byte a = 0;
      byte b = 1;
      byte c = 2;
      byte d = 3;
      byte e = 4;
      byte f = 5;

      final byte max = 49;

      int index = 0;
      numbers[index++]=(byte)(a+1);
      numbers[index++]=(byte)(b+1);
      numbers[index++]=(byte)(c+1);
      numbers[index++]=(byte)(d+1);
      numbers[index++]=(byte)(e+1);
      numbers[index++]=(byte)(f+1);

      while(a != max-6)
      {

         if(f < max-1) 
         {
            f=(byte)(f+1);
         }
         else
         {
            if(e < max-2)
            {
               e=(byte)(e+1);
               f=(byte)(e+1);
            }
            else
            {
               if(d < max-3)
               {
                  d=(byte)(d+1);
                  e=(byte)(d+1);
                  f=(byte)(e+1);
               }
               else
               {
                  if(c < max-4)
                  {
                     c=(byte)(c+1);
                     d=(byte)(c+1);
                     e=(byte)(d+1);
                     f=(byte)(e+1);
                  }
                  else
                  {
                     if(b < max-5)
                     {
                        b=(byte)(b+1);
                        c=(byte)(b+1);
                        d=(byte)(c+1);
                        e=(byte)(d+1);
                        f=(byte)(e+1);
                     }
                     else
                     {
                        a=(byte)(a+1);
                        b=(byte)(a+1);
                        c=(byte)(b+1);
                        d=(byte)(c+1);
                        e=(byte)(d+1);
                        f=(byte)(e+1);
                     }
                  }
               }
            }
         }
         numbers[index++]=(byte)(a+1);
         numbers[index++]=(byte)(b+1);
         numbers[index++]=(byte)(c+1);
         numbers[index++]=(byte)(d+1);
         numbers[index++]=(byte)(e+1);
         numbers[index++]=(byte)(f+1);
      }

      System.out.println("Rechnen Fertig\n");
      System.out.println("Das Ergebnis lautet: " + (index/6));

      long Ende = System.currentTimeMillis();

      System.out.println("\nBenoetigt: " + (Ende - Start) + " Millisekunden");
      System.out.println("ENTER erwartet.");
      System.in.read();
   }

}

Output:

Beginne mit Rechnen

Rechnen Fertig

Das Ergebnis lautet: 13983816

Benoetigt: 777 Millisekunden
ENTER erwartet.

Jetzt ist die Geschwindigkeit also etwa äquivalent zur optimierten C++-Version. Der Unterschied wird größtenteils am höheren Speicherverbrauch der C++-Version liegen.

Wenn man mit dem Array danach noch arbeiten will, dann lohnt es sich vielleicht, einen kleinen Wrapper darum zu schreiben, mit dem man dann einfach auf die einzelnen Permutationen zugreifen kann.

EDIT: BTW: Das ist ein interessantes Resultat. So eine Optimierung war mir bisher unbekannt. Da hat sich der Thread ja noch richtig gelohnt.

Hallo an alle,

ich habe da noch zwei fragen:
Wenn ich einen Vektor erstelle wie zum Beispiel.
....
class zahl{
int z1;
int z2;
}

Zahl z = new Zahl();
Vector.add(z);

Wie kann ich denn auf diesen Vektor zugreifen wenn ich die zahlen haben will?

Außerdem habe ich gesehen dass ihr öfters folgende deklaration gemacht habt:

ArrayList<zahl> liste = new ArrayList<zahl>(14000000);

Ich frage mich nur wie ihr das durch den compiler bekommen habt. Bei mir geht es auf keinen fall. Sowas wie <zahl> kennt er nicht.

Jop, du musst Java 5.0 verwenden. Dann ist es auch einfacher, das Objekt wieder rauszubekommen.

Ich denke man könnte noch etwas Speicher sparen, wenn man bedenkt
das pro Zahl maximal 6 Bit benötigt werden, also pro Kombination
6*6=36 Bit. Vielleicht einen 64-Bit Typ (long?) nehmen und
entsprechende Methoden zum setzen/holen der Zahlen.
Kostet natürlich Zeit, aber ich denke hier ist Speicherverbrauch wichtiger.

Jockel

Sgt. Nukem

Optimizer schrieb:

Denke ich nicht, weil das Erstellen eines Objekts in Java nicht viel mehr als dem Erhöhen eines Pointers entspricht (vergleichbar mit dem Stack).
Allerdings machen viele lebende Objekte dem GC zu schaffen. Viele temporäre sind nicht schlimm, aber bei dem Speicherverbrauch gehe ich davon aus, dass es viele lebende gibt und die muss der GC alle rumschieben.

Könntest Du das mal näher erläutern?!
Was genau meinst Du damit? *nixraff*

Gregor schrieb:

Man könnte vielleicht insgesamt ein großes byte-Array mit 6*14000000 Elementen nehmen und das als Speicher verwenden.

Gregor schrieb:

Joar, das bringt was:

Cool. Sowas wird ja auch bei den neuen NIO-Sockets verwendet, um Päckchen schnell abzuschicken. ByteBuffer.

Jockelx schrieb:

Kostet natürlich Zeit, aber ich denke hier ist Speicherverbrauch wichtiger.

Meinst Du nicht die drölfzig Bit-Manipulationen würden die Zeit ins Unermessliche steigern??!

Sgt. Nukem schrieb:

Meinst Du nicht die drölfzig Bit-Manipulationen würden die Zeit ins Unermessliche steigern??!

War das jetzt ironisch ?
Der einzige wirkliche Zeitaufwand ist doch der Funktionsaufruf.
Die Bit-Manipulationen kostet einen Takt - auch bei der Menge wohl
auszuhalten. Man muss ja auch keine Methode schreiben, oder
vielleicht kann ein Java-Kompiler sowas auch inline machen?

Jockel