9

I have an array that holds a history of values, and when adding a new value, I need to shift all previous values one position to the left, to loose the oldest value and make room for the next.

I can think of two ways of doing this, by using memmove:

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

Or by swapping the pointers:

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

Is there a performance difference between the two methods, and if not, which one would be advised?

Maestro
  • 9,046
  • 15
  • 83
  • 116
  • 1
    Have you considered not using an array for this or is that not an option? – nic Sep 02 '13 at 14:08
  • 1
    @nic I need to keep track of the last X values, so I cant think of any more logical way to store them except for an array. – Maestro Sep 02 '13 at 14:12
  • Use a queue (you can still use an array to implement it), and avoid the memory copying. http://www.thelearningpoint.net/computer-science/data-structures-queues--with-c-program-source-code – Jacob G Sep 02 '13 at 14:14
  • @Joshua Why not use a double-ended list? That way you get O(X) complexity accessing your X elements but inserting elements will by way faster. What works best in the end depends on you application. Do you insert a lot or do you access a lot? – nic Sep 02 '13 at 14:14
  • Or use a circular buffer (keep an `int head` index and do all accesses `% arraySize`). – chrylis -cautiouslyoptimistic- Sep 02 '13 at 14:15
  • @nic Its for a digital filter. Everytime I add a new point, I need to calculate the sum of all previous points, so the amount of accesses vs inserts is equal. – Maestro Sep 02 '13 at 14:22
  • The second of your methods should have `i != sizeof(arr)/sizeof(*arr) - 1` as its stopping condition. I'd also use simple array indexing in the loop, `arr[i] = arr[i + 1]`. Even with those changes, I'd still prefer the `memmove` solution, though there are some attractive alternatives in the posted answers. – Joshua Green Sep 02 '13 at 15:15

4 Answers4

8

There is a faster option:

A circular buffer where insert, remove and read are all O(1).

Klas Lindbäck
  • 33,105
  • 5
  • 57
  • 82
3

They both have the same time complexity. Any other difference in performance would be due to specific circumstances, such as the CPU, the compiler, how memmove is implemented, and the size of the array, so you have to actually measure the performance each way and see what is best.

Vaughn Cato
  • 63,448
  • 5
  • 82
  • 132
1

I don't think that an array is the best way to do this , try using a linked list and you wont have this problem.

Farouq Jouti
  • 1,657
  • 9
  • 15
0

You can use the FIFO Queue implemented as a linked list or as an array. From your description, it's the most straightforward solution.

pkacprzak
  • 5,537
  • 1
  • 17
  • 37