Exception in der metode

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