Insert item into a sorted list with Julia (with and without duplicates)

Question

Main Question: What is the fastest way to insert an item into a list that is already sorted using Julia?

Currently, I do this:

v = [1, 2, 3, 5] #example list
x = 4 #value to insert
index = searchsortedfirst(v, x) #find index at which to insert x
insert!(v, index, x) #insert x at index

Bonus Question: What if I want to simultaneously ensure no duplicates?

Gametocyte

Answer 1

You can use searchsorted to get the range of indices where the value occurs instead of just the first one and then use splice! to replace the values in that range with a new set of values:

insert_and_dedup!(v::Vector, x) = (splice!(v, searchsorted(v,x), [x]); v)

That's a nice little one-liner that does what you want.

julia> v = [1, 2, 3, 3, 5];

julia> insert_and_dedup!(v, 4)
6-element Array{Int64,1}:
 1
 2
 3
 3
 4
 5

julia> insert_and_dedup!(v, 3)
5-element Array{Int64,1}:
 1
 2
 3
 4
 5

This made me think that splice! should handle the case where the replacement is a single value rather than an array, so I may add that feature.

Marinetti

I've changed splice! to allow the replacement argument to be anything enumerable, which includes scalar values: github.com/JuliaLang/julia/commit/…. You can now define insert_and_dedup!(v::Vector, x) = (splice!(v, searchsorted(v,x), x); v) instead. – Marinetti

Thanks, and thanks also for all your work on julia. I'm loving the language. – Gametocyte

i tried this in julia 1.6.1 and it doesn't dedup anymore, but inserts the value in the correct place – Machutte

Answer 2

For sorted arrays of structs a modified version of StefanKarpinski solution would look like the example below:

struct TimeEvent
    date::Dates.DateTime
    type::String
end
    
v = [
    TimeEvent(DateTime("2019-03-01"),"data_release") 
    TimeEvent(DateTime("2019-02-01"),"data_release") 
    TimeEvent(DateTime("2019-05-01"),"data_release") 
 ]

new_event=TimeEvent(DateTime("2019-04-01"),"data_release") 

# Sort Events
sort!(v, by = v -> v.date, rev=true) 

# Define Function
sortedStructInsert!(v::Vector, x) = (splice!(v, 
    searchsorted(v,x,by= v->v.date, rev=true), [x]); v)

# Call function
sortedStructInsert!(v, new_event)

4-element Vector{TimeEvent}:
 TimeEvent(DateTime("2019-05-01T00:00:00"), "data_release")
 TimeEvent(DateTime("2019-04-01T00:00:00"), "data_release")
 TimeEvent(DateTime("2019-03-01T00:00:00"), "data_release")
 TimeEvent(DateTime("2019-02-01T00:00:00"), "data_release")

The example below allows you to specify which field of the struct is the one that sorts, for a more generic implementation.

sortedStructInsert!(v::Vector, x,symbol) = (splice!(v,
    searchsorted(v,x,by= v->getproperty(v,symbol), rev=true), [x]); v)
sortedStructInsert!(v, new_event, :date)

Skat