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

141–150 of 189 posts

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

#141

Post by kwantam »

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 emeritus faculty at Stanford, directed the SUN project before it became Sun Microsystems, was instrumental in Sun's early days (director of research and designer of the Sun logo!), and is responsible for all kinds of other awesome stuff (near and dear to me: Pratt certificates of primality).

Four independent Turing awards! SPARCstations! This paper has it all.

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

#142

Post by Munksgaard »

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…

Here's a direct link for anyone who, like me, would be interested in reading the original article: https://people.csail.mit.edu/rivest/pubs/BFPRT73.pdf

That's an impressive list of authors, for sure.

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

#143

Post by jiggawatts »

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…

Job interview question for an entry-level front end developer: "Reproduce the work of four Turing award winners in the next thirty minutes. You have a dirty whiteboard and a dry pen. Your time begins... now."

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

#144

Post by jiggawatts »

rented_mule wrote: post #111
justinpombrio wrote: post #103

Earlier quoted context omitted.

Did you actually need to find the true median of billions of values? Or would finding a value between 49.9% and 50.1% suffice? Because the latter is much easier: sample 10,000 elements uniformly at random and take their median. (I made the number 10,000 up, but you could do some statistics to figure out how many samples would be needed for a given level of confidence, and I don't think it would be prohibitively large…

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 over the data: "SELECT min(x), max(x) FROM y"

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

#145

Post by geraldwhen »

Xcelerate wrote: post #10

I received a variant of this problem as an interview question a few months ago. Except the linear time approach would not have worked here, since the list contains trillions of numbers, you only have sequential read access, and the list cannot be loaded into memory. 30 minutes — go. First I asked if anything could be assumed about the statistics on the distribution of the numbers. Nope, could be anything, except the…

These are horrible interview questions. Data issues like this do pop up in the real world; heck I deal with them.

But when you run into or , the correct solution is to slow down, Google, then document your work as you go. In a real application log n may be insufficient. But coding interview exercises need tight constraints to fit the nature of the interview.

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

#146

Post by mjburgess »

rhymer wrote: post #133
enriquto wrote: post #112

Earlier quoted context omitted.

> the latter is much easier: sample 10,000 elements uniformly at random and take their median Do you have a source for that claim? I don't see how could that possibly be true... For example, if your original points are sampled from two gaussians of centers -100 and 100, of small but slightly different variance, then the true median can be anywhere between the two centers, and you may need a humungous number of sample…

Asymptotic properties of quantile estimators are widely studied [1]. The key is to have a sufficiently large sample size. [1] Bahadur, R. R. (1966). A note on quantiles in large samples. Annals of Mathematical Statistics, 37, 577–580.

Yet, for any given distribution the sample size can be arbitrarily close to infinite. Unless I've missed something, I don't see the relevance.

If you want the n-9s rate of failure (eg., n=5, 99.999) for a system with a power-law performance distribution, you could be waiting much more than a billion samples to see a failure.

eg., 3E10 ms (30 bn samples) in a year, at 5-9s failure rate has 3E3 ms of failure (3 thousand samples) -- which will be lower given a sampling strategy.

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

#147

Post by mnw21cam »

jagged-chisel wrote: post #87

It's quicksort with a modification to select the median during the process. I feel like this is a good way to approach lots of "find $THING in list" questions.

It's quicksort, but neglecting a load of the work that quicksort would normally have to do. Instead of recursing twice, leading to O(nlogn) behaviour, it's only recursing once.

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

#148

Post by Cleonis »

dataflow wrote: post #77
anonymoushn wrote: post #55

Earlier quoted context omitted.

> For MSD, do you get a performance hit from putting your stack on the heap (to avoid overflow on recursion)? I'm not sure. My original C++ implementation which is for non-adversarial inputs puts the array containing histograms and indices on the heap but uses the stack for a handful of locals, so it would explode if you passed the wrong thing. The sort it's based on in the parallel-string-sorting repo works the same…

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 the purpose of making application of calculus of variations in mechanics transparent. As part of that the form of the Lagrangian L=T-V is explained.

http://cleonis.nl/physics/phys256/calculus_variations.php

http://cleonis.nl/physics/phys256/energy_position_equation.p...

I recognize the 'you are certainly entitled to ask why' quote, it's from the book 'Classical Mechanics' by John Taylor.

Here's the thing: there is a good answer to the 'why' question. Once you know that answer things become transparent, and any wall is gone.

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

#149

Post by cerved »

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 preventing you from doing it in one pass?

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

#150

Post by jagged-chisel »

klyrs wrote: post #115
jagged-chisel wrote: post #105

Earlier quoted context omitted.

Indeed. But I need clarity on which skill they want to test in thirty minutes.

Speaking as an interviewer: nope, you're not being tested on a single skill.

See, that's what the multi-round, two-hour interview blocks are for. Each interview tests a different set of skills.

If you're testing on algorithm implementation and requirements gathering in thirty minutes, you're not testing for the skills you claim to be testing for. There's no way you're getting a good (let alone accurate) picture of the candidate's ability to gather requirements and implement those requirements, especially if your selection tactic is to deny them because they didn't get the PhD answer.

You're testing for how good of a minion this candidate will be.

Post reply on HN