Mit O (n) bekannt und Systemtakt bekannt, können wir die Ausführungszeit des Codes berechnen

-1

Die Zeit Komplexität des Codes bekannt ist. Das System, auf dem das Programm ausgeführt wurde, ist Intel Corei3, das Dual Core und CPU @ 2.4ghz ist - es hat 4 logische Prozessoren. Mit diesen Details, wie kann die Ausführungszeit des Codes berechnet werden?Mit O (n) bekannt und Systemtakt bekannt, können wir die Ausführungszeit des Codes berechnen

public class PerfmTest { 
    public static void main(String[] args) { 
     getexeTime(1000000); 
    } 

    public static void getTime (long n) { 
     // long startTime = System.currentTimeMillis(); 
     long startTime = System.nanoTime(); 
     long k = 0; 
     for (int i = 1; i <=5; i++) { 
      // k = k + 5; 
     } 
     // long endTime = System.currentTimeMillis(); 
     long estimatedTime = System.nanoTime() - startTime; 
     //System.out.println("Execution time for n = " + n + " is " + (endTime - startTime) + " milliseconds"); 
     System.out.println("Execution time for n = " + n + " is " + estimatedTime + " nanoseconds"); 
    } 
}

Die Ausgabe war 855 Nanosekunden.

Quelle

2016-11-15 Uma

Ich vermute, Sie wussten nicht, dass Code ohne beobachtbare Nebenwirkungen zur Kompilierzeit optimiert werden kann. Egal, was ** willst du mit dieser Übung erreichen? –

Ich bin mir bewusst, dass der Code optimiert ist. Aber Punkt ist, wie in der Theorie sein O (n) und wie es mit 2 Doppelkernen funktioniert. Ich arbeite an einem Lehrmittelprojekt. – Uma

In der Theorie ist es nicht O (n), weil der Compiler die Schleife eliminieren kann (du liest nie 'k' nach der Schleife - also gibt es keine Nebenwirkungen, um sie zu entfernen - selbst wenn du die Addition hineinlegst) Theorie). Ihr aktueller Code ist also theoretisch "O (1)". Achte auch auf Mikro-Benchmarks. Es gibt einen JIT, und Kaltläufe unterscheiden sich von Warmläufen (und es kann mehrere Läufe dauern, um JIT auszulösen). –

Wenn ich Sie richtig verstehe, fragen Sie, ob wir die Laufzeit durch Kenntnis der Systemspezifikationen und des betreffenden Codes berechnen können. Die Antwort darauf ist Nein, wir können die Ausführungszeit nicht berechnen.

Der Grund ist, dass der Code nicht isoliert ausgeführt wird. Diese vier Prozessoren sind nicht nur mit Ihrem Code. Das Betriebssystem macht Dinge im Hintergrund, Dienste laufen und so weiter.

In der Tat können wir nicht nur die Laufzeit des Codes berechnen, aber wir können nicht einmal zukünftige Laufzeiten vorhersagen, wenn wir bereits die Laufzeit kennen. Alles kann während einer zweiten Ausführung des Codes passieren, die die Ausgabe ändern könnte. Mehr Kontextwechsel, mehr Hintergrundaufgaben oder irgendetwas anderes.

Ich habe diese Effekte aus erster Hand viele Male beim Ausführen von Leistungstests erlebt. Die gleiche Testsuite erzeugt unterschiedliche Zeitvorgaben, wenn der Computer längere Zeit im Leerlauf war oder wenn der letzte Start ein Kaltstart im Gegensatz zu einem Standby-/Wiederaufnahme-Vorgang war.

Wenn Sie fragen, wie Sie messen können die Laufzeit Ihres Codes, alle oben genannten gelten immer noch. Sie sprechen im Wesentlichen davon, ein Experiment durchzuführen. In einem Experiment müssen alle externen Variablen gesteuert werden. Das System muss für jeden Testlauf den gleichen Zustand haben, was technisch möglich ist, aber sicherlich weit über den Rahmen dieser Frage hinausgeht.

Das einzige, was wir können tun mit jeder vernünftigen Erwartung des Erfolgs ist vorhersagen, dass Algorithmus A wird besser als Algorithmus B (und sogar das wird manchmal unerwartete Ergebnisse für verschiedene Eingaben, Eingabegrößen, etc. ergeben). Wir kann nicht genau vorhersagen, wie lange Algorithmus A dauert.

Zusammenfassung

Ohne eine extrem kontrollierten Umgebung (über den Rahmen dieser Frage) ist es unmöglich, Schätzung zu berechnen, oder auch die Laufzeit eines beliebigen Stück Code zu messen.

Quelle

2016-11-15 01:43:22 nhouser9

Ich denke, Sie könnten eine no-Strings-Attach-Timing-Schätzung von Algorithmen vornehmen, wenn Sie die Komplexität kennen und die Verarbeitungszeit pro Iteration vernünftig schätzen können. – Bohemian

@Bohemian Wir können sehr gute Schätzungen von Algorithmen relativ zueinander machen - da stimme ich definitiv überein. Wir können keine sehr guten Schätzungen zu absoluten Zeitpunkten machen, gerade weil wir die Verarbeitungszeit pro Iteration nicht vernünftig schätzen können. Es variiert mit Compiler, Hardware, Systemstatus, Software und vielen zusätzlichen Faktoren; Darüber hinaus sind diese Variationen oft nicht trivial. Das ist nur meine Erfahrung als professioneller Performance-Analyst. – nhouser9

@ Nhouser9, so wird das Wesentliche nur zum Vergleich verwendet. – Uma

-1

Mit O (n) bekannt und Systemtakt bekannt ist, können wir die Ausführungszeit des Codes berechnen.

No. O (N) bedeutet nur, dass die Ausführungszeit wächst linear mit N, d.h.über eine lineare Gleichung der Form

t = aN+b

wo y die Zeit ist, ist NN und a und b Konstanten sind, aber es macht Sie die Konstanten nicht sagen.

Quelle

2016-11-15 02:31:09 EJP

Haben Sie das Bild von O (n), dass wir die Ausführungszeit nicht berechnen können. – Uma

Ich kann nicht zwei Lösungen markieren die Website sagt, obwohl ich es als Lösung markieren wollte. – Uma

Wenn ich das sagen darf, halte ich das für eine bessere Antwort als die andere, da es Ihren Irrtum an der Wurzel anspricht. Der andere geht davon aus, dass es prinzipiell möglich ist, gibt aber Gründe, warum nicht in der Praxis: Mit anderen Worten, er teilt Ihren Irrtum. – EJP

Mit O (n) bekannt und Systemtakt bekannt, können wir die Ausführungszeit des Codes berechnen

Antwort

Verwandte Themen