3 ms·
Well, I believe you could use the streaming algorithms to pick the likely median, so help choose the pivot for the real quickselect. quickselect can be done inp
by conradludgate 2y ago
Well, I believe you could use the streaming algorithms to pick the likely median, so help choose the pivot for the real quickselect. quickselect can be done inplace too which is O(1) memory if you can afford to rearrange the data.
- SkiFire13 2y agoThen you don't get a guaranteed O(n) complexity if the approximated algorithm happen to make bad choices
- mgaunard 2y agosay you want the median value since the beginning of the day for a time series that has 1000 entries per second, that's potentially hundreds of gigabytes in RAM, or just a few variables if you use a p-square estimator.