This small package contains:
-
cavity!
andcavity
: Functions to compute theN
all-but-one operations betweenN
elements in timeO(N)
. The operation is arbitrary and needs only to be associative. This is equivalent to computing[reduce(op, (src[j] for j in eachindex(src) if i != j); init) for i in eachindex(src)]
which however would needN*(N-1)
evaluations ofop
. Ifop
is commutative with exact inverseinvop
, you could obtain the same result ofcavity(src, op, init)
, also in timeO(N)
, withinvop.(reduce(op, src; init), src)
. -
Accumulator
: Ana = Accumulator(v::Vector)
works as a replacement forv
with extra tracking computations.- Construction of
a
requires timeO(N)
whereN == length(v)
. sum(a)
,cumsum(a)
,cavity(a)
all require timeO(1)
.- See also:
CumSum
andCavity
.
- Construction of
-
c::CumSum(a::Accumulator)
: keeps a live-updatedcumsum
ofa
.- Create it with
c = cumsum(a::Accumulator)
- Retrieval
c[i]
takes timeO(log N)
. collect(c)
takes timeO(N)
searchsortedfirst(r, c)
takes timeO(log N)
- Create it with
-
c::Cavity(a::Accumulator)
: keeps a live-updatedcavity
ofa
.- Create it with
c = cavity(a::Accumulator)
. - Retrieval
c[i]
takes timeO(log N)
. collect(c)
takes timeO(N)
(but is slower thancavity(v::Vector)
).
- Create it with
-
Q::ExponentialQueueDict{K}()
:Dict
-like interface to a collection of events with associated independent probability rates, intended for sampling on a Gillespie-like scheme.- Events are of type
K
. - Rates can be queried by
getindex
(i.e.r = Q[k]
) and updated viasetindex!
(i.e.Q[k] = r
). both in timeO(log N)
whereN
is the number of stored events. - Next event type and time can extracted from the queue by
k,t = pop!(Q)
ork,t=peek(Q)
. Onpop!
, eventk
is then removed from the collection.pop!
takes timeO(log N)
,peek
isO(1)
. - If event time is unneeded, next event alone can be extracted with
k = peekevent(Q)
.
- Events are of type
-
Q::ExponentialQueue(N::Integer)
: LikeExponentialQueue{Int}
but events are stored on a vector instead of aDict
, so it is slightly more efficient. Event indices are in1:N
.