使用Julia将项目插入到排序列表中(包含和不包含重复项)

Question

主要问题:将项目插入已使用Julia排序的列表的最快方法是什么？

目前,我这样做:

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

奖金问题:如果我想同时确保没有重复怎么办？

Answer 1

您可以使用searchsorted获取值出现的索引范围而不仅仅是第一个索引的范围,然后使用splice!一组新值替换该范围中的值:

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

这是一个很好的小单线,可以做你想要的.

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

这让我觉得splice!应该处理替换是单个值而不是数组的情况,所以我可以添加该功能.