falsche implementierung von currentTimeMillis() ?

[m4libu17]

hi leute, es geht um folgendes:

ich soll die n-te fibonaccizahl, und n! (n Fakultät) jeweils iterativ und rekursiv berechnen und für jeden vorgang die dauer bestimmen.

was ich hab ist dashier:

public class Rekursion{
    long zeit = 0;
    
    // Gibt die Zeit (in ms) zurück die für die letzte Berechnung nötig war.
    public long getLastRuntime(){
      return zeit;
    }          
    
    // Nicht rekursive Berechnung der n-ten Fibonacci Zahl.
    public long Fibonacci( int n){ 
      zeit = System.currentTimeMillis(); 
      long fib = 0;      
      for(long fib1 = 0, fib2 = 1, i=2; i <= n; i++){
         fib =  fib1 + fib2;
         fib1 = fib2;
         fib2 = fib;
      }         
      zeit = System.currentTimeMillis()-zeit;
      return fib;
    }
    
    // Rekursive Berechnung der n-ten Fibonacci Zahl.
    public long FibonacciRekursiv( int n){
      zeit = System.currentTimeMillis();
      long fib = 0;
      if(n == 0){
         fib = 0;
      }
      if(n == 1){
         fib = 1;
      }
      else if(n >= 2){
         fib = FibonacciRekursiv(n-1) + FibonacciRekursiv(n-2);
      }
      zeit = System.currentTimeMillis()-zeit;
      return fib;
    }                                         
    
    // Rekursive Berechnung von n!.
    public long FakultaetRekursiv( int n){
      zeit = System.currentTimeMillis();
      long fak = 1;    
      if(n >= 2){
         fak = Fakultaet(n-1)*n;
      }
      zeit = System.currentTimeMillis()-zeit;
      return fak;
    }          
        
    // Nicht rekursive Berechnung von n!.                             
    public long Fakultaet( int n){
      zeit = System.currentTimeMillis();      
      long fak = 1;
      for(int k = 2; k <= n; k++){
         fak = fak * k;
      }
      zeit = System.currentTimeMillis()-zeit;
      return fak;
    }                                     
}

für die zeit iterativ berechnen er mir meistens 0 ... wahrscheinlich weil die benutzen zahlen zu klein sind, was mich aber stört, ist, dass bei der Zeit für die rekursive Berechnung bei beiden das gleiche rauskommt (fakultaetrekursiv ist immer exakt 1 größer)

die berechnungen der funktionswerte an sich stimmen, nur die zeiten eben nicht


danke schonmal im vorraus für die hilfe

 

[Network]

Hab das Problem jetzt nicht verstanden, aber für die Zeitmessung nimmst du am besten System.nanoTime(); ist genauer aber wie immer muss man beachten, dass es sich bei einem Computer nicht um eine Atomuhr handelt.

Gruß
Net

 

[Marco13]

Bei einer Rekursiven Funktion die Zeitmessung IN der Funktion zu machen ist etwas ... problematisch

 

[Kevin94]

Solche Microbenchmarks sind sinnlos, aus drei Gründen:

• Die Ausfürhrungszeit sollte deutlich unter 1 ms liegen
• Die Auflösung von currentTimeMillis liegt OS abhängig bei 5 bis 50 und mehr ms (auf Windows afaik >10ms)
• Mögliche Aussage lassen sich nur über den Durchschnitt von sehr vielen Durchläufen (>100.000) ableiten, da Java/ dem Thread während des Test der Prozessor enzogen werden kann und so die Zeitmessung nur aussagt, wie lange die Methode von einem anderen Prozess unterbrochen wurde

Nimm System.nanoTime() und den Durchschnitt von min. 1000 Durchläufen, um ein vernünftiges Ergebnis zu bekommen.

 

[Da_Tebe]

Die operation ist zu fix. nanoTime() sollte gehen =)

oder mal eine richtig hohe Fib zahl übergeben

Edit: Oh, da haben meine Vorredner schneller getippt

 

[Marco13]

