# Regaining Lost Knowledge

DevFeed: [Regaining Lost Knowledge](<https://devfeed.tech/articles/regaining-lost-knowledge-21695.md>)

Original publisher: [Read original article](<https://rhettinger.wordpress.com/2010/02/06/lost-knowledge/>)

Author: rhettinger

Published: 2010-02-06T23:28:30Z

Content type: article

Language: en

Sources: [Raymond Hettinger](<https://devfeed.tech/sources/raymond-hettinger.md>)

Topics: [Running Median](<https://devfeed.tech/topics/running-median.md>), [Skiplists](<https://devfeed.tech/topics/skiplists.md>), [Algorithms](<https://devfeed.tech/topics/algorithms.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [data-structures](<https://devfeed.tech/tags/data-structures.md>), [knowledge](<https://devfeed.tech/tags/knowledge.md>), [lost-knowledge](<https://devfeed.tech/tags/lost-knowledge.md>), [median](<https://devfeed.tech/tags/median.md>), [python](<https://devfeed.tech/tags/python.md>), [running-median](<https://devfeed.tech/tags/running-median.md>), [skiplists](<https://devfeed.tech/tags/skiplists.md>), [sliding-window](<https://devfeed.tech/tags/sliding-window.md>), [wikipedia](<https://devfeed.tech/tags/wikipedia.md>)

## AI overview

The excerpt presents an indexable skiplist as a portable O(log n)-time approach to maintaining a running median in a sliding window. Earlier replies based on the median's small movement and a QuickSelect recipe were described as unusably slow for large windows; a published method offered O(√n), while a tree-based solution offered O(log n) but was messy to implement and depended on the blist extension for a ready implementation. Adding link widths to a skiplist made median indexing logarithmic, according to the author, and the resulting approach scales to large windows and is portable across languages. The excerpt claims this application had not previously been presented, while acknowledging the passage is truncated.

## Source excerpt

Rediscovery of Indexable Skiplists in the solution of the Running Median problem.