Beste Weg, um shift-array in C?
Ich habe ein array, hat eine Geschichte von Werten, und beim hinzufügen eines neuen Wertes, muss ich mit shift alle bisherigen Werte eine position nach Links, zu verlieren, der älteste Wert und machen Platz für die nächsten.
Ich denken kann, zwei Möglichkeiten, dies zu tun, durch die Verwendung von memmove:
memmove(&arr[0], &arr[1], sizeof(arr) - sizeof(*arr));
Oder durch das vertauschen der Zeiger:
for (i = 0; i != sizeof(arr) - 1; i++) {
*(arr + i) = *(arr + i + 1);
}
Gibt es einen performance-Unterschied zwischen den beiden Methoden, und wenn nicht, welches wäre ratsam?
- Haben Sie in Betracht gezogen, nicht mit einem array oder ist das nicht eine option?
- Ich brauche zu verfolgen, die letzten X-Werte, so kann ich nicht denken, mehr logische Weg, um Sie zu speichern, außer für ein array.
- Benutzen Sie eine Warteschlange (Sie können weiterhin verwenden Sie ein array, um es zu implementieren), und vermeiden Sie den Speicher kopieren. thelearningpoint.net/computer-science/...
- Warum nicht verwenden ein double-ended-Liste? So erhalten Sie in O(X) Komplexität, der Zugriff auf Ihren X-Elemente, aber das einfügen von Elementen wird durch viel schneller. Was am besten funktioniert, am Ende hängt Sie die Anwendung. Fügen Sie viel oder haben Sie Zugriff auf eine Menge?
- Oder verwenden Sie einen kreisförmigen Puffer (halten Sie die
int head
index und alle Zugriffe% arraySize
). - Vielen Dank.
- Seine für ein digitales filter. Jedesmal, wenn ich einen neuen Punkt hinzuzufügen, ich brauche zu berechnen, die Summe aller vorherigen Punkte, so dass die Menge der Zugriffe vs fügt gleich ist.
- Ihr willkommen.
- Die zweite von den Methoden sollte
i != sizeof(arr)/sizeof(*arr) - 1
als seine stoppen Zustand. Ich würde auch einfache Indizierung von Arrays in der Schleifearr[i] = arr[i + 1]
. Selbst mit diesen änderungen, ich würde immer noch lieber diememmove
Lösung, aber es gibt einige attraktive alternativen die Antworten.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Beide haben die gleiche Zeit Komplexität. Jede andere performance-Unterschied wäre aufgrund besonderer Umstände, wie z.B. die CPU, der compiler, wie memmove implementiert ist, und die Größe des Arrays, so dass Sie haben, um tatsächlich zu Messen, die Leistung jeder Art und Weise und sehen, was am besten ist.
Gibt es eine schnellere Möglichkeit:
Einen Ringpuffer wo einfügen, entfernen und Lesen, sind alle O(1).
Ich glaube nicht, dass ein array die beste Weg, dies zu tun , versuchen Sie es mit einer verketteten Liste, und Sie werden nicht dieses problem haben.
Können Sie die FIFO-Warteschlange implementiert als verkettete Liste oder als array. Von deiner Beschreibung her, ist es die einfachste Lösung.