Ja, nimm' die bisherige Zeitmessung mal raus, und mach' die Methoden static, dann kann man mit sowas wie

    public static void main(String[] args)
    {
        long before = 0;
        long after = 0;
        int runs = 10;
        long sum = 0;
        for (int r=0; r<runs; r++)
        {
            System.out.println("Run "+r);
            for (int n=25; n<=40; n+=5)
            {
                before = System.nanoTime();
                sum += Fibonacci(n);
                after = System.nanoTime();
                System.out.println("Iterative for "+n+" took "+(after-before)/1e6);
                
                before = System.nanoTime();
                sum += FibonacciRekursiv(n);
                after = System.nanoTime();
                System.out.println("Recursive for "+n+" took "+(after-before)/1e6);
            }
        }
        System.out.println(sum);
    }

zumindest eine (SEHR eindeutige) Tendenz erkennen. Aber aus den o.g. Gründen ist das immernoch Hinterfragenswert. Es gibt viele Infos dazu, z.B. Java theory and practice: Anatomy of a flawed microbenchmark oder AngelikaLanger.com - Java Performance - Micro-Benchmarking - Angelika Langer Training/Consulting

 

[m4libu17]

ja gut also das mit nanoTime hab ich ausprobiert .... wird nicht als korrekt angenommen
wies aussieht is die erwartete zeit anders .... in den rekursiven hab ich die anfängliche zeitsetzung bearbeitet, sodass er sie nicht immer wieder auf ne neue zeit setzt falls ich den rekursiven aufruf mache ... aber es scheint auch in der iterativen berechnung von Fakultaet bspw. fehler in der Zeitmessung zu geben....

 

[Network]

Ich bin mir immernoch nicht sicher, aber woran erkennst du das eine Zeitmessung fehlerhaft ist?
Dass sie niemals korrekt sein kann, hat bereits Heissenberg erwiesen, aber sie kann annähernd richtig sein.

[...] wird nicht als korrekt angenommen wies
aussieht is die erwartete zeit anders [...]

Wer sagt es wäre nicht korrekt, dein Lehrer/Prof/[unwichtige Drittperson]?
Und was heißt "erwartete" Zeit? Beachte es handelt sich um Nanosekunden, also 1/1.000.000.000 Sekunde. (Jedoch nicht um die Genauigkeit)

Das Ergebniss der Zeitmessung ist jedesmal eine andere, weil die Länge der Ausführung des Codes Situationsbedingt ist im Prozessor und ist selbstverständlich von Computer zu Computer anderst.
Hinzu kommt die Besonderheit hinzu, das Java(?) Programme mit der Anzahl der Aufrufe und der Länge der Ausführungszeit an Geschwindigkeit gewinnen.

Jetzt würde mich echt mal interessieren was dein Zeitergebniss ist, und was die vorgegebene "richtige" Zeitmessung ist.


Gruß
Net

 

[m4libu17]

Ich weiß dass das nie GENAU ist...

Geprüft wird das mit einem separaten Programm auf der Unihomepage.
Das Programm stellt der Prof. bereit.

Als Ergebnis seh ich nur WO der Fehler in etwa liegt,
allerdings seh ich nicht wie das geprüft wird.

Ich weiß also beim hochladen ob's richtig war,
Wenn's falsch war nur dass etwas falsch war mit der Ausgabe dass
getLastRuntime einen falschen Wert für Fakultaet(0) liefert.

 

[Kevin94]

Als Ergebnis seh ich nur WO der Fehler in etwa liegt,
allerdings seh ich nicht wie das geprüft wird.

Wie meinen? Sagt dir das Prüf-Programm die Zeit für einen Aufruf ist zu lang/kurz oder eine bestimmte Zeile der Ausführung dauert zu lange/kurz. Bei letzerem hätte ich keine Ahnung wie sowas gemessen werden sollte und bei ersterem würde ich mir ernsthaft über den Prof gedanken machen, wenn du nicht irgendwas missverstanden hast und die Zeitmessung tatsächlich für exakt 1 Durchlauf und eine Angabe in ms gemacht werden soll.

