ソート済みのバージョン

Question

私は時の配列を持っていますevent_timesと私はt in event_timesをチェックしたいと思います。しかし、私はevent_timesがソートされていることを知っています。検索をより速くするためにそれを利用する方法はありますか？

Answer 1

慣用ユリウス道はの精緻次のようになります。その後、

struct SortedVector{T,V<:AbstractVector} <: AbstractVector{T} 
    v::V 
    SortedVector{T,V}(v::AbstractVector{T}) where {T, V} = new(v) 
    # check sorted in inner constructor?? 
end 
SortedVector(v::AbstractVector{T}) where T = SortedVector{T,typeof(v)}(v) 

@inline Base.size(sv::SortedVector) = size(sv.v) 
@inline Base.getindex(sv::SortedVector,i) = sv.v[i] 
@inline Base.in(e::T,sv::SortedVector{T}) where T = !isempty(searchsorted(sv.v,e)) 

そして：私が正しくリコール

julia> v = SortedVector(sort(rand(1:10,10))) 
10-element SortedVector{Int64,Array{Int64,1}}: 
    1 
    4 
    5 
    5 
    6 
    6 
    6 
    7 
    7 
10 

julia> 3 in v 
false 

julia> 1 in v 
true 

デビッド・サンダースは、この名前の実装を持っていました。おそらくhttps://github.com/JuliaIntervals/IntervalOptimisation.jl/blob/889bf43e8a514e696869baaa6af1300ace87b90b/src/SortedVectors.jlを見ると、再利用が促進されます。

Answer 2

@ ColinTBowersのヒントに続いて、searchsortedは、tがevent_timesにない場合、空の範囲を返します。したがって、!isempty(searchsorted(event_times,t))は答えを得るための高速な方法です。