Code I:Welche Loop-Konfiguration benötigt mehr Zeit zum Ausführen?
for(i=0; i<100; i++){
for(j=0; j<1000; j++){
x = y;
}
}
-Code II:
for(i=0; i<1000; i++){
for(j=0; j<100; j++){
x = y;
}
}
Können Sie erklären, warum eine dieser Schleifenkonfigurationen wird mehr Zeit als die anderen zu laufen nehmen?
Das hängt wirklich von mehreren Faktoren ab, die Sie nicht direkt kontrollieren können.
Wie in den Kommentaren user David V sagt, werden beide nur von einem guten Compiler eliminiert werden. Wenn dies nicht der Fall ist, werden sie in einen Maschinencode mit Verzweigungsbefehlen übersetzt. Wenn ein Prozessor Code mit Verzweigungen ausführt, verwendet er eine sogenannte spekulative Verzweigungsvorhersage, die sich je nach den genauen Anweisungen, in die der Code übersetzt wird, unterschiedlich verhält. Andere Faktoren können eingreifen - wie zum Beispiel Cache-Fehler des Codes. Sie können es nicht wirklich sagen, bis Sie sorgfältig und gründlich die Ergebnisse analysieren.
Eine gute Antwort ist wahrscheinlich: Sie sind beide unwirksame Möglichkeiten, etwas in einem zweidimensionalen Array zu finden, und Sie sollten versuchen, eine Art Indexierung, um es zu entfernen.
Dies war ein Interview-Frage, nicht wahr? Nun, erwarten Sie ein Interview Antwort :)
Im Allgemeinen die innere Schleife hat große Chancen, vollständig in Cache, so dass die 100 out-1000 in sollte schneller sein. Aber Compiler sind so intelligent ...
Es scheint keinen Code überhaupt hier einbezogen zu werden, die mehr als eine Cache-Zeile verwenden würde, so dass es shouldn‘ t machen überhaupt einen Unterschied. –
Ja, in diesem speziellen Fall. Meine Überlegung betraf einen generischen Fall mit zwei verschachtelten Schleifen. Grüße –
Ich kann darauf hinweisen, dass jeder gute Compiler, aber nicht so gut wie von David oben erwähnt, wird dies zu verschiedenen CPU-Anweisungen kompilieren, und keine Notwendigkeit haben für die Verzweigung, oder Jede Verzweigungsvorhersage-Logik, die hilft, Pipeline-Blockaden zu vermeiden.
Tatsächlich gibt es ein triviales Konstrukt auf CPU-Ebene (die Schleifenanweisung), das das obige mit minimaler Softwareemulation durchführen wird. Daher ist die Multiplikation kommutativ, also ist 100x1000 oder 1000x100 gleich.
Während alle Antworten im Allgemeinen korrekt sind, meiner Meinung nach. Das heißt, würde es optimiert, und es wäre auf den Maschinencode abhängen, usw. ich in dem stark vereinfachteste Fall denke, keine Optimierung und keine spekulative Verzweigung angenommen (was nicht realistisch sein kann), Code 1 würde beweisen, schneller sein, weil es ist eine gewisse Menge an Overhead beim Einrichten der Schleifen. Sie müssen nämlich die Variablen i und J deklarieren. Da der Overhead der äußeren Schleife immer nur einmal auftritt, ist die innere Schleife hier der wirkliche Faktor. Da in Code 1 der innere Loop nur 100-mal eingerichtet ist und Code 2 den inneren Loop 1000-mal aufruft, sollte Code 1 schneller sein. Auch dies ist im einfachsten Fall, wofür wahrscheinlich die Interview- oder Quizfrage gesucht wurde.
Mit einem guten Compiler, beide Schleifen werden beseitigt :) –
Dies ist ein Quiz? : D – Fabian
@David V. Es sei denn, x und y werden als flüchtig deklariert. – mouviciel