rolling

A collection of computationally efficient rolling window iterators for Python.

This module implements useful arithmetical, logical and statistical functions on rolling/moving/sliding windows. There's also a flexible 'apply' mode where any user-defined function can be used on the window. Both fixed-length and variable-length window iteration is supported.

To get started, see the Quickstart section below, or have a look at the some Recipes.

Overview

Suppose we have a list x and we want to find the maximum of each window of 3 values. We could use Python's max() function and write [max(x[i:i+3]) for i in range(len(x) - 2)] to do this, for example.

But applying builtin Python's functions (like max() and sum()) to a window becomes increasingly slow as the window gets larger. The complexity is typically linear (i.e. O(k) where k is the size of the window).

For for many operations there are algorithms that return the value for the next window in sublinear time (e.g. O(log k)) or constant time (O(1)). The algorithms implemented so far in this module are summarised below:

See the References section below for more details about the algorithms and links to other resources.

Installation

There are no external library dependencies for running this module.

The module is tested with Python 3.5 and above, and Python 3.4 is also known to work. Python 2 is not currently supported.

You can install it using pip install rolling.

Alternatively, you can install from source:

git clone https://github.com/ajcr/rolling.git
cd rolling/
pip install .

If you want to run the tests you'll need to install pytest. Once done, just run pytest from the base directory.

Quickstart

Import the rolling module:

>>> import rolling

Now suppose we have this list:

>>> counts = [1, 5, 2, 0, 3]

We can create an iterator object over this list that performs a reduction operation for a given window size (3 in this case):

>>> r_sum = rolling.Sum(counts, 3)
>>> r_all = rolling.All(counts, 3)
>>> r_max = rolling.Max(counts, 3)

The result of iterating over each rolling object using list() is shown below. Note that the window type is fixed by default, meaning that only full windows of the specified size are used:

>>> list(r_sum)
[8, 7, 5] # i.e. [1+5+2, 5+2+0, 2+0+3]

>>> list(r_all)
[True, False, False]

>>> list(r_max)
[5, 5, 3]

As well as the built-in efficient algorithms provided by this module, any callable Python object can be applied to a rolling window using the Apply() class. For instance, Python's tuple() function:

>>> r_list = rolling.Apply(counts, 3, operation=tuple)
>>> list(r_list)
[(1, 5, 2), (5, 2, 0), (2, 0, 3)]

Variable-length windows can be specified using the window_type argument. This allows windows smaller than the specified size to be evaluated at the beginning and end of the iterable. For instance:

>>> r_list = rolling.Apply([1, 5, 2, 0, 3], 3, operation=list, window_type='variable')
>>> list(r_list)
[[1],
 [1, 5],
 [1, 5, 2],
 [5, 2, 0],
 [2, 0, 3],
 [0, 3],
 [3]]

References and resources

Some rolling algorithms are widely known (e.g. 'Sum') and I am not sure which source to cite. Some algorithms I made up (e.g. 'Any', 'All') but these are relatively simple and probably exist elsewhere.

Other rolling algorithms are very cleverly designed and I learned a lot by reading about them and seeing other peoples' implementations. Here are the main resources that I used:

• Max and Min are implemented using the Ascending Minima and Descending Maxima algorithms described by Richard Harter here. This algorithm is also used in pandas and bottleneck. My attention was first drawn to this algorithm by Jaime Fernandez del Rio's excellent talk 'The Secret Life Of Rolling Pandas'. The algorithm is also described by Keegan Carruthers-Smith here, along with code examples.

• Median uses the indexable skiplist approach presented by Raymond Hettinger here.

• Var and Std use Welford's algorithm. I referred to the rolling variance implementation in pandas as well as an older edit of the Wikipedia page Algorithms for calculating variance.

Discussion and future work

The algorithms implemented by this module are chosen to be efficient in the sense that the cost of computing each new return value scales efficiently with the size of window.

In practice you might find that it is quicker not to use the the 'efficient' algorithm, and instead apply a function to the window. This is especially true for very small window sizes where the cost of updating a window is relatively complex. For instance, while the window size k is less than approximately 50, it may quicker to use rolling.Apply(array, k, min) (apply Python's builtin minimum function min()) rather than using rolling.Min(array, k).

With this in mind, in future it might be worth implementing some of the algorithms here in compiled code (e.g. as a C extension module, or using Cython) to improve speed.