ENH: add time-window capability to .rolling
State: closed

xref #13327
closes #936 

This [notebook shows the usecase](http://nbviewer.jupyter.org/gist/jreback/186d09a99902a17a095d99ac6a5e4cd3)
- implement lint checking for cython (currently only for windows.pyx), xref #12995

This implements time-ware windows, IOW, to a `.rolling()` you can now pass a ragged / sparse timeseries and have it work with an offset (e.g. like `2s`). Previously you _could_ achieve these results by resampling first, then using an integer period (though you would have to jump thru hoops when crossing day boundaries and such). 

This now provides a nice easy / performant implementation (as indicated on the linked notebook, min/max impl is giving scaling issues).

```
In [1]: df = DataFrame({'B': range(5)})

In [2]: df.index = [Timestamp('20130101 09:00:00'),
   ...:             Timestamp('20130101 09:00:02'),
   ...:             Timestamp('20130101 09:00:03'),
   ...:             Timestamp('20130101 09:00:05'),
   ...:             Timestamp('20130101 09:00:06')]

In [3]: df
Out[3]: 
                     B
2013-01-01 09:00:00  0
2013-01-01 09:00:02  1
2013-01-01 09:00:03  2
2013-01-01 09:00:05  3
2013-01-01 09:00:06  4

In [4]: df.rolling(2, min_periods=1).sum()
Out[4]: 
                       B
2013-01-01 09:00:00  0.0
2013-01-01 09:00:02  1.0
2013-01-01 09:00:03  3.0
2013-01-01 09:00:05  5.0
2013-01-01 09:00:06  7.0

In [5]: df.rolling('2s', min_periods=1).sum()
Out[5]: 
                       B
2013-01-01 09:00:00  0.0
2013-01-01 09:00:02  1.0
2013-01-01 09:00:03  3.0
2013-01-01 09:00:05  3.0
2013-01-01 09:00:06  7.0
```


Labels:
name: Enhancement
name: Datetime
description: Datetime data dtype
name: Numeric Operations
description: Arithmetic, Comparison, and Logical operations

Comments:
cc @jorisvandenbossche 
cc @wesm 
cc @chrisaycock 
cc @joshuastorck 

if anyone would like to try to fixup min/max would be great. [here](https://github.com/jreback/pandas/commit/05331e8cff28734b491fc804a85aac19c8b8983b) is the same PR with a priority heap (but its a fair bit slower, I am probably doing something non-optimal).

closes https://github.com/pydata/pandas/issues/936

yeah we'll close #936 but I think that impl is a bit different.

## [Current coverage](https://codecov.io/gh/pydata/pandas/pull/13513?src=pr) is **84.39%**

> Merging [#13513](https://codecov.io/gh/pydata/pandas/pull/13513?src=pr) into [master](https://codecov.io/gh/pydata/pandas/branch/master?src=pr) will increase coverage by **0.01%**

``` diff
@@             master     #13513   diff @@
==========================================
  Files           142        142          
  Lines         51235      51299    +64   
  Methods           0          0          
  Messages          0          0          
  Branches          0          0          
==========================================
+ Hits          43234      43296    +62   
- Misses         8001       8003     +2   
  Partials          0          0          
```

> Powered by [Codecov](https://codecov.io?src=pr). Last updated by [084ceae...d8f3d73](https://codecov.io/gh/pydata/pandas/compare/084ceaee135627680f4dd00115c3d6c7d930a22d...d8f3d73c45a1c8f46d90814d7554ccc0f8f9bc49?src=pr)

Looks good to me. Regarding max/min, is the priority list faster than just recomputing the maximum value from scratch for each iteration? Caching and branch prediction can work wonders for small sample sizes.

Long awaited feature! Will try to review this today. 

Take a look at this: https://people.cs.uct.ac.za/~ksmith/articles/sliding_window_minimum.html.

You don't want to use a heap for min/max as it's worst case O(n \* log(n)). There is a more efficient algorithm that is O(N). It also should be a bit easier to implement as all you really need for a data structure is a deque. 

That's the algorithm that the existing implementation was using. 

@chrisaycock 

ok, silly of me not to test the completely naive soln, which is quite fast. It _still_ scales on O(n) where n is the window size, but now the constant is 1/10 of my prioritylist constant. So this is pretty reasonable.

```
In [1]: N = 100000                     
dfp = DataFrame({'B' : np.random.randn(N)}, 
                 index=pd.date_range('20130101',periods=N,freq='s'))
   ...: 

In [2]: %timeit dfp.rolling(10).min()
100 loops, best of 3: 2.47 ms per loop

In [3]: %timeit dfp.rolling('10s').min()
100 loops, best of 3: 3.2 ms per loop

In [4]: %timeit dfp.rolling(100).min()
100 loops, best of 3: 2.58 ms per loop

In [5]: %timeit dfp.rolling('100s').min()
100 loops, best of 3: 11.2 ms per loop

In [6]: %timeit dfp.rolling(1000).min()
100 loops, best of 3: 2.62 ms per loop

In [7]: %timeit dfp.rolling('1000s').min()
10 loops, best of 3: 97.2 ms per loop
```

@joshuastorck yes the deque is theoretically faster, but it was very awkward with a variable sized window; others welcome to take a shot thought!

Meta-comment: since getting exposed to Gerrit over the last couple years, large reviews on GitHub PR's tend to encourage less careful review (because it's difficult to keep track of what still needs doing sometimes), at least for me. It might be worth playing around with gerrithub.io sometime to mirror patches there for review sometimes. Not sure what's the best solution. 

This looks like it was quite a slog -- we should add to our ever-increasing TODO list a review of all of our aggregation code and ways to foster reuse or more flexibility. Trying to think if there was a way that this could have been made less painful. C++ templates could help (for example, a particular aggregator could be passed as a template argument, so the update inner loop could all get inlined at compile time -- e.g. the add_sum / remove_sum bits). But we'd need to decide if we want to commit to the route of writing more C++ and less Cython (I think there's good arguments for it, but evolving the build-and-deployment tools to accommodate that would be as discussed an upfront investment of work) -- this is somewhat orthogonal to the bigger discussion of writing more of the data structure internals in C or C++.  

Also, I'm always happy to see 4+ year-old issues that were once just a twinkle in my eye get realized, so better late than never =) Great stuff

I think there are a couple of compelling arguments for going to C++ templates, mostly that you can vary the implementation based on type at compile time. For example, since integer columns don't have NaN's, you don't really need the min_periods for rolling_\* functions and could use SFINAE for that distinction. Alternatively, you could put 'if' statements inside the inner loops that are based on type, such as 'if std::is_integral<T>::value". With the rolling functions, much of the looping code is common, but the algorithm and state varies. You can define a rolling_apply function that takes iterators, a functor/lambda and variadic arguments to hold the state. And it goes without saying that there are a lot of possibilities for using SIMD when dealing with contiguous columns.

The downside with C++ is that you have to do a lot of boilerplate dispatching code to templates based on numpy type, the cross-platform compile gets more complicated, and the code could arguably be harder to read. 

At a minimum, it would be worth comparing the runtime of hand converted Cython code, as the code generator for Cython introduces a lot of constructs that might make it harder for the compiler to do optimizations, such as sanity checks in inner loops that could probably be done up front.

@jreback There is a memory leak when using `center=True` (first time  I got a MemoryError, but second time it just crashed my computer :-))

@jorisvandenbossche I didn't change anything w.r.t. `center` (and its disabled for rolling with time series). can you show a repro?

With the example from your notebook: `df.rolling('2s', center=True).sum()`

@jorisvandenbossche pushed. Its not implemented. 

@jreback Took a first look, I also made a PR with some small doc fixes that I made along the way: https://github.com/jreback/pandas/pull/17

Some other comments:
- If the `on` column is set anyway as the index in the result, I don't see that much of advantage of adding this keyword, as it is exactly the same as just doing a `set_index('foo').rolling(..)` ?
  
  Further, I think this keyword only makes sense for datetimelike values with offset window? Probably we should raise in other cases that this is ignored? (if we keep the keyword)
- Can you update the docstring for `window` and `min_periods` keywords?

@jorisvandenbossche Indices are a huge nuisance for most users, so I had specifically requested the `on` keyword a while back.

@chrisaycock should the resulting frame then keep it as a column? (now the 'on' column is set as the index, so if you want it as a column, you have to do `reset_index()` after rolling)

@jorisvandenbossche actually that last is an error

```
In [1]:    dft = DataFrame({'B': [0, 1, 2, np.nan, 4]},
   ...:                    index = pd.Index([pd.Timestamp('20130101 09:00:00'),
   ...:                                      pd.Timestamp('20130101 09:00:02'),
   ...:                                      pd.Timestamp('20130101 09:00:03'),
   ...:                                      pd.Timestamp('20130101 09:00:05'),
   ...:                                      pd.Timestamp('20130101 09:00:06')],
   ...:                                     name='foo'))

In [2]: dft
Out[2]: 
                       B
foo                     
2013-01-01 09:00:00  0.0
2013-01-01 09:00:02  1.0
2013-01-01 09:00:03  2.0
2013-01-01 09:00:05  NaN
2013-01-01 09:00:06  4.0

In [3]: df = dft.reset_index()

In [4]: df
Out[4]: 
                  foo    B
0 2013-01-01 09:00:00  0.0
1 2013-01-01 09:00:02  1.0
2 2013-01-01 09:00:03  2.0
3 2013-01-01 09:00:05  NaN
4 2013-01-01 09:00:06  4.0

#### this should *not* set the index, instead it should remain a column (as it was to start), and the existing index should be preserved.
In [5]: df.rolling('2s', on='foo').sum()
Out[5]: 
                       B
foo                     
2013-01-01 09:00:00  0.0
2013-01-01 09:00:02  1.0
2013-01-01 09:00:03  3.0
2013-01-01 09:00:05  NaN
2013-01-01 09:00:06  4.0
```

ok, fixed up docs as suggested by @jorisvandenbossche 
- `on` now works correctly in that it doesn't actually set the index
- its now cheap to use `on` as just skipped during block creation and added back at the end. 
- the result frame will be in the same order as input (not checked and incorrect before)

Using a slightly different example for testing.

```
In [1]:        df = DataFrame({'A': [0, 1, 2, 3, 4],
   ...:                         'B': [0, 1, 2, np.nan, 4],
   ...:                         'C': pd.Index([pd.Timestamp('20130101 09:00:00'),
   ...:                                        pd.Timestamp('20130101 09:00:02'),
   ...:                                        pd.Timestamp('20130101 09:00:03'),
   ...:                                        pd.Timestamp('20130101 09:00:05'),
   ...:                                        pd.Timestamp('20130101 09:00:06')])},
   ...:                        columns=['A', 'C', 'B'])

In [2]: df
Out[2]: 
   A                   C    B
0  0 2013-01-01 09:00:00  0.0
1  1 2013-01-01 09:00:02  1.0
2  2 2013-01-01 09:00:03  2.0
3  3 2013-01-01 09:00:05  NaN
4  4 2013-01-01 09:00:06  4.0

In [3]: df.rolling('2s', on='C').sum()
Out[3]: 
     A                   C    B
0  0.0 2013-01-01 09:00:00  0.0
1  1.0 2013-01-01 09:00:02  1.0
2  3.0 2013-01-01 09:00:03  3.0
3  3.0 2013-01-01 09:00:05  NaN
4  7.0 2013-01-01 09:00:06  4.0

In [4]: df.rolling('2s', on='C').B.sum()
Out[4]: 
0    0.0
1    1.0
2    3.0
3    NaN
4    4.0
Name: B, dtype: float64

In [5]: df.rolling('2s', on='C')[['A', 'B', 'C']].sum()
Out[5]: 
     A    B                   C
0  0.0  0.0 2013-01-01 09:00:00
1  1.0  1.0 2013-01-01 09:00:02
2  3.0  3.0 2013-01-01 09:00:03
3  3.0  NaN 2013-01-01 09:00:05
4  7.0  4.0 2013-01-01 09:00:06
```

further comments?

@jorisvandenbossche 
@wesm 
@chrisaycock 

I think this is looking pretty good. Are you satisfied with the unit tests for correctness? If I'm being perfectly honest it feels a touch thin -- would it make sense to run a test like https://github.com/pydata/pandas/pull/13513/files#diff-51f469e6b0911fa166d4cc24e5123919R3513 on maybe a slightly smaller dataframe size but on all the rolling statistics? Maybe I missed some other tests that do that 

All looks good to me. I look forward to getting this into people's hands.

This functionality looks great, but I worry about overloading the first argument to `.rolling` with this orthogonal functionality (frequencies/label-units as well as integers). This is similar to the issues with fallback logic for ix/getitem. If the index is numeric, it will no longer be entirely obvious what `df.rolling(2)` means.

@shoyer this is not the same as fallback logic at all as its an explicit user choice. If you pass an offset and you have a time-based on/index then it will work, otherwise it will raise. Adding _another_ method to basically to the same `.rolling_time` just crowds the api and then forces users to jump thru too many hoops (what if I remove the index and switch it to a column, now I _also_ have to change the method name....bad).

I _agree_ however, that we could _deprecate_ using integer based with time-based on/index, though It IS still meaningful with a non-ragged freq. Up till now that has been the only way.

@wesm https://github.com/pydata/pandas/pull/13513/files#diff-51f469e6b0911fa166d4cc24e5123919R3568 covers the complete comparison. Though its a bit simplistic. I will add a more complete ragged example.

[here](https://github.com/pydata/pandas/pull/13513/commits/c9c420268af2748c88a8f708366bd08155eb4dea) is a doc update, is this more clear?

@wesm 

> >  Stephan:  I worry about overloading the first argument to .rolling with this orthogonal functionality
> 
> Jeff: Adding another method to basically to the same .rolling_time just crowds the api

@jreback It does not necessarily have to be another method, we could also use another _keyword_ to not overload the `windows` keyword.