CircularBuffer//insert value

General Usage
1

I have CircularBuffer (sorted) array, and want to insert the value into it. A simple example is

cb = CircularBuffer{Float64}(5)
#when full capacity
append!(cb, [1.0, 2.0, 3.0, 4.0, 5.0])
ii = searchsortedlast(cb, 3.5)
copyto!(cb, [cb[2:ii]; 3.5])
#when not full capacity
empty!(cb)
append!(cb, [2.0, 3.0, 4.0, 5.0])
ii = searchsortedlast(cb, 3.5)
#want to have cb = [2.0, 3.0, 3.5, 4.0, 5.0]

With full capacity, I use copyto! to get the result (although not sure if the most efficient way), but I can’t figure it out when the array is not full capacity. Also, this is inside of several for loops, so the speed is essential. I would appreciate if you give some help.

2

From the details here this seems like a heap would be a better choice. That is, if you just want to maintain the n-largest elements from some process and get them sorted at the end.

using DataStructures
h = BinaryHeap{Float64, DataStructures.FasterForward}(1.0:5.0) # improved performance for floats

function push_with_cap!(heap, item, cap)
  push!(heap, item)
  while length(heap) > cap
    pop!(heap)
  end
end

push_with_cap!(h, 3.5, 5)

...

# get elements in sorted order
extract_all!(h)
3

If you actually need to maintain a sorted list between insertions I’m not sure that a CircularBuffer is going to help and you probably won’t do much better than just maintaining a sorted vector

function push_with_cap!(v, item, cap)
  ii = searchsortedlast(v, item; rev=true)
  insert!(v, ii+1, item)
  while length(v) > cap
    pop!(v)
  end
end

buf = Float64[]
sizehint!(buf, capacity+1)
append!(buf, 1.0:5.0)
sort!(buf; rev=true)

push_with_cap!(buf, 3.5, 5)

Since it is more efficient to add and remove from the end of a vector we maintain it in reverse order.

HTH

1 Like