Adding an update-based sliding_window function

Start with the existing sliding_window entry point and review the discussion around pull request #321, along with the related reduceby and accumulate APIs. Compare the proposed slideby variants and examples, then determine the accepted name and API. Done means the feature is integrated with the testing, optimization, and documentation requested in the issue.

Hi,

I love the toolz package and am trying to use it more and more. The sliding_window function is a great start but often there are great efficiency gains by processing only the update to the sliding window rather than the whole window, like for example when calculating rolling sums or means. So I'm wondering whether we could add something like a slideby function in the spirit of reduceby or accumulate?

I wrote a basic one that is based off the sliding_window function:

from cytoolz import sliding_window, first, last

def slideby0(n, seq, update=None, init=None):
    windows = sliding_window(n, seq)
    initseq = first(windows)
    if callable(init):
        state = init(initseq)
    elif init is not None:
        state = init
    else:
        state = initseq
    leaving = first(initseq)
    yield state
    for window in windows:
        entering = last(window)
        if update is not None:
            state = update(entering, leaving, state)
        else:
            state = state[1:] + (entering,)
        yield state
        leaving = first(window)

After finding the discussion thread for pull request #321 and seeing one of @eriknw 's versions of sliding_window I came up with the following:

from itertools import tee, islice, izip

def slideby(n, seq, update=None, init=None):
    it = iter(seq)
    front, back = tee(it, 2)
    initseq = tuple(islice(front, n))
    if init is None:
        state = initseq
    elif callable(init):
        state = init(initseq)
    else:
        state = init
    yield state
    for entering, leaving in izip(front, back):
        if update is None:
            state = state[1:]+(entering,)
        else:
            state = update(entering, leaving, state)
        yield state

This has the advantage that it allows us to reproduce the behaviour of sliding_window when the update and init parameters are omitted but allows for custom implementations of update and init where efficiency matters.

from toolz import sliding_window as py_sliding_window

print(list(py_sliding_window(3, range(5))))
print(list(slideby(3, range(5))))

[(0, 1, 2), (1, 2, 3), (2, 3, 4)]
[(0, 1, 2), (1, 2, 3), (2, 3, 4)]

The basic sliding window performance is better than the pytoolz version on my system (version 0.7.2) and is not far off the cytoolz version. I haven't tested the new improved versions in PR #321 though.

import toolz
print(toolz.__version__)
W, N = 250, 10000
%timeit list(cy_sliding_window(W, range(N)))
%timeit list(py_sliding_window(W, range(N)))
%timeit list(slideby(W, range(N)))

0.7.2
10 loops, best of 3: 18.9 ms per loop
10 loops, best of 3: 31.9 ms per loop
10 loops, best of 3: 23.4 ms per loop

However the main point is really to allow for efficient implementations of rolling operations and here the algorithmic improvements far outweigh any cython speedups.

# Rolling sums
from cytoolz import sliding_window as cy_sliding_window
print(map(sum, py_sliding_window(3, range(5))))
print(map(sum, cy_sliding_window(3, range(5))))
print(list(slideby(3, range(5), update=lambda e, l, s: s+e-l, init=sum)))

W, N = 250, 10000
%timeit map(sum, py_sliding_window(W, range(N)))
%timeit map(sum, cy_sliding_window(W, range(N)))
%timeit list(slideby(W, range(N), update=lambda e, l, s: s+e-l, init=sum))

[3, 6, 9]
[3, 6, 9]
[3, 6, 9]
10 loops, best of 3: 36.5 ms per loop
10 loops, best of 3: 24.7 ms per loop
100 loops, best of 3: 2.21 ms per loop

# Rolling means
print(list(py_sliding_window(3, range(5))))
print(map(np.mean, py_sliding_window(3, range(5))))
print(map(np.mean, cy_sliding_window(3, range(5))))
print(list(slideby(3, range(5), update=lambda e, l, s: s+(e-l)/3, init=np.mean)))

W, N = 250, 10000
%timeit map(np.mean, py_sliding_window(W, range(N)))
%timeit map(np.mean, cy_sliding_window(W, range(N)))
%timeit list(slideby(W, range(N), update=lambda e, l, s: s+(e-l)/W, init=np.mean))

[(0, 1, 2), (1, 2, 3), (2, 3, 4)]
[1.0, 2.0, 3.0]
[1.0, 2.0, 3.0]
[1.0, 2.0, 3.0]
1 loops, best of 3: 300 ms per loop
1 loops, best of 3: 287 ms per loop
100 loops, best of 3: 3.81 ms per loop

So while I could just use my own implementation, it would be great if this could be integrated into the toolz package to get the assurance and reliability from the testing, optimisation and documentation that make this package great!

Any comments and suggestions for a better name or API welcome!