使用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

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

- Colin T Bowers

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! 应该处理替换为单个值而不是数组的情况，因此我可能会添加该功能。

- StefanKarpinski

---

谢谢，这非常整洁。 - Colin T Bowers

我已经修改了splice！函数，使其允许替换参数为任何可枚举的值，包括标量值：https://github.com/JuliaLang/julia/commit/e048f2bf1b8da56b07738c0a4d142cd29e140e98。现在你可以定义`insert_and_dedup!(v::Vector, x) = (splice!(v, searchsorted(v,x), x); v)`来代替。 - StefanKarpinski

谢谢，也感谢您在Julia上的所有工作。我非常喜欢这门语言。 - Colin T Bowers

我在 Julia 1.6.1 中尝试过这个，它不再去重，而是将值插入到正确的位置。 - longemen3000

Answer 2

对于已排序的结构体数组，StefanKarpinski解决方案的修改版本如下所示：

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")

下面的示例允许您指定结构体中用于排序的字段，以实现更通用的功能。

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

- Bruno Castro