General window

A state to represent a window of aribtrarily variable capacity.

Every time a new value is pushed onto the end of the window, we must specify how many values are removed from the front of the window.

AssociativeWindowAggregation.WindowedAssociativeOp — Type
WindowedAssociativeOp{T}

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.

Fields

  • op::Function: Any binary, associative, function.
  • previous_cumsum::Array{T, 1}: Corresponds to array A above.
  • ri_previous_cumsum::Int: A reverse index into previous_cumsum, once it contains values. It should be subtracted from end in order to obtain the appropriate index.
  • values::Array{T, 1}: Corresponds to array B above.
  • sum::Union{Nothing, T}: The sum of the elements in values.
AssociativeWindowAggregation.update_state! — Method
update_state!(
    state::WindowedAssociativeOp{T},
    value,
    num_dropped_from_window::Integer
)::WindowedAssociativeOp{T} where T

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}: The state to update (will be mutated).
  • value: The value to add to the end of the window - must be convertible to a T.
  • num_dropped_from_window::Integer: The number of elements to remove from the front of the window.

Returns

  • ::WindowedAssociativeOp{T}: The instance state that was passed in.
AssociativeWindowAggregation.window_size — Method
function window_size(state::WindowedAssociativeOp{T})::Int where T

Get the current size of the window in state.

Arguments:

  • state::WindowedAssociativeOp{T}: The state to query.

Returns:

  • Int: The current size of the window.
AssociativeWindowAggregation.window_value — Method
window_value(state::WindowedAssociativeOp{T})::T where T

Get the value currently represented by the state.

Arguments:

  • state::WindowedAssociativeOp{T}: The state to query.

Returns:

  • T: The result of aggregating over the values in the window.