Bearbeiten: Ich habe die schnellere / effizientere aus dem Titel der Frage entfernt, da es irreführend war. Meine Absicht war nicht Optimierung, sondern das Verstehen von Arrays. Entschuldige den Ärger!
%Vor%Versus
%Vor%Ich bin mir ziemlich sicher, dass die Antwort damit zu tun hat, wie Arrays auf Hardwareebene implementiert werden; dass die Syntax [] [] nur die Abstraktion eines Programmierers ist, um die Visualisierung / Modellierung zu unterstützen. Ich habe jedoch vergessen, welcher der obigen Codes vom Anfang bis zum Ende der Reihe auf den Speicherblock zugreift ...
Danke für alle Antworten ...
Nur um mein Verständnis zu bestätigen, bedeutet das, dass der erste Code äquivalent zu
ist %Vor%Abgesehen davon, dass das Warten auf Benutzereingaben deutlich langsamer ist als der Arrayzugriff, ist der erste schneller.
Schauen Sie sich diese Seite im 2D-Array-Speicherlayout an Wenn Sie mehr Hintergrundinformationen zu diesem Thema wünschen.
Mit dem zweiten prüfen Sie A[0], A[10] ... A[1], A[11].
Die erste wird sequenziell A[0], A[1], A[2] ..
Der erste hat eine bessere räumliche Lokalität. Weil der erste Index der Index eines Subarrays ist und der zweite Index das Element innerhalb dieses Subarrays ist; Wenn Sie also i fixieren und die j variieren, betrachten Sie Elemente, die alle innerhalb eines Subarrays liegen und somit nahe beieinander liegen. Wenn Sie jedoch j und die i s ändern, betrachten Sie Elemente, die 10 (die Länge eines Subarrays) voneinander entfernt sind, also sehr verteilt.
Ich stimme zu, dass dies eine vorzeitige Optimierung ist, aber ...
C ++ speichert Matrizen in der Reihenfolge der Zeilen. Dies wird dazu führen, dass die erste Syntax schneller wird (auf der meisten Hardware), da Sie im Speicher auf das Array zugreifen und die Lokalität in Ihrem Datenzugriff beibehalten.
Einzelheiten zum Array-Speicher finden Sie in diesem Artikel .
Die richtige Methode zum Iterieren eines Arrays in C ++ ist die erste Methode. Das Iterieren eines Arrays "outside-in", wie Sie es im zweiten Beispiel getan haben, ist in der Regel langsamer, da Sie bei jeder Iteration der inneren Schleife sehr unterschiedliche Speicherorte erhalten. Das Array ist sequentiell reihenförmig angeordnet, wobei die erste Methode nach den inneren Zeilen iteriert. Dies gibt dem Code die beste Möglichkeit, den CPU-Cache effektiv zu nutzen, indem er eine Zeile nach der anderen in den Cache lädt und nicht die ganze Zeit ungültig machen muss.
Für kleine Arrays macht es keinen Unterschied!
Jedoch wird die erste Option für größere Arrays schneller sein, da sie auf das gesamte Array in der Sequenz zugreifen wird, da es physisch im Speicher gespeichert ist. Zusätzlich wird es möglich sein, den Compilern Zugriff auf eine ganze Reihe von Tricks zu geben, um dies noch weiter zu beschleunigen.
Die zweite Option springt über den gesamten Speicher für jeden einzelnen Durchlauf des Arrays, dies wird Ihre Cache-Trefferrate reduzieren und im schlimmsten Fall Sie in viele E / A-Paging-virtuellen Speicher ein- und auslagern.
Sie möchten immer auf Speicherorte in Gruppen basierend auf der Lokalität zugreifen, also erste Option. Ort wird auf drei verschiedenen Ebenen ins Spiel kommen:
Die Dinge variieren von Prozessor zu Prozessor und von Betriebssystem zu Betriebssystem, aber nur mit kleinen Gewinnspannen, es sei denn, Sie sprechen über einige exotische Plattformen.