CODEWITHSUNDEEP
calgorithmcontainers
Dan Thomas
Dan Thomas

Reputation: 29

Circular buffer with fast lookup/insert/remove

I have a problem that I didn't find a solution that could be efficient enough. I need to speed up a circular buffer with a fixed size of 1.000.000 elements. It is currently implemented using a singly linked list.

For the moment, I have changed the implementation to use an array instead of the linked list. I use a write and read pointer to avoid shifting every index of my array. I need to do A LOT of lookup in my fifo, and I would need to delete items from indexes (well, I know it breaks the fifo rule).

First I was thinking of a sorted index table that matches the fifo array. It would be a O(log n) complexity for the lookup, but every time I'll need to update my fifo, I'll also need to update my index table. This is the part I didn't manage to do it efficiently (with a small complexity).

Any hints about an implementation that keeps track of the FIFO's order, and gives good performances in insert/delete/search operations ?

Thanks.

Upvotes: 2

Views: 1531

Answers (1)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

One approach would be to use:

  1. An array with n elements to store the items
  2. A Fenwick tree with n elements to store the occupancy.

We use the Fenwick Tree to write a 1 whenever an element is present, or 0 if the element is not present.

Once you have this structure, you can find the k^th present element and perform deletions in O(logn) time. (The actual implementation details may be a bit fiddly due to the FIFO wraparound - it may help to keep track of the total occupancy in the array and the occupancy from the pointer to the first element until the end of the array.)

Note that this structure will allow you to delete items anywhere, but only to insert items at the end of the FIFO - it is not clear whether this matches your requirements?

Upvotes: 1

Related Questions