In C++, die die Möglichkeit ist, sequentiell auf ein 2D-Array zuzugreifen (Speicherblock weise)

Question

Edit: Ich habe die schneller/effizienter aus dem Titel der Frage entfernt, wie es irreführend war .. meine Absicht war nicht Optimierung, aber Verständnis Arrays . Entschuldigen Sie die Umstände!

int array[10][10], i, j; 

for(i=0;i<10;i++) 
{ 
    for(j=0;j<10;j++) 
     std::cin>>array[i][j]; 
} 

Versus

int array[10][10], i, j; 

for(i=0;i<10;i++) 
{ 
    for(j=0;j<10;j++) 
     std::cin>>array[j][i]; 
} 

Ich bin mir ziemlich sicher, dass die Antwort mit dem zu tun hat, wie Arrays auf Hardware-Ebene umgesetzt werden; dass die Syntax [] [] nur die Abstraktion eines Programmierers ist, um die Visualisierung/Modellierung zu unterstützen. Allerdings habe ich, welche der oben genannten Code greift auf den Speicherblock sequentiell von Anfang bis Ende vergessen ...

Danke für alle Antworten ...

Nur mein Verständnis zu bestätigen, bedeutet dies der erste Code äquivalent zu

int array[10][10], k; 

for(k=0;k<100;k++) 
{ 
    std::cin>>*(array+k); 
} 

Answer 1

Abgesehen von der Tatsache, dass Warten auf Benutzereingaben deutlich langsamer als der Array-Zugriff ist, ist der erste schneller.

Check out this page on 2D array memory layout, wenn Sie mehr Hintergrund zu diesem Thema möchten.

mit dem zweiten Sie A[0], A[10] ... A[1], A[11].

Die erste wird sequentiell A[0], A[1], A[2] ..

Answer 2

Die 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. aber wenn Sie j beheben und die i variieren, betrachten Sie Elemente, die 10 (die Länge eines Subarrays) auseinander sind, also sind sehr verteilt.

Answer 3

Ich bin damit einverstanden, dass diese vorzeitige Optimierung ist, aber ...

C++ speichern Matrizen in Reihenhauptordnung. Dies wird dazu führen, dass die erste Syntax schneller wird (auf der meisten Hardware), da Sie auf das Array in der Reihenfolge im Speicher zugreifen und die Lokalität in Ihrem Datenzugriff beibehalten.

Weitere Informationen zum Array-Speicher finden Sie unter see this article.

Answer 4

die korrekte Weise sind die Überprüfung ein Array in C++ iterieren 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 zu einem Zeitpunkt in den Cache lädt und nicht die ganze Zeit ungültig machen muß.

Answer 5

Für kleine Arrays macht es keinen Unterschied!

Bei größeren Arrays ist die erste Option jedoch schneller, da sie auf das gesamte Array in der Sequenz zugreifen, da es physikalisch im Speicher abgelegt ist. Zusätzlich wird es möglich sein, den Compilern Zugriff auf eine ganze Reihe von Tricks zu geben, um dies 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 ausführen.

Answer 6

Sie möchten immer Speicherorte in Gruppen basierend auf Lokalität zugreifen, also erste Option. Lokalität wird in drei verschiedenen Schichten ins Spiel kommen:

Prozessor-Cache. Sie möchten zusammen auf den Speicherort zugreifen, der in dieselbe Cachezeile fällt. Das Lesen des ersten Elements nimmt den Cache-Lese-Lesetreffer, aber nachfolgende 2-3 Lesevorgänge fallen in den bereits zwischengespeicherten Inhalt.

Translation Lookaside Puffer. Sie möchten auf Speicherorte auf derselben Seite (normalerweise 4 KB) zugreifen, so dass die virtuell-physische Übersetzung bereits im Prozessor gespeichert ist. Sie möchten auf Speicherorte auf der gleichen Seite zugreifen, so dass die Seite im Arbeitsprozess beibehalten wird und nicht in die Bereitschaftsliste verschoben oder sogar ausgetauscht wird

Die Dinge variieren von Prozessor zu Prozessor und von OS zu OS, aber nur durch kleine Ränder, es sei denn, Sie sprechen einige exotische Plattformen.