Given a multidimensional array, I want to compute a rolling percentile over one of its axes, with the rolling windows truncated near the boundaries of the array. Below is a minimal example implementation using only numpy
via np.nanpercentile()
applied to stacked, rolled (through np.roll()
) arrays. However, the input array may be very large (~ 1 GB or more), so two issues arise:
- For the current implementation, the stacked, rolled array may
not fit into RAM memory. Avoidable with
for
-loops over all axes unaffected by the rolling, but may be slow. - Even fully vectorized (as below), the computation time is quite long, understandably due to the sheer amount of computations performed.
Questions: Is there a more efficient python
implementation of a rolling percentile (with axis/axes
argument or the like and with truncated windows near the boundaries)?** If not, how could the computation be sped up (and, if possible, without exceeding the RAM)? C-code called from Python? Computation of percentiles at fewer "central" points, and approximation in between via (e.g. linear) interpolation? Other ideas?
Related post (implementing rolling percentiles): How to compute moving (or rolling, if you will) percentile/quantile for a 1d array in numpy? Issues are:
pandas
implementation viapd.Series().rolling().quantile()
works only forpd.Series
orpd.DataFrame
objects, not multidimensional (4D or arbitrary D) arrays;- implementation via
np.lib.stride_tricks.as_strided()
withnp.nanpercentile()
is similar to the one below and should not be much faster given thatnp.nanpercentile()
is the speed bottleneck, see below
Minimal example implementation:
import numpy as np
np.random.seed(100)
# random array of numbers
a = np.random.rand(10000,1,70,70)
# size of rolling window
n_window = 150
# percentile to compute
p = 0.7
# NaN values to prepend/append to array before rolling
nan_temp = np.full(tuple([n_window] + list(np.array(a.shape)[1:])), fill_value=np.nan)
# prepend and append NaN values to array
a_temp = np.concatenate((nan_temp, a, nan_temp), axis=0)
# roll array, stack rolled arrays along new dimension, compute percentile (ignoring NaNs) using np.nanpercentile()
res = np.nanpercentile(np.concatenate([np.roll(a_temp, shift=i, axis=0)[...,None] for i in range(-n_window, n_window+1)],axis=-1),p*100,axis=-1)
# cut away the prepended/appended NaN values
res = res[n_window:-n_window]
Computation times (in seconds), example (for the case of a
having a shape of (1000,1,70,70) instead of (10000,1,70,70)):
create random array: 0.0688176155090332
prepend/append NaN values: 0.03478217124938965
stack rolled arrays: 38.17830514907837
compute nanpercentile: 1145.1418626308441
cut out result: 0.0004646778106689453