Consider a sequence of numbers and imagine you need to compute the maximum of all adjacent sub-sequences of length . How would you do that efficiently?
Let’s write for the original sequence. We want to compute with . Such k-ary needs to be computed in terms its binary version . To simplify notations, we will write it .
The naive approach
A naive way to compute is by “folding” the binary operator. For , we could write:
Each requires computing binary max, and there is no sharing between sub-expressions between two and . So, to compute all , we need binary operations, i.e. roughly for large and . We could “fold in the other direction”:
Of course, we get the same number of operations. Can we do better?
The problem with the naive approach above is that we cannot reuse any intermediate computation. Even though is “part” of both and , the way the computations are organised does not allow us to benefit from such sharing.
A better algorithm
Let’s move brackets around, relying on the associativity of the operator. We can rewrite:
When computing , one can reuse the internal bracket we had already computed as part of . So computing involves just one more binary . If we keep track of such sharing, we can see that computing involves only 12 operations, which is twice better than the 24 for the native algorithm (with ). If we want to go further in the sequence above, one can just “shift” the indices:
Note that we do not reuse any previously computed bracket for that new block . Let’s count the number of operations in general. For the first block , we need:
-
The left and right folding and , remembering their internal brackets. This requires binary operations.
-
Then, each can be computed with one more binary operation (combining two of the results obtained above, or one of them and some ), hence more operations.
To compute the first , we thus need operations. So, when the total number of to compute (i.e. ) is a multiple of , we need operations, i.e. roughly for large and , which is of course much better than for the naive algorithm. The algorithm has some nice properties:
-
We can produce the series sequentially, remembering only at most values at each step.
-
We can also parallelize the calculation across independent blocks (of length ), since no intermediate result is shared between two such blocks.
-
We only used the associativity property of our “bracket” binary operator. The same algorithm would work for any associative operator. For instance, we can use it to compute the largest number in each window (working on a domain of multi-sets of at most elements).
-
The algorithm produces a static computation graph, which can be mapped directly to low level instructions with no comparison, no branching, no pointer, just applications the binary operator to input or temporary variables assigned to outputs or other temporary variables (with at most live temporary variables at any instruction).
Implementation
This post is part of our “OCaml Blog”, so let’s write some (completely unidiomatic) OCaml :-)
Trying to be careful with index manipulations, the algorithm can be implemented as below:
val sliding_associative: 'a array -> ('a -> 'a -> 'a) -> int -> 'a array
let sliding_associative a f k =
if k <= 0 then invalid_arg "sliding_associative";
let n = Array.length a in
if n < k then [||]
else if k = 1 then a
else if k = 2 then Array.init (n - 1) (fun i -> f a.(i) a.(i + 1))
else
let r = Array.make (n - k + 1) a.(0) in
let b = Array.make (k - 2) a.(0) in
begin try
for row = 0 to (n - k) / (k + 1) do
let ofs = row * (k + 1) in
let ofs_k = ofs + k in
b.(k - 3) <- f a.(ofs_k - 2) a.(ofs_k - 1);
for i = k - 4 downto 0 do
b.(i) <- f a.(ofs + i + 1) b.(i + 1)
done;
r.(ofs) <- f a.(ofs) b.(0);
if ofs_k < n then begin
let acc = ref a.(ofs + k) in
for i = 1 to k - 2 do
r.(ofs + i) <- f b.(i - 1) !acc;
if ofs_k + i = n then raise_notrace Exit;
acc := f !acc a.(ofs_k + i)
done;
r.(ofs_k - 1) <- f a.(ofs_k - 1) !acc;
if ofs_k + k - 1 < n then r.(ofs_k) <- f !acc a.(ofs_k + k - 1);
end
done
with Exit -> ()
end;
r
Optimality?
Is this algorithm optimal, in the sense that it requires the smallest possible number of applications of the binary operator? I don’t know!
I’ve tried to find empirical optimal solutions, applying some restrictions to which solutions are considered.
Namely, let’s consider computation graphs where each intermediate result represents the of a consecutive segment (). This excludes computing e.g. . If we look at all intermediate results, i.e. all such segments involved in the computation, a graph can be represented by a set of pairs with , with the property that for any there exists some such that: (i) either or , and (ii) either or . This property means that any intermediate result is obtained by splitting the segment into two sub-segments (possibly reduced to a single ), whose has also been computed. This excludes relying on the idempotence of to compute e.g. as .
These restrictions correspond to the fact that the only property of the binary operator that we use is its associativity.
Moreover, we require that all pairs for are in , i.e. the graph actually computes the required outputs.
It’s rather straightforward to implement a brute-force search of such set with minimal size. For and , I’ve confirmed that we get the same result as the algorithm presented above for all ; and also for for all ; for for all .
I haven’t tried to prove that the algorithm is indeed optimal, at least with the restrictions above. I’d be interested to hear if somebody gives it a try, or find better solutions lifting the restrictions. Also, I’d be surprised if the algorithm wasn’t already known in some form or another. Let me know if you had already heard about it!
Application
The curious reader might be interested to know how we got interested with this problem at LexiFi. As you might know, our software allows modelling and pricing ad hoc financial products. A few weeks ago, we have been submitted a product with a rather complex definition, involving computing on a daily basis the of some quoted underlying over the last 60 market observations (and then doing some more complex crazy stuff over this series). Pricing such product involves “running” this payoff formula many thousands of times over different simulated market trajectories (a.k.a. a Monte Carlo simulation), and it is thus of paramount importance that the code to evaluate the payoff be as fast as possible. As a matter of fact, we compile (just-in-time) our internal payoff description into some native code which we execute many times. For a product with such sliding-max feature, we could observe a 10 fold reduction in RAM usage for the internal product representation, and a similar gain in terms of pricing code generation and execution time
It is rather common that changing how a given product is represented can impact significantly the performance of our software, but it is very infrequent that we need to resort to such a non-trivial technique (albeit quite simple once you know about it!).
Another algorithm
Googling for “sliding window maximum algorithm”, one can find another efficient and very different algorithm, which consists in using a “deque” data structure to keep track, while “sliding the k-window” over the initial sequence, of at most elements from the current window in decreasing order. When the window moves to the next position, the new element is inserted in the data structure, removing all elements which are smaller than it from the deque (they are found at the beginning) and also the element which just moved out of the window. See e.g. this website or this one. This algorithm uses a similar number of operations, but a more advanced data structure, which cannot be expressed as a simple static computation graph (the counting of operations relies on an amortized analysis: each element is inserted and removed at most once from the deque, but when a new element is added, the number of elements dropped from the deque can be as large as ). Moreover, it does not seem that this algorithm extends to arbitrary associative operators.