Sliding Window

Sliding windows provide a fixed width view into a list that moves along the length of the list. If used properly it can reduce the time complexity of a problem.

Implementing a sliding window

const std = @import("std");

pub fn main() void {
  const data = [_]i32{ 1, 2, 3, 4, 5, 6, 7, 8 };
  const window_size = 4;

  // +1 ensures the loop includes the last valid window.
  for (0..(data.len - window_size + 1)) |i| {
    // window represents a slice of size `window_size` of `data`.
    const window = data[i..(i + window_size)];
    std.debug.print("Window {d}: {any}\n", .{i, window});
  }
}

In the example above we implement a sliding window of size 4 elements on an array of 8 elements. Let’s step through each iteration until we view the entire length of the data array.

To do this we use the formula data.len - window_size + 1. Our for loop starts with 0 and iterates a number of times provided by our formula which tells us how many iterations we’ll need, given a window size, to view the entire length of the array. For the code above this is 0 through 4 (5 iterations).

Let’s step through each iteration to see what’s going on.

Iteration 1 (i=0):
Window => data[0..4]
Output => Window 0: { 1, 2, 3, 4 }

Iteration 2 (i=1):
Window => data[1..5]
Output => Window 1: { 2, 3, 4, 5 }

Iteration 3 (i=2):
Window => data[2..6]
Output => Window 2: { 3, 4, 5, 6 }

Iteration 4 (i=3):
Window => data[3..7]
Output => Window 3: { 4, 5, 6, 7 }

Iteration 5 (i=4):
Window => data[4..8]
Output => Window 4: { 5, 6, 7, 8 }

When are sliding windows useful?

When processing a large list of items or a long stream you can theoretically reduce the time to solve by eliminating unnecessary computations. Each time the window slides you can perform operations on a subset and is typically linear in time complexity.

Some use cases are:

• String matching
• Stream processing
• Time-series data
• Image processing
• Sums and occurrences