Für die Berechnung von Fakultaet(0) benötig mein Rechner ca. 25ns im Durchschnitt über 100.000 Durchläufe und 250ns für Fakultät(10_000), also beides weit weg von 1ms. Ich vermute mal stark, dass die Zeitangabe in ns und nicht in ms erfolgen soll und du die Aufgabenstellung falsch gelesen hast. [IRONIE]Oder das die Test gedacht sind auf dem Z3 mit 100Hz ausgeführt zu werden.[/IRONIE]

 

[m4libu17]

Hier die Angabe:


Blatt 13
Allgemein

Abgabe spätestens bis Di. 29.01.2013, 09:00 Uhr

Verwenden Sie für das "Hauptprogramm"(Demo) als Klassen- und Dateinamen immer BspXX, wobei XX die Aufgabennummer zweistellig ist.

Die erste Zeilen jeder abgegebenen Datei sollen den eigenen Vornamen, Nachnamen und die Matrikelnummer als Java-Kommentar beinhalten, z.B.

// Vorname Nachname, Matrikelnummer

Aufgabe 13

Implementieren Sie folgende Klasse:

public class Rekursion{
public long getLastRuntime(); // Gibt die Zeit (in ms) zurück die für die letzte Berechnung nötig war.
public long Fibonacci( int n); // Nicht rekursive Berechnung der n-ten Fibonacci Zahl.
public long FibonacciRekursiv( int n); // Rekursive Berechnung der n-ten Fibonacci Zahl.
public long Fakultaet( int n); // Nicht rekursive Berechnung von n!.
public long FakultaetRekursiv( int n); // Rekursive Berechnung von n!.
}
Die Methoden Fibonacci(n) und FibonacciRekursiv(n) sollen die n-te Zahl der Fibonacci Folge berechnen und zwar als rekursive und als nicht rekursive Variante. Die Fibonacci Folge ist definiert als:

f(0) = 0
f(1) = 1
f(n) = f(n-1)+f(n-2) Für n >= 2
Die Methoden Fakultaet(n) und FakultaetRekursiv(n) sollen n! berechnen und zwar als rekursive und als nicht rekursive Variante. Die Fakultät (auch Faktorielle genannt) ist wie folgt definiert:

f(0) = 1
f(n) = n*f(n-1) Für n >= 1
Die Implementierungen der Methoden Fibonacci, FibonacciRekursiv, Fakultaet und FakultaetRekursiv sollen eine Zeitmessung enthalten. Die Zeitmessung soll die Zeit (in ms), die für die Berechnung nötig war, speichern. Mit getLastRuntime soll man die gespeicherte Zeit (also die Ausführzeit der letzten Berechnung) abfragen können.

Ausblick:

Das Beispiel ist nicht nur Übung, sondern auch Ausblick auf die Vorlesung Algorithmen und Datenstrukturen, in der es nicht nur um Algorithmen, sondern auch um deren Laufzeit geht. In der Hinsicht überlegen Sie sich, wie man das Demo Programm (Bsp13.java) gestalten könnte, um folgende Fragestellungen zu beantworten:

Wie unterscheidet sich die Laufzeit von Fibonacci(n) und FibonacciRekursiv(n) abhängig von n?
Wie unterscheidet sich die Laufzeit von Fakultaet(n) und FakultaetRekursiv(n) abhängig von n?
Hinweis:
Zur Zeitmessung kann man die Methode currentTimeMillis() aus java.lang.System verwenden, siehe javadoc.

 

[m4libu17]

Ich denke nicht dass ich da was missverstanden habe

Und nanoTime soll man ja garnicht benutzen.

 

[Marco13]

Das hättest du so auch schon früher posten können. Also, nicht nanoTime, und die vogegebenen Methoden implementieren, OK. Aber die Zeitmessung in der rekursiven Funktion macht IMHO so keinen Sinn. Vielleicht würde ein Muster wie

private long lastTime = 0;

public long FibonacciRecursive( int n){ 
    long before = System.currentTimeMillis();
    long result = FibonacciRecursiveImpl(n);
    long after = System.currentTimeMillis();
    lastTime = after-before;
    return result;
}

