Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

My Favorite Algorithm: Linear Time Median Finding (2018)

rcoh.me

Post reply on HN
Print view View original

151–160 of 189 posts

Re: My Favorite Algorithm: Linear Time Median Finding (2018)

#151

Post by Filligree »

rented_mule wrote: post #102

10-15 years ago, I found myself needing to regularly find the median of many billions of values, each parsed out of a multi-kilobyte log entry. MapReduce was what we were using for processing large amounts of data at the time. With MapReduce over that much data, you don't just want linear time, but ideally single pass, distributed across machines. Subsequent passes over much smaller amounts of data are fine. It was a…

Was this by any chance for generating availability metrics, and were you an intern at the time? The system sounds, ah, very familiar.

Re: My Favorite Algorithm: Linear Time Median Finding (2018)

#152

Post by praptak »

kwantam wrote: post #141

One of the fun things about the median-of-medians algorithm is its completely star-studded author list. Manuel Blum - Turing award winner in 1995 Robert Floyd - Turing award winner in 1978 Ron Rivest - Turing award winner in 2002 Bob Tarjan - Turing award winner in 1986 (oh and also the inaugural Nevanlinna prizewinner in 1982) Vaughan Pratt - oh no, the only non-Turing award winner in the list. Oh right but he's eme…

Some other awesome stuff by Pratt:

Pratt parsing (HN discussion: https://news.ycombinator.com/item?id=39066465), the "P" in the KMP algorithm.

Re: My Favorite Algorithm: Linear Time Median Finding (2018)

#153

Post by dataflow »

Cleonis wrote: post #148
dataflow wrote: post #77

Earlier quoted context omitted.

Yeah, what I hate about MSD is the stack explosion. Otherwise - cool, thanks!

Hi, I want to respond to a post from you from 2019. (That 2019 thread no longer offers the reply button, otherwise I would reply there of course.) I apologize for using this thread to get my message in. This is the item I want to respond to: https://news.ycombinator.com/item?id=19768492 When you took a Classical Mechanics course you were puzzled by the form of the Lagrangian: L = T - V I have created a resource for t…

Haha wow, this was definitely random. Thank you for letting me know, I'll take a look when I have the chance.

Re: My Favorite Algorithm: Linear Time Median Finding (2018)

#154

Post by thanatropism »

danlark wrote: post #33

Around 4 years ago I compared lots of different median algorithms and the article turned out to be much longer than I anticipated :) https://danlark.org/2020/11/11/miniselect-practical-and-gene...

Is any of those easily modifiable to return the arg-median (the index which has the median).

Re: My Favorite Algorithm: Linear Time Median Finding (2018)

#155

Post by hammeiam »

IncreasePosts wrote: post #79
hammeiam wrote: post #52

The "Split the array into subarrays of length 5, now sorting all of the arrays is O(n) instead of O(n log n)" feels like cheating to me

It would only be cheating if you could merge the arrays in O(1), which you can't.

ahh this is the insight I was missing, thank you!

Re: My Favorite Algorithm: Linear Time Median Finding (2018)

#156

Post by davidmurdoch »

jiggawatts wrote: post #144
rented_mule wrote: post #111

Earlier quoted context omitted.

The kind of margin you indicate would have been plenty for our use cases. But, we were already processing all these log entries for multiple other purposes in a single pass (not one pass per thing computed). With this single pass approach, the median calculation could happen with the same single-pass parsing of the logs (they were JSON and that parsing was most of our cost), roughly for free. Uniform sampling also wa…

Speaking of "single pass", one of the criticisms I have of the "enumerator" patterns in modern programming languages is that they encourage multiple passes. As an example: computing the .min() and .max() of an enumerable is two passes even though it could be done with one pass. I'd love to see a language embrace a more efficient style similar to how a SQL does it, where you can elegantly request this as a single pass…

Does C# have the plumbing for this built in? It's been 7 years since using it so I might not be remembering correctly.

Re: My Favorite Algorithm: Linear Time Median Finding (2018)

#157

Post by _dain_ »

jiggawatts wrote: post #144
rented_mule wrote: post #111

Earlier quoted context omitted.

The kind of margin you indicate would have been plenty for our use cases. But, we were already processing all these log entries for multiple other purposes in a single pass (not one pass per thing computed). With this single pass approach, the median calculation could happen with the same single-pass parsing of the logs (they were JSON and that parsing was most of our cost), roughly for free. Uniform sampling also wa…

Speaking of "single pass", one of the criticisms I have of the "enumerator" patterns in modern programming languages is that they encourage multiple passes. As an example: computing the .min() and .max() of an enumerable is two passes even though it could be done with one pass. I'd love to see a language embrace a more efficient style similar to how a SQL does it, where you can elegantly request this as a single pass…

What's wrong with doing it in two passes? N iterations each doing 2 operations is exactly the same cost as 2*N iterations each doing 1 operation. Because multiplication is commutative.

Re: My Favorite Algorithm: Linear Time Median Finding (2018)

#158

Post by buildbot »

_dain_ wrote: post #157
jiggawatts wrote: post #144

Earlier quoted context omitted.

Speaking of "single pass", one of the criticisms I have of the "enumerator" patterns in modern programming languages is that they encourage multiple passes. As an example: computing the .min() and .max() of an enumerable is two passes even though it could be done with one pass. I'd love to see a language embrace a more efficient style similar to how a SQL does it, where you can elegantly request this as a single pass…

What's wrong with doing it in two passes? N iterations each doing 2 operations is exactly the same cost as 2*N iterations each doing 1 operation. Because multiplication is commutative.

This is true, but a big advantage of the single pass method is data reuse. Instead of loading each element twice, you load each element once. Per bit, reading/writing to external memory is massively more energy intensive than any compute op. Orders of magnitude more.

Re: My Favorite Algorithm: Linear Time Median Finding (2018)

#159

Post by rented_mule »

Filligree wrote: post #151
rented_mule wrote: post #102

10-15 years ago, I found myself needing to regularly find the median of many billions of values, each parsed out of a multi-kilobyte log entry. MapReduce was what we were using for processing large amounts of data at the time. With MapReduce over that much data, you don't just want linear time, but ideally single pass, distributed across machines. Subsequent passes over much smaller amounts of data are fine. It was a…

Was this by any chance for generating availability metrics, and were you an intern at the time? The system sounds, ah, very familiar.

The metrics were about speed. And I was decades past my last internship at the time in question. But, as is so often the case, more than one of us may have been reinventing pretty similar wheels. :)

Re: My Favorite Algorithm: Linear Time Median Finding (2018)

#160

Post by srcreigh »

_dain_ wrote: post #157
jiggawatts wrote: post #144

Earlier quoted context omitted.

Speaking of "single pass", one of the criticisms I have of the "enumerator" patterns in modern programming languages is that they encourage multiple passes. As an example: computing the .min() and .max() of an enumerable is two passes even though it could be done with one pass. I'd love to see a language embrace a more efficient style similar to how a SQL does it, where you can elegantly request this as a single pass…

What's wrong with doing it in two passes? N iterations each doing 2 operations is exactly the same cost as 2*N iterations each doing 1 operation. Because multiplication is commutative.

It’s more like 2NM where M is loading the data from disk/memory. One pass is 2N+M.

Why go to the store and back twice to buy two things instead of buying two things in one trip? ;p

Post reply on HN