Ich habe eine ganze Matrix, das wie ein Puffer wirken soll:C: clevere Möglichkeit, eine Matrix zu "verschieben"?
x = {{0, 0, 0, 0, 0}, {1, 1, 1, 1, 1}, {2, 2, 2, 2, 2}};
Nun, wenn ich eine neue Zeile {3, 3, 3, 3, 3}, die neue Matrix hinzufügen soll wie folgt aussehen:
x = {{1, 1, 1, 1, 1}, {2, 2, 2, 2, 2}, {3, 3, 3, 3, 3}};
Gibt es Eine clevere Art dies zu tun, ohne alle Elemente zu kopieren?
Wie wäre es mit Modulo-Betrieb?
Wenn Sie Zugriff auf die Elemente als matrix[x + SZ * y] Sie es ändern könnte:
matrix[x + SZ * ((y + FIRST_ROW) % SZ)].
Um diese Verschiebung zu implementieren, legen Sie einfach die neue Zeile {3, 3, 3 ..} mit der Zeile {0, 0, 0} und erhöhen den Zähler FIRST_ROW, um auf die neue Startzeile zu zeigen.
Schön, danke! Dieser Ort ist voll von kreativen Menschen. :-) –
+1 basierend auf der zusätzlichen Spezifikation in den Kommentaren zur ursprünglichen Frage, dies ist wahrscheinlich die Alternative, die die beste Leistung geben wird. –
Ich habe es jetzt implementiert und es funktioniert gut. Nochmals vielen Dank und danke Jungs für all die anderen Antworten! –
Verwenden Sie eine verkettete Liste.
struct node
{
int row[5];
struct node *next;
};
Anfügen eine Reihe ist so einfach wie die Liste zu Ende geht, dann die nächsten Zeiger NULL mit einem neuen Knoten ersetzt (deren nächsten Zeiger NULL).
Dies funktioniert für den Algorithmus, aber wird es nicht extrem langsame Ergebnisse geben, wenn Sie tatsächlich Dinge mit der Matrix tun? – alternative
Das hängt davon ab, was Sie damit machen. Wenn du deine Matrix nicht ständig erweiterst, bist du wahrscheinlich besser dran, wenn du das gelegentliche Memcpy aufnimmst. – nmichaels
Beachten Sie, dass in der Frage die neue Zeile nicht zur Matrix "hinzugefügt" wird, sondern die erste Zeile ersetzt. Wenn Sie also die Lösung mit verknüpften Listen auswählen, vergewissern Sie sich, dass Sie Ihr erstes Element in der Liste annullieren. – ysap
Können Sie x inkrementieren, so dass es auf die zweite Zeile zeigt, dann die erste Zeile freigeben? Offensichtlich müssten Sie eine Zeile auf einmal zuweisen und dies würde nicht garantieren, dass die Matrix zusammenhängend ist. Wenn Sie das benötigen, können Sie einen großen Speicherblock für Ihre Matrix reservieren und dann die unbenutzten Teile überlisten, wenn Sie das Ende erreicht haben.
Wenn Ihre Matrix als int ** definiert ist und Sie jede Zeile separat zuweisen, müssten Sie nur die Zeilenzeiger tauschen.
Das klingt gut. Ich muss wirklich lernen, mehr Zeiger-orientiert zu denken. :) –
Das einzige Problem ist, dass im Gegensatz zu der vorgeschlagenen Lösung für die verknüpfte Liste, Zeiger auf die maximale Anzahl von Zeilen, die Sie haben werden, vorab zugewiesen werden müssen. Ansonsten ist es ein effizienterer Weg als die verknüpfte Liste. ** EDIT ** Ich habe gerade festgestellt, dass Sie in Ihrer Frage nach dem Hinzufügen der neuen Zeile mit 3 Zeilen bleiben. Wenn das repräsentativ ist, dann ist die Antwort von @mikerobi in Ordnung. Sie müssen nur Ihre Zeiger verwalten, sobald die Zeilen vertauscht sind. – ysap
@ysap, die gelegentliche O (n) -Operation, um die Anzahl der Zeilen zu erhöhen, wird in der Regel effizienter sein als eine häufige O (n), um auf einen Wert zuzugreifen. – mikerobi
Wenn Sie ein Array von Zeigern zu Arrays verwenden (anstatt eines gewöhnlichen zweidimensionalen Arrays), können Sie nur die Zeiger in Zeilen kopieren, anstatt alle Elemente zu kopieren.
Und wenn Sie in Ordnung mit dem Array von Zeigern overdoocating sind, könnten Sie vielleicht einen neuen Zeiger auf das Ende hinzufügen und den Zeiger auf den "Start" des Arrays weiterleiten. Aber das wäre keine gute Idee, wenn Sie diese Art von Schicht möglicherweise mehrmals durchführen möchten. Und natürlich möchten Sie sicherstellen, dass Sie den Originalzeiger irgendwo haben, damit Sie Ihre Ressourcen richtig nutzen können.
Lazy zu Code-Beispiel schreiben - Sie können Modulo-Arithmetik verwenden, um die Zeilen zu adressieren. Wenn Sie eine neue Zeile drücken, erhöhen Sie einfach eine Start-Offset-Variable, addieren die Matrixhöhe und modulieren das Ergebnis nach Matrixhöhe. Auf diese Weise erhalten Sie eine zirkuläre Matrix, ohne dass Sie die gesamte Matrix kopieren und das Matrix-Array kompakt halten müssen.
Mehrere Antworten sind technisch korrekt, aber alle beinhalten unterschiedliche Kompromisse. Können Sie Ihre erwartete Verwendung etwas erweitern? Wie groß werden diese Matrizen sein? Wie oft rechnen Sie damit, dass Sie eine Zeile hinzufügen, verglichen mit der Häufigkeit, mit der Sie auf Daten aus den Matrizen zugreifen? Werden Sie auf einzelne Elemente der Matrix zugreifen, oder werden sie nur von Anfang bis Ende als ganze Entität gelesen? Möchten Sie Teile der Matrix von Zeit zu Zeit freigeben können? Wenn ja, nur vom Ende oder vom Anfang oder von einer willkürlichen Reihe? –
Die Matrix ist nicht groß (wie 100 Elemente insgesamt).Ich werde immer auf die ganze Matrix zugreifen, die "alte" Zeile kann weggehen (Fifo-Queue-Verhalten), Updates kommen sehr oft vor. –
In diesem Fall ist der von @ruslik vorgeschlagene Modulo-Ansatz wahrscheinlich die beste Wahl. Ordnen Sie einfach ein Array zu, das die maximale Größe verarbeiten kann, behalten Sie einen Zeiger auf den aktuellen Kopf bei und wickeln Sie das Ende des Arrays um, wenn kein Platz mehr ist. –