Summary How to implement sliding windows on Enumerable types using C# extension methods.

What's a sliding window?

The concept of a sliding window is popular in some algorithms. When applied to a sequence of items, a window is a contiguous subsequence of possibly varying size, although in most cases the window size is fixed.

The sliding window examines a contiguous subsequence of input elements. Here, the window is positioned over the elements of indices 2 through 6, and has a size of 5.

Sliding windows are useful in a variety of situations. For example, the longest common substring problem can be solved using a sliding window algorithm. Likewise, sliding windows are used as part of TCP, one of the major communications methods of the Internet.

Using sliding windows in C#

In C#, getting one of the windows from an input sequence is easy. We can just use the Skip() and Take() extension methods:

// Start at index 3; consume 4 elements. Result is "4567".
var result = "12345678".Skip(3).Take(4);

What if we want all the windows of a particular size? In the above example, if we wanted all the windows of size 4, we'd like to have a list containing ["1234", "2345", ..., "5678"].

We could simply iterate this expression, invoking Skip() on our list of items with an index that varied from , where is equal to inputLength - windowSize + 1. But that's not terribly efficient, because if your window size is large you'll wind up repeating some of the same elements each time.

In fact, let's call windowSize and inputLength . On the i^th iteration, we have to traverse elements to get to the first element of the window, plus an additional elements for the window itself. So we have for the whole thing, which reduces to . This is , meaning that bigger window sizes are prohibitively more expensive if the window is small relative to the length of the input sequence.

Doing it a smarter way

So how do we get all of the windows of a particular Enumerable<T> in an efficient way? I put together this small extension method called ContiguousSubsequences that tries to do just that.

    public static IEnumerable<IEnumerable<T>> ContiguousSubsequences<T>(this IEnumerable<T> input, int windowSize) {
      if (windowSize < 1)
        yield break;

      int index = 0;
      var window = new List<T>(windowSize);
      window.AddRange(new T[windowSize]);
      foreach (var item in input) {
        bool initializing = index < windowSize;

        if (!initializing) {
          window = window.Skip(1).ToList();
          window.Add(default(T));
        }

        int itemIndex = initializing ? index : windowSize - 1;
        window[itemIndex] = item;

        index++;
        bool initialized = index >= windowSize;
        if (initialized)
          yield return new List<T>(window);
      }
    }

This extension method creates a sliding window of size windowSize and begins filling it up with elements from input. After the window is full (as determined by the state of initialized), we return the window after processing each new element.

In addition, once the window is full, all of the previous elements slide one place to the left inside the window (window.Skip(1).ToList()), and the newest element is appended (window.Add(default(T))). The resulting list then becomes the new window.

Notice that now each element in the input sequence is visited just once, by the foreach (var item in input) { enumerator.

Wrapping it up

Putting it all together, we get a much more useful result:

var results = "12345678".ContiguousSubsequences(4);
foreach (var result in results) {
   Console.WriteLine(new string(result.ToArray()));
}

which prints:

1234
2345
3456
4567
5678