Fast Median Filter over arbitrary datatypes (opens in new tab)

(martianlantern.github.io)

38 pointsmartianlantern3mo ago2 comments

2 comments

Just because the article mentions median-of-medians, I'd like to call out median-of-ninthers: https://erdani.org/research/sea2017.pdf

I was able to use this to implement practical deterministic linear time median selection in Go: https://github.com/ncruces/sort/blob/main/quick/quick.go

munro3mo ago

seriously cool, i just did something similar with quantiles for even bucketizing on arb key data types (still needs ord tho)

j / k navigate · click thread line to collapse

Just because the article mentions median-of-medians, I'd like to call out median-of-ninthers: https://erdani.org/research/sea2017.pdf

I was able to use this to implement practical deterministic linear time median selection in Go: https://github.com/ncruces/sort/blob/main/quick/quick.go

munro3mo ago

seriously cool, i just did something similar with quantiles for even bucketizing on arb key data types (still needs ord tho)

j / k navigate · click thread line to collapse