Implementation:Online ml River Utils SortedWindow
| Knowledge Sources | |
|---|---|
| Domains | Online_Learning, Data_Structures, Sliding_Windows |
| Last Updated | 2026-02-08 16:00 GMT |
Overview
Maintains a fixed-size window of values in sorted order for efficient quantile computation.
Description
Implements a rolling window that keeps elements sorted using binary search for insertions and deletions. Maintains both a sorted list and an unsorted deque to track insertion order. Enables O(log n) insertions and efficient median/quantile computations on recent data.
Usage
Use for rolling quantiles, rolling medians, or any statistic requiring sorted access to recent values. Essential for robust statistics that need to handle outliers or compute percentiles.
Code Reference
Source Location
- Repository: Online_ml_River
- File: river/utils/sorted_window.py
Signature
class SortedWindow(collections.UserList):
def __init__(self, size: int):
...
def append(self, x) -> None:
...
@property
def size(self):
...
Import
from river import utils
Usage Examples
from river import utils
window = utils.SortedWindow(size=3)
# Add values in arbitrary order
for i in reversed(range(9)):
window.append(i)
print(window)
# Output:
# [8]
# [7, 8]
# [6, 7, 8]
# [5, 6, 7] (oldest value 8 removed)
# [4, 5, 6]
# [3, 4, 5]
# [2, 3, 4]
# [1, 2, 3]
# [0, 1, 2]
# Use for rolling median
print("\nRolling median example:")
window2 = utils.SortedWindow(size=5)
values = [10, 3, 7, 1, 9, 5, 8]
for val in values:
window2.append(val)
if len(window2) > 0:
median_idx = len(window2) // 2
median = window2[median_idx]
print(f"Window: {list(window2)}, Median: {median}")
# Use for rolling quantiles
window3 = utils.SortedWindow(size=10)
for i in range(15):
window3.append(i)
if len(window3) >= window3.size:
# 25th percentile
q25_idx = len(window3) // 4
print(f"25th percentile: {window3[q25_idx]}")
Related Pages
Page Connections
Double-click a node to navigate. Hold to expand connections.
Principle
Implementation
Heuristic
Environment