Fast way to get rolling percentile ranks

Viewed 896

Let's say we have a pandas df like this:

        A    B    C
day1  2.4  2.1  3.0
day2  4.0  3.0  2.0
day3  3.0  3.5  2.5
day4  1.0  3.1  3.0
.....

I want to get for all columns rolling percentile ranks, with a window of 10 observations. The following code works but it's slow:

scores = pd.DataFrame().reindex_like(df).replace(np.nan, '', regex=True)
scores = df.rolling(10).apply(lambda x: stats.percentileofscore(x, x[-1]))

I also tried this, but it's even slower:

def pctrank(x):
    n = len(x)
    temp = x.argsort()
    ranks = np.empty(n)
    ranks[temp] = (np.arange(n) + 1) / n
    return ranks[-1]
scores = df.rolling(window=10,center=False).apply(pctrank)

Is there a faster solution? Thanks

3 Answers

As you want the rank of a single element in the rolling window, you don't need to sort at every step. You could just compare the last value to all others in the window:

def pctrank_comp(x):
    x = x.to_numpy()
    smaller_eq = (x <= x[-1]).sum()
    return smaller_eq / len(x)

To remove the apply overhead, you could rewrite the same in NumPy, using the slide_tricks from NumPy v1.20:

from numpy.lib.stride_tricks import sliding_window_view
data = df.to_numpy()
sw = sliding_window_view(data, 10, axis=0)
scores_np = (sw <= sw[..., -1:]).sum(axis=2) / sw.shape[-1]
scores_np_df = pd.DataFrame(scores_np, columns=df.columns)

This doesn't contain the first 9 NaN values per column, as your solution, I'll leave it up to you to fix that, if needed.

Switching the sliding window axis from the last axis to the first gives another performance improvement:

sw = sliding_window_view(data, 10, axis=0).T
scores_np = (sw <= sw[-1:, ...]).sum(axis=0).T / sw.shape[0]

To benchmark, some testing data with 1000 rows:

df = pd.DataFrame(np.random.uniform(0, 10, size=(1000, 3)), columns=list("ABC"))

Original solution from question comes in at 381ms:

%timeit scores = df.rolling(window=10,center=False).apply(pctrank)
381 ms ± 2.62 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Diff implementation using apply, ~5x faster on my machine:

%timeit scores_comp = df.rolling(window=10,center=False).apply(pctrank_comp)
71.9 ms ± 318 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

The groupby solution from Cimbali's answer, ~45x faster on my machine:

%timeit grouped = pd.concat({n: df.shift(n) for n in range(10)}).groupby(level=1); scores_grouped = grouped.rank(pct=True).loc[0].where(grouped.count().eq(10))
8.49 ms ± 182 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Pandas sliding window from @Cimbali, ~105x faster:

%timeit scores_concat = pd.concat({n: df.shift(n).le(df) for n in range(10)}).groupby(level=1).sum() / 10
3.63 ms ± 136 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Sum shift version from @Cimbali, ~141x faster:

%timeit scores_sum = sum(df.shift(n).le(df) for n in range(10)).div(10)
2.71 ms ± 70.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

The Numpy sliding window solution from above. For 1000 elements, it's faster than the Pandas versions, at ~930x (and possibly uses less memory?), but more complicated. For larger datasets, it becomes slower than the Pandas version.

%timeit data = df.to_numpy(); sw = sliding_window_view(data, 10, axis=0); scores_np = (sw <= sw[..., -1:]).sum(axis=2) / sw.shape[-1]; scores_np_df = pd.DataFrame(scores_np, columns=df.columns)
409 µs ± 4.43 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

The fastest solution is moving the axes around, 2800x faster than the original version for 1000 rows, and about 2x faster than the Pandas sum version for 1M rows:

%timeit data = df.to_numpy(); sw = sliding_window_view(data, 10, axis=0).T; scores_np = (sw <= sw[-1:, ...]).sum(axis=0).T / sw.shape[0]; scores_np_df = pd.DataFrame(scores_np, columns=df.columns)
132 µs ± 750 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Here’s the way to write this with pandas-only tools, where pd.DataFrame.rank() comes in handy:

df.rolling(10).apply(lambda x: x.rank(pct=True).iloc[-1])

If this remains very slow and your window is reasonable, you could concatenate across an axis to generate all the values to compare, and then use groupby.rank() to compare within each set of values:

>>> pd.concat({n: df.shift(10 - n) for n in range(10)})
         A     B
0 0    NaN   NaN
  1    NaN   NaN
  2    NaN   NaN
  3    NaN   NaN
  4    NaN   NaN
...    ...   ...
9 95  17.0   9.0
  96  12.0  11.0
  97  11.0  19.0
  98   4.0  15.0
  99   8.0  17.0

[1000 rows x 2 columns]
>>> grouped = pd.concat({n: df.shift(n) for n in range(10)}).groupby(level=1)
>>> grouped.rank(pct=True).loc[0].where(grouped.count().eq(10))
       A     B
0    NaN   NaN
1    NaN   NaN
2    NaN   NaN
3    NaN   NaN
4    NaN   NaN
..   ...   ...
95  0.75  0.50
96  0.60  1.00
97  0.20  0.60
98  0.50  0.70
99  0.75  0.35

[100 rows x 2 columns]

We can compare this with @w-m’s great answer which computes ranks using sums, this gives slightly different results, probably in the case of tie-breaks between grades. The sliding window view computation using pandas could look like:

>>> sum(df.shift(n).le(df) for n in range(10)).div(10)
      A    B
0   0.1  0.1
1   0.1  0.2
2   0.1  0.1
3   0.2  0.1
4   0.1  0.4
..  ...  ...
95  0.8  0.5
96  0.6  1.0
97  0.2  0.6
98  0.5  0.7
99  0.8  0.4

[100 rows x 2 columns]

Note that you can always add .where(df.index.to_series().ge(10)) to the resulting dataframes to remove the 10 first rows.

Here’s what happens when I compare these solutions and both from @w-m’s post: enter image description here

You can see the sliding window remains faster. If you’re using pandas you might as well use the rank(), it’s not that much slower and gives you more flexibility. .apply() techniques are always slow.

Results obtained with:

import numpy as np, pandas as pd, timeit

glob = {'df': pd.DataFrame(np.random.uniform(0, 10, size=(1000, 3)), columns=list("ABC")), 'pctrank': pctrank, 'pctrank_comp': pctrank_comp, 'sliding_window_view': np.lib.stride_tricks.sliding_window_view, 'pd': pd}
timeit.timeit('df.rolling(window=10,center=False).apply(pctrank)', globals=glob, number=10) / 10
timeit.timeit('df.rolling(window=10,center=False).apply(pctrank_comp)', globals=glob, number=100) / 100
timeit.timeit('data = df.to_numpy(); sw = sliding_window_view(data, 10, axis=0); pd.DataFrame((sw <= sw[..., -1:]).sum(axis=2) / sw.shape[-1], columns=df.columns)', globals=glob, number=10_000) / 10_000
timeit.timeit('pd.concat({n: df.shift(n).le(n) for n in range(10)}).groupby(level=1).sum()', globals=glob, number=10_000) / 10_000
timeit.timeit('sum(df.shift(n).le(df) for n in range(10)).div(10)', globals=glob, number=10_000) / 10_000
timeit.timeit('pd.concat({n: df.shift(n) for n in range(10)}).groupby(level=1).rank(pct=True).loc[0]', globals=glob, number=1000) / 1000
Related