0

I have a never ending stream of data coming in to a program I’m writing. I would like to have a fixed size buffer array which only stores the T most recent observations of that stream. However, to me its not obvious how to implement that in an efficient way.

What I have done so far is to first allocate the buffer of length T and place incoming observations in consecutive order from the top as they arrive: data_0->index 0, data_1->index 1…data_T->index T.

Which works fine until the buffer is full. But when observation data_T+1 arrives, index 0 needs to be removed from the buffer and all T-1 rows needs to be moved up one step in the array/matrix in order to place the newest data point at index T.

That seems to be a very inefficient approach when the buffer is large and hundreds of thousands of elements need to be pushed one row up all the time. How is this normally solved?

Petahanks
  • 182
  • 11

1 Answers1

0

This algorithm called FIFO queue java fifo queue Look at this API it has several code examples.

Eliad Cohen
  • 378
  • 2
  • 10
  • I looked at the link but I don’t know java so I didn’t understand much of that. I mainly code in Python, C and Matlab. But regardless of language, I was seeking a conceptual solution to the problem which easily can be implemented in a similar way in any language. – Petahanks Oct 08 '17 at 09:18
  • Ok so use [ring buffer](https://stackoverflow.com/questions/215557/how-do-i-implement-a-circular-list-ring-buffer-in-c) – Eliad Cohen Oct 08 '17 at 10:18
  • Hmm, so essentially start overwriting from the top once the buffer is filled to the bottom? That was my first initial idea as well but I dismissed it because I suspected that it would be too cumbersome to keep track of the indexing if the buffer is not sorted in the way the data arrives. Is there an approach which preserves the consecutive order of the data? So that the buffer always goes from oldest->newest or newest->oldest? – Petahanks Oct 09 '17 at 18:46
  • You can use linked list: 1. Allocate an array in a size that you want. 2. Every element in this Array should contain 3 parameters: 2.1 next,prev and value 3. Create an object that point to the first and the last objects. 3.1. Init them to NULL 4. implement add() and remove() 4.1 add - change the last(and the first when it NULL) 4.2 remove - change the first. You can continue with this algorithm by your self. – Eliad Cohen Oct 09 '17 at 19:39