Insert value into sorted array with fixed size

General Usage
,
1

I want to insert a value into a sorted array with fixed size, removing the last (greatest) value of the array. A naive solution is this function that combines insert! (or pushfirst!) and pop!:

function insertandropgreatest_naive!(collection, newvalue)
    if newvalue >= last(collection)
        return collection
    end
    i = searchsortedlast(collection, newvalue)
    if i==0
        pushfirst!(collection, newvalue)
    else
        insert!(collection, i, newvalue)
    end
    pop!(collection)
    return collection
end

I thought that it would be better to make something that does not redimension the array, like this:

function insertandropgreatest_fixedsize!(collection, newvalue)
    # do nothing if newvalue is greater than greatest in collection
    if newvalue >= last(collection)
        return collection
    end
    # search, and replace...
    for i = length(collection):-1:2
        collection[i] = collection[i-1]
        if newvalue >= collection[i]
            collection[i] = newvalue
            return collection
        end
    end
    # replace in first position if newvalue is smaller than smallest in collection
    collection[1] = newvalue
    return collection
end

An advantage of this is that it works with MArrays (from StaticArrays.jl), but for standard arrays I can’t see a big gain in performance. Is the “naive” version sufficiently optimized for this problem, or does anyone have some suggestion to improve it?

NB: I’m starting the search from the greatest to the smallest, because I expect newvalue to be greater than all elements of collection more frequently.

2

I think your idea to avoid resizing the array is sensible (although probably not a huge win), and being able to work with MArrays is a good idea too. However, your second option loses some benefit by doing a linear search over the entire collection, when that might not actually be necessary. It also has a branch inside the inner loop, which may interfere with your CPUs pipelining and branch prediction.

Perhaps you could instead do:

  1. Use searchsortedlast to find the right place to put the value
  2. Use copyto! (or a for loop) to shift the data after that index by one to make room.
  3. Put the new value into the space you’ve just made

On the other hand, if you’re dealing with lots of sorted data, you might be better off using a different data structure entirely, like the ones from Sorted Containers · DataStructures.jl

Alternatively, if your collections are small, there may be no advantage to using searchsortedlast, in which case your second option may actually be optimal.

Edit: But you can probably save some time using the usual @inbounds stuff from Performance Tips · The Julia Language

1 Like