median implementation is slow

[belm0]

TLDR; don't use skip lists

I've found that a sorted list implemented with standard list + bisect module will be faster for tracking median than rolling's implementation up to about N < 50,000. For example, for N of 10,000 it's 4x faster. Resources explaining why list + bisect are unbeatable at these sizes: http://www.grantjenks.com/docs/sortedcontainers/implementation.html, http://www.grantjenks.com/docs/sortedcontainers/performance-scale.html

Of course, rolling would want to perform well for N > 50,000 too. So use sortedcontainers.SortedList. Even though it doesn't beat standard list + bisect until about N of 20,000, it's still faster than rolling's implementation for all sizes. For example, for N of 100,000 using SortedList is 2x faster.

[ajcr]

Many thanks for this interesting observation and links, @belm0.

List + bisect sounds like a good first alternative to the skiplist and shouldn't be too difficult to implement (?).

Perhaps if there's demand for increased performance at the window sizes you mention, SortedList can be used. I quite like the fact that rolling has no third-party dependencies yet, but there's no requirement to keep it this way if there's a good reason to use one.