BUG: Fix #46726; wrong result with varying window size min/max rolling calc.
State: closed

- [x] closes #46726 
- [x] [Tests added and passed](https://pandas.pydata.org/pandas-docs/dev/development/contributing_codebase.html#writing-tests) 
- [x] All [code checks passed](https://pandas.pydata.org/pandas-docs/dev/development/contributing_codebase.html#pre-commit).
- [x] Added [type annotations](https://pandas.pydata.org/pandas-docs/dev/development/contributing_codebase.html#type-hints) to new arguments/methods/functions.
- [x] Speed improved by ~10% as measured by ASV.
- [x] added an entry in the latest `doc/source/whatsnew/v3.0.0.rst`.

### Summary:

-	Fixes a 3-year-old bug with incorrect min/max rolling calculation for custom window sizes. Adds an error check for invalid inputs.
-	Speed improvement of ~10% by not using additional queue for handling NaNs.
-	For complex cases, incurs additional multiplicative log(k) complexity (where k is max window size), but this cost is only incurred in cases that produced invalid result before. For example, for constant window size this cost is not incurred.

### Changed behavior:
Has additional validity check, which will raise ValueError if the function detects a condition it cannot work with, namely improper ordering of start/end bounds. The existing method would happily consume such input and would produce a wrong result. There is a new unit test to check for the raised ValueError.

### Note on invalid inputs:

It is possible to make the method work for an arbitrary stream of start/end window bounds, but it will require sorting. It is very unlikely that such work is worth the effort, and it is estimated to have extremely low need, if any. Let someone create an enhancement request first. 
If sorting is to be implemented: it can be done with only incurring performance hit in the case of unsorted input: copy and sort the start/end arrays, producing a permutation, run the main method on the copy, and then extract the result back using the permutation. To detect if the start/end array pair is properly sorted will only take O(N). (Soring is N*log(N), does not have to be stable, but the input array is extremely likely to be “almost” sorted, and you have to pick your poison of a sorting method that works well with nearly sorted array, or use efficient soring methods, most of which do not offer additional speed on nearly sorted arrays.) Working such intermediate step (without copying and pasting) into 3 different implementations will require some less than straightforward work in the “apply” family of methods used by other rolling functions, and therefore will bear risk. If this is decided to be done, it is recommended to have an additional parameter to optionally skip the “sorted” check. (The user may already know that the arrays are properly sorted).

### How to Debug numba
You can temporarily change 2 lines of code in order to Python-debug numba implementation with VS Code or another Python debugger:
- Comment out the `numba.jit` decorator on the function(`sliding_min_max()` in `min_max_.py`). 
- Do the same with the `column_looper()` function defined inside the `generate_apply_looper()` function in **executor.py**.
- Your breakpoint inside the function will now hit!

### Misc Notes

The speed improvement of ~10% was confirmed in two ways:
-	As measured by pandas’ supplied asv benchmark suite (0.80-0.91 coefficient (depending on particular test) on my hardware).
-	With a custom load test over a 2MM-long rolling window on a 300MM-long data set. (See the supplied [bench.py.txt](https://github.com/user-attachments/files/19735182/bench.py.txt).) A single run of the test takes approx. 6-8 seconds and consumes ~15GB of RAM on a 32-GB RAM PC.



Labels:
name: Bug
name: Window
description: rolling, ewma, expanding

Comments:
@mroeschke, all done!
Edited my original comment to reflect what is actually being done. Thx!
(CI is still in progress. I will fix ti up if anything fails.)
Thank you for the thoughtful review. Give me some time (hopefully under a week) to read up on PEP8 and address other comments. Thanks for the helpful naming suggestions: only takes a minute, and saves me hours of time digging too deep into PEP8.
Thanks @viable-alternative!