private long FibonacciRecursiveImpl(int n)
{
    // Ruft intern wieder FibonacciRecursiveImpl (!) auf
    // Macht aber NICHTS mehr, was mit Zeitmessung
    // zu tun hat 
}

das ganze schon übersichtlicher machen.

 

[Kevin94]

Ich bin sprachlos. Ich hab keine Ahnung, was der Prof. als Ergebnis erwartet oder sich dabei gedacht hat, vielleicht steh ich auch einfach nur auf dem Schlauch. Nach einem kleinen Test auf meinem Rechner, dürfte die Methode Fakultaet erst ab einem Wert von 2^20 einen Ausführungszeit von > 1ms haben und ähnliches sollte wohl auch für alle anderen Methoden gelten. Wenn man bedenkt, dass es bei den rekursiven Versionen ab einem Wert von ca. 3000 zu einem StackOverflowError kommt, kann man davon ausgehen das die Ausführungszeit immer 0ms ist (ca. 5000ns für FakulaetRekursiv(1000)).

Nebenbei bemerkt hast du im Code aus dem ersten Post einen Fehler: Die rekursive Variante der Fakultät ruft die normale iterative Fakulät auf, richtig müsste sie die rekursive aufrufen.

 

[m4libu17]

mithilfe von Marco13's letztem post hab ich mein programm noch etwas anders gestaltet und der onlinecheck hats diesmal in ruhe gelassen.... mir wird zwar nur "OK" angezeigt und ned was getestet wurde, aber ich kann euch mal gerne die endversion geben.... scheint wie gesagt jetzte alles richtig zu sein

btw: den overflow hatte ich teilweise schon bei 35 liegt wohl aber nicht am programmstück sondern dem uraltrechner
und werte von mehr als 1millisekunde hatte ich auch schon bei werten von c.a. 20

aber wie gesagt hier die (scheinbar richtige) version:

public class Rekursion{
    private long zeit = 0;
    
    // Gibt die Zeit (in ms) zurück die für die letzte Berechnung nötig war.
    public long getLastRuntime(){
      return zeit;
    }          
    
    // Nicht rekursive Berechnung der n-ten Fibonacci Zahl.
    public long Fibonacci( int n){
      long before = System.currentTimeMillis(); 
      long fib = 0;
      if(n == 1)
         return 1;      
      for(long fib1 = 0, fib2 = 1, i=2; i <= n; i++){
         fib =  fib1 + fib2;
         fib1 = fib2;
         fib2 = fib;
      } 
      long after = System.currentTimeMillis();
      zeit = after-before;
      return fib;
    }  
    
    public long FibonacciRekursiv( int n){ 
       long before = System.currentTimeMillis();
       long result = f(n);
       long after = System.currentTimeMillis();
       zeit = after-before;
       return result;
    }
    // Rekursive Berechnung der n-ten Fibonacci Zahl.
      public long f( int n){
      long fib = 0;
      if(n == 0)
         fib = 0;
      if(n == 1)
         fib = 1;
      if(n >= 2)
         fib = f(n-1) + f(n-2);
      return fib;
    }                                           
    
    //ab n = 21 bietet long nicht genug speicherplatz
    
    
    public long FakultaetRekursiv( int n){
       long before = System.currentTimeMillis();
       if(n == 0)
         return 1;
       long result = FakultaetRekursivImpl(n);
       long after = System.currentTimeMillis();
       zeit = after-before;
       return result;
    }   

    // Rekursive Berechnung von n!.
      public long FakultaetRekursivImpl( int n){
      long fak = 1; 
      if(n == 1 || n== 0)
         return 1;
      if(n >= 2){
         fak = FakultaetRekursivImpl(n-1)*n;
      }
      return fak;
    }          
       
    // Nicht rekursive Berechnung von n!.   
    public long Fakultaet( int n){
      long before = System.currentTimeMillis(); 
      long fak = 1;
      for(int k = 1; k <= n; k++){
         fak = fak * k;
      }
      long after = System.currentTimeMillis();
      zeit = after - before;
      return fak;
    }                                     
}