2013-09-02 11 views
7

Ich habe ein Array, das eine Geschichte von Werten enthält, und wenn ich einen neuen Wert hinzufüge, muss ich alle vorherigen Werte um eine Position nach links verschieben, um den ältesten Wert zu verlieren und Platz für den nächsten zu schaffen.Die beste Methode, um ein Array in C zu verschieben?

Ich denke an zwei Möglichkeiten, dies zu tun, durch memmove mit:

memmove(&arr[0], &arr[1], sizeof(arr) - sizeof(*arr)); 

Oder durch die Zeiger Swapping:

for (i = 0; i != sizeof(arr) - 1; i++) { 
    *(arr + i) = *(arr + i + 1); 
} 

ein Performance-Unterschied zwischen den beiden Methoden ist es, und wenn nicht, welcher wäre beraten?

+1

Haben Sie darüber nachgedacht, kein Array zu verwenden oder ist das keine Option? – nic

+1

@nic Ich muss die letzten X-Werte verfolgen, daher kann ich mir keine logischere Möglichkeit vorstellen, sie außer einem Array zu speichern. – Muis

+0

Verwenden Sie eine Warteschlange (Sie können immer noch ein Array verwenden, um es zu implementieren) und vermeiden Sie das Kopieren des Speichers. http://www.thelearningpoint.net/computer-science/data-structures-queues--with-c-program-source-code –

Antwort

3

Sie haben beide die gleiche Zeit Komplexität. Jeder andere Unterschied in der Leistung hängt von bestimmten Umständen ab, z. B. von der CPU, dem Compiler, der Implementierung von mem move und der Größe des Arrays. Sie müssen also die Leistung in jeder Hinsicht messen und herausfinden, was am besten ist.

+1

Das Lesen der Assembly-Ausgabe könnte ebenfalls aufschlussreich sein. – chrylis

1

Ich glaube nicht, dass ein Array der beste Weg ist, dies zu tun, versuchen Sie es mit einer verknüpften Liste, und Sie haben dieses Problem nicht.

7

Es gibt eine schnellere Option:

A circular buffer wo einfügen, entfernen und zu lesen sind alle O (1).

0

Sie können die FIFO Queue als eine verkettete Liste oder als ein Array implementiert verwenden. Nach Ihrer Beschreibung ist es die einfachste Lösung.

Verwandte Themen