In C gibt es einen Unterschied in Zeit und Abstand zwischen einem m × n 2-dimensionalen Array und einem 1-dimensionalen Array der Länge m × n (für große Werte von m und n)? Ist der Zugriff auf Elemente mit einem 1-dimensionalen Array schneller?Leistung von 2-dimensionalen Arrays vs 1-dimensionalen Arrays
In C sind zweidimensionale Arrays nur ein einfaches Indexierungsschema für eindimensionale Arrays. Genau wie bei einem 1D-Array ordnen 2D-Arrays einen einzelnen Block zusammenhängenden Speichers zu, und die A[row][col]-Notation ist ähnlich zu A[row*NCOLS+col].
Normalerweise, wenn Sie sind Ihre eigene multidimensionalen Arrays mit eindimensionalen Arrays implementieren, dann würden Sie eine Indizierungsfunktion schreiben:
int getIndex(int row, int col) { return row*NCOLS+col; }
Compiler inlines diese Funktion Unter der Annahme, hier die Leistung wäre genau das gleiche wie wenn Sie die integrierte Indexfunktion von 2D-Arrays verwenden.
Zur Veranschaulichung:
#define NROWS 10
#define NCOLS 20
Dieses:
int main(int argc, char *argv[]) {
int myArr[NROWS*NCOLS];
for (int i=0; i<NROWS; ++i) {
for (int j=0; j<NCOLS; ++j) {
myArr[getIndex(i,j)] = i+j;
}
}
return 0;
}
sollen das gleiche wie dies auszuführen:
int main(int argc, char *argv[]) {
int myArr[NROWS][NCOLS];
for (int i=0; i<NROWS; ++i) {
for (int j=0; j<NCOLS; ++j) {
myArr[i][j] = i+j;
}
}
return 0;
}
Obwohl als AraKpointed out, wenn Sie viel um Reihen springen werden , und die Reihen sind sehr groß, Sie könnten viele Seitenfehler treffen ... in diesem Fall der Kunde Die om-Indizierungsfunktion (mit umgeschalteten Zeilen und Spalten) könnte helfen, könnte aber auch einfach ändern, welche der Dimensionen in einem zweidimensionalen Array Sie als Zeilen behandeln und welche Sie als Spalten behandeln.
Ich glaube nicht, dass es einen Unterschied gibt. Intern behandelt c ein zweidimensionales Array wie mehrere eindimensionale Arrays nacheinander.
Wie bei allen Dingen Leistung, kann Ihre Laufleistung variieren. Es kann eine Art subtile Zeigerarithmetikdifferenz geben. Führen Sie zeitgesteuerte Tests für beide Szenarien aus. Wer schneller läuft, gewinnt.
Kann man auch Arrays in C nicht implementieren, wie zum Beispiel 'int ** array' und dann 'array = malloc (sizeof (int *) * rows); für (i = 0; i
@derobert: Diese Struktur wird oft als "Ragged Array" bezeichnet. Es hat einen ähnlichen syntaktischen Zugriff, ist aber nicht dasselbe wie ein gewöhnliches 2d-Array. – dmckee
@dmckee zackig oder gezackt? –
Ich rate nur, aber ich würde sagen, dass ein 1d-Array schneller ist als ein 2d-Array. Es wäre jedoch nicht messbar schneller. Ein bisschen wie $ 1.000.000.01 ist mehr als $ 1.000.000.
Ich würde verwenden, was einfacher zu codieren ist.
Wenn Sie das so genannte zweidimensionale Array in C verwenden, wird der Compiler tatsächlich für Sie das Mapping in eindimensionales Array vornehmen. Wenn Sie ein eindimensionales Array verwenden und es als zweidimensionales Array behandeln möchten, müssen Sie das Mapping selbst schreiben.
Das Einzige, um das Sie kümmern müssen, ist, dass Sie zeilenweise auf das Array zugreifen sollten, da der C-Compiler Ihr zweidimensionales Array Zeile um Zeile speichert. Wenn Sie spaltenweise auf ein "großes" zweidimensionales Array zugreifen, treten wahrscheinlich Seitenfehler auf. Selbst wenn Sie in einer Sprache programmieren, die nur eindimensionale Arrays unterstützt, können Sie das Mapping problemlos in eine beliebige Anzahl von Dimensionen schreiben.
Werfen Sie einen Blick auf diese Wikipedia-Artikel, wenn Sie die mapping row-wise tun möchten. Ihre Zuordnung könnte spaltenweise erfolgen, wie zum Beispiel FORTRAN-Matrizen.
Robert hat Recht.Indexierungsausdrücke werden in arithmetische Ausdrücke für Zeiger kompiliert, sodass kein Unterschied besteht.
Was jedoch Auswirkungen haben kann, ist die Zugriffsreihenfolge. Daher sollten Sie die Dinge selbst implementieren, damit Sie die Zugriffsreihenfolge steuern können. Zum Beispiel Spalte zuerst vs Zeile erste Formulare.
Bei modernen Prozessoren kann der Zugriff auf große Arrays mit unterschiedlichen Schritten zu unerwarteten Leistungsunterschieden führen. Sequenzieller Zugriff ist immer am schnellsten und andere Schritte können aufgrund von Cache-Interaktionen bis zu 30 Mal langsamer sein. Multidimensionale Arrays, bei denen die inneren Dimensionen eine Potenz von zwei sind, haben oft eine schlechte Leistung, da sie mit der Cache-Assoziativität interagieren. Um diese Probleme zu verstehen, gibt es keinen wirklichen Ersatz für Messungen.
Sie müssen nicht Ihr eigenes schreiben, um das Layout zu bestimmen; Das Layout des eingebauten C ist klar definiert. Sie können wählen, welches Sie verwenden möchten, indem Sie 'array [row] [column]' vs. 'array [column] [row] schreiben' – derobert
Ja, das stimmt. Ich hätte ein besseres Beispiel geben sollen, wie die verschiedenen Schemata für blockierte Matrizen. –
Wie gesagt, der Unterschied ist wirklich, wie Sie auf Ihre Artikel zugreifen: Was zählt, wenn Ihre Elemente Layout im Speicher sind, die linear ist, zumindest auf gemeinsamen Architekturen. Also alles, was Sie wirklich haben, ist 1D-Array, die 2D, etc ... ist "nur" eine Bequemlichkeit, und ein vernünftiger Compiler sollte die Indizierung optimieren - aber in der Praxis, wenn Sie mehr als ein paar Variablen haben, scheitern oft Compiler auf Arch wie x86 wegen der Registerverknappung.
Jetzt hängt es von Ihrer Anwendung ab, aber ich denke, dass Sie mit einem 1d-Layout standardmäßig denken sollten, besonders wenn Sie mehrere Dimensionen behandeln müssen. Das erste Problem mit mehrdimensionalen Arrays in C ist, dass Sie sie nicht dynamisch zuordnen können - wenn Sie pro Reihe zuweisen, werden Sie schreckliche Leistungen haben, weil Sie kein zusammenhängendes Stück Gedächtnis haben. Einzelheiten hierzu finden Sie unter FFTW doc.
Beachten Sie, dass Sie Ihr einzelnes Speicherelement immer mit einer praktischen Array-Indexierung darüber beschreiben können (Sie ordnen einen großen nxm-Speicherblock zu und erstellen dann ein Array mit einem n-Zeiger für jede Zeile).
Ausgezeichnete Erklärung, danke! –