Was ist eine gute Möglichkeit, ein zweidimensionales Array zu "rotieren" (kreisförmige Verschiebung)?

Question

Dies ist wirklich eine konzeptionelle (sprachunabhängige) Frage, aber um der Erklärung willen werde ich C++ verwenden. Ich würde eine Antwort bevorzugen, die in andere Sprachen portiert werden kann (keine Zeigerarithmetik oder Speichertricks).

---

Sagen wir, wir haben:

• arr, unsere rechteckigen 2D-Array von einer beliebigen Art T
• void shift(int dx, int dy), die Funktion, die die "Rotation"
• numRows führt, die Anzahl der Reihen
• numCols, die n Umbra von Spalten

shift() verschiebt sich die Anordnung so, dass alle Zeilen dx Plätze nach unten bewegt wird, und die Reihen geschoben außerhalb der Grenzen wird Wrap-around zum Anfang zurück. (Das gleiche gilt für die Spalten und dy.) Lassen Sie uns sagen, das ist es, was unser Angebot wie zunächst aussieht:

{{a1, a2, a3, a4}, 
{b1, b2, b3, b4}, 
{c1, c2, c3, c4}, 
{d1, d2, d3, d4}}; 

Nachdem wir unsere Funktion aufrufen: shift(2,1), arr sollte wie folgt aussehen:

{{c4, c1, c2, c3}, 
{d4, d1, d2, d3}, 
{a4, a1, a2, a3}, 
{b4, b1, b2, b3}}; 

In dieser Fall dx war , so bewegt alles nach unten zwei Plätze und dy war , also alles auch mov ed auf die rechts einen Platz.

war hier mein Ansatz zur Lösung dieses Problems:

void shift(int dx, int dy) 
{ 
    T newArr[numRows][numCols]; 
    for(int r = 0; r < numRows; r++) 
    { 
     for(int c = 0; c < numCols; c++) 
     newArr[(r + dx) % numRows][(c + dy) % numCols] = arr[r][c]; 
    } 
    for(int r = 0; r < numRows; r++) 
    { 
     for(int c = 0; c < numCols; c++) 
     arr[r][c] = newArr[r][c]; 
    } 
} 

Ich bin nicht zufrieden mit diesem Code, weil es weder zeiteffizient noch raumeffizient ist. Ich suche eine elegantere Lösung, die mehr mit weniger Loops und weniger Speicher benötigt.

Answer 1

Eine andere Möglichkeit wäre, die Elemente überhaupt nicht zu bewegen. Die Idee wäre, eine Funktion zu haben, die den/die verwendeten Indexe so transformiert, dass das ursprüngliche Array gedreht angezeigt wird.

Sie erhalten einen leichten Leistungseinbruch, indem Sie das ursprüngliche Array mit einem geeigneten Datentyp umhüllen. Aber wann immer Sie rotieren (oder spiegeln, oder umgekehrt oder was auch immer), gewinnen Sie in Bezug auf Erinnerung und Zeit.

Answer 2

Ich schlage vor, die folgende Lösung:

#include <stdio.h> 
#include <memory> 

int main() { 
    const int nrows = 4, ncols = 5; 
    const int dx = 2, dy = 1; 
    int a[nrows ][ncols] = { {1, 2, 3, 4, 5}, 
     { 6, 7, 8, 9, 10 }, 
     { 11, 12, 13, 14, 15 }, 
     { 16, 17, 18, 19, 20 } 
    }; 
    int tmp[nrows][ncols]; 
    for (int i = 0; i < nrows; i++) 
     for (int j = 0; j < ncols; j++) 
      tmp[(i + dx) % nrows][(j + dy) % ncols] = a[i][j]; 
    memcpy(a, tmp, sizeof(tmp)); 
    for (int i = 0; i < nrows; i++) 
     for (int j = 0; j < ncols; j++) 
      printf(j < ncols - 1 ? "%3d " : "%3d\n", a[i][j]); 
} 

Demo.

Der alternative Ansatz mit Speicherkopieren ist spezifisch für c++. Dies ist möglich aufgrund einer Methode zum Speichern mehrdimensionaler Felder im Speicher in c++, die zusammenhängend ist. Auf die letzten Elemente einer Zeile folgen die ersten Elemente der nächsten Zeile.

#include <stdio.h> 
#include <memory> 

int main() { 
    const int nrows = 4, ncols = 5; 
    const int dx = 2, dy = 1; 
    int a[nrows][ncols] = { {1, 2, 3, 4, 5}, 
     { 6, 7, 8, 9, 10 }, 
     { 11, 12, 13, 14, 15 }, 
     { 16, 17, 18, 19, 20 } 
    }; 
    int tmp[nrows][ncols]; 
    memcpy(tmp + dx, a, (nrows - dx) * ncols * sizeof(int)); 
    memcpy(tmp, a + (nrows - dx), dx * ncols * sizeof(int)); 
    memcpy(a, tmp, sizeof(tmp)); 
    for (int i = 0; i < nrows; i++) { 
     memcpy(tmp[i] + dy, a[i], (ncols - dy) * sizeof(int)); 
     memcpy(tmp[i], a[i] + ncols - dy, dy * sizeof(int)); 
    } 

    memcpy(a, tmp, sizeof(tmp)); 
    for (int i = 0; i < nrows; i++) 
     for (int j = 0; j < ncols; j++) 
      printf(j < ncols - 1 ? "%3d " : "%3d\n", a[i][j]); 
} 

Demo.

Answer 3

Angenommen, Sie haben eine Funktion niedrigerer Ebene, die effizient Matrix-Sublocks kopiert (die sich mit Low-Level-Speicheranordnung, Reihen-Hauptspalte-Major-Reihenfolge usw. befasst), kann die Operation konzeptionell in 4 Unterblockkopien zerlegt werden. Matlab-Array-Notationen und 1-basierte Array-Indizierung, ist, dass so etwas wie:

tmp(1:nr , 1:nc) = a(end-nr+1:end , end-nc+1:end); 
tmp(1:nr , nc+1:end) = a(end-nr+1:end , 1:end-nc); 
tmp(nr+1:end , 1:nc) = a(1:end-nr , end-nc+1:end); 
tmp(nr+1:end , nc+1:end) = a(1:end-nr , 1:end-nc); 

Man beachte, dass die Annahme der Vermietung Low-Level-Funktionen tut Job des niedrigen Niveaus ist sehr häufig (wie BLAS und LAPACK zum Beispiel).