AssociativeWindowAggregation.FixedWindowAssociativeOp
— TypeFixedWindowAssociativeOp{T,Op}
State necessary for accumulation over a rolling window of fixed size.
Fields
window_state::WindowedAssociativeOp{T,Op}
: The underlying general-window state.remaining_window::Int
: How much of the window remains to be filled. Initially this will be set to the window size, and will then reduce for every value added until it reaches zero.
AssociativeWindowAggregation.TimeWindowAssociativeOp
— TypeTimeWindowAssociativeOp{Value, Time, TimeDiff}
State necessary for accumulation over a rolling window of fixed size, in terms of time.
When presented with a new time t', we guarantee that all times t remaining in the window satisfy:
t > t' - w
That is, at time t' this window represents the open-closed time interval (t' - w, t']
Fields
window_state::WindowedAssociativeOp{Value}
: The underlying general-window state.window::TimeDiff
: The window, as a difference between two times.times::Deque{Time}
: The same length as the values stored inwindow_state
, and representing the times of those observations.window_full::Bool
: For internal use - will be set to true once a point has dropped out of the window.
AssociativeWindowAggregation.WindowedAssociativeOp
— TypeWindowedAssociativeOp{T,Op}
State associated with a windowed aggregation of a binary associative operator, in a numerically accurate fashion.
Wherever summation is discussed, we can consider any alternative binary, associative, operator. For example: +, *, max, min, &&, union
NB. It is interesting to observe that commutativity is not required by this algorithm, which is one of the reasons that it enjoys stable numerical performance.
Conceptually the window is maintained in two buffers:
[---- A ---)[----- B ------)
< > <-- current window finishes at the end of B, and
starts somewhere in A.
A
is stored as a sequence of cumulative sums, such that as the "<" advances we merely pick out the correct element:
x_i, x_i-1 + x_i, x_i-2 + x_i-1 + x_i
B
is stored as both:
- The sequence of values seen:
x_i+1, x_i+2, x_i+3, ...
- The total of that sequence:
x_i+1 + x_i+2 + x_i+3 + ...
When the "<" advances from A
to B
, we discard A
, and the subset of B
remaining after <
becomes the new A
. In becoming A
, we transform its representation into that of the cumulative sums. We create a new, empty, B
.
O(1)
amortized runtime complexity, and O(L)
space complexity, where L
is the typical window length.
Type parameters
T
: The type of the values of the array.Op
: Any binary, associative, function.V
: The abstract vector subtype used for internal state.
Fields
previous_cumsum::Vector{T}
: Corresponds to arrayA
above.ri_previous_cumsum::Int
: A reverse index intoprevious_cumsum
, once it contains values. It should be subtracted fromend
in order to obtain the appropriate index.values::Vector{T}
: Corresponds to arrayB
above.sum::T
: The sum of the elements in values.
AssociativeWindowAggregation.WindowedAssociativeOp
— MethodWindowedAssociativeOp{T,Op}
Create a new, empty, instance of WindowedAssociativeOp.
Type parameters
T
: The type of the values of the array.Op
: Any binary, associative, function.
AssociativeWindowAggregation.update_state!
— Methodupdate_state!(state::FixedWindowAssociativeOp, value)
Add the specified value
to the state
. Drop a value from the window iff the window is full.
Returns
::FixedWindowAssociativeOp
: The instancestate
that was passed in.
AssociativeWindowAggregation.update_state!
— Methodupdate_state!(
state::TimeWindowAssociativeOp{Value,Time,TimeDiff},
time,
value
)::TimeWindowAssociativeOp{Value,Time,TimeDiff} where {Value,Time,TimeDiff}
Add the specified value
to the state with associated time
, and drop any values that are no longer in the time window.
Arguments
state::TimeWindowAssociativeOp{Value,Time,TimeDiff}
:time
: The time to whichvalue
corresponds.value
: The value to add to the window.
Returns
::TimeWindowAssociativeOp{Value,Time,TimeDiff}
:state
, which has been mutated.
AssociativeWindowAggregation.update_state!
— Methodupdate_state!(
state::WindowedAssociativeOp{T,Op},
value,
num_dropped_from_window::Integer
)::WindowedAssociativeOp{T,Op} where {T,Op}
Add the specified value to the state, drop some number of elements from the start of the window, and return state
(which will have been mutated).
Arguments
state::WindowedAssociativeOp{T,Op}
: The state to update (will be mutated).value
: The value to add to the end of the window - must be convertible to aT
.num_dropped_from_window::Integer
: The number of elements to remove from the front of the window.
Returns
::WindowedAssociativeOp{T,Op}
: The instancestate
that was passed in.
AssociativeWindowAggregation.window_full
— Methodwindow_full(state::FixedWindowAssociativeOp)::Bool
Returns true iff the given state
has a full window.
AssociativeWindowAggregation.window_full
— Methodwindow_full(state::TimeWindowAssociativeOp)::Bool
Returns true iff the given state
has had at least one value drop out of the window, indicating that the window is now full.
AssociativeWindowAggregation.window_size
— Methodfunction window_size(state::WindowedAssociativeOp)::Int
Get the current size of the window in state
.
Arguments:
state::WindowedAssociativeOp
: The state to query.
Returns:
Int
: The current size of the window.
AssociativeWindowAggregation.window_value
— Methodwindow_value(state::WindowedAssociativeOp{T,Op})::T where T
Get the value currently represented by the state.
Arguments:
state::WindowedAssociativeOp{T,Op}
: The state to query.
Returns:
T
: The result of aggregating over the values in the window.