Algorithmen und Datenstrukturen · Senior · Frage 51 von 75
Was ist cachefreundlich daran, ein 2D-Array in C-artigem Layout Zeile für Zeile zu durchlaufen?
- 1Zeilen sind immer kürzer als Spalten
- 2Zeilen liegen zusammenhängend, Lesezugriffe treffen also dieselben Cache-Zeilen
- 3Die CPU kann Zeilenzugriffe vorhersagen, Spaltenzugriffe nicht
Antwort zeigen
Richtige Antwort: Zeilen liegen zusammenhängend, Lesezugriffe treffen also dieselben Cache-Zeilen
Erklärung
Bei zeilenweisem Layout sind a[i][j] und a[i][j+1] Nachbarn. Spaltenweises Durchlaufen springt pro Schritt eine ganze Zeile weiter und verfehlt den Cache, was bei gleicher O(n²)-Arbeit um ein Mehrfaches langsamer sein kann.