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

111–120 of 189 posts

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

#111

Post by rented_mule »

justinpombrio wrote: post #103
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…

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 wasn't obviously simple, at least to me. There were thousands of log files involved, coming from hundreds of computers. Any single log file only had timings from a single computer. What kind of bias would be introduced by different approaches to distributing those log files to a cluster for the median calculation? Once the solution outlined in the previous comment was identified, that seemed simpler that trying to understand if we were talking about 49-51% or 40-50%. And if it was too big a margin, restructuring our infra to allow different log file distribution algorithms would have been far more complicated.

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

#112

Post by enriquto »

justinpombrio wrote: post #103
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…

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 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 samples to get anywhere close to it.

True, in that case any point between say -90 and 90 would be equally good as a median in most applications. But this does not mean that the median can be found accurately by your method.

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

#113

Post by ant6n »

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…

I’m not sure why you use a dictionary with keys 0…999, instead of an array indexed 0…999.

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

#114

Post by maronato »

enriquto wrote: post #112
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 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…

the key word is “uniformly”. If your data is not uniformly distributed, then you just have to pick random values non-uniformly. There are many ways to do that, and once you have your algo you’ll be able to reliably find an approximation of the median much faster than you would find the actual median.

https://en.m.wikipedia.org/wiki/Non-uniform_random_variate_g...

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

#115

Post by klyrs »

jagged-chisel wrote: post #105
NoToP wrote: post #96

Earlier quoted context omitted.

Which in fairness, is a reasonable competency to test for in an interview

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.

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

#116

Post by mrguyorama »

mabbo wrote: post #42

I learned about the median-of-medians quickselect algorithm when I was an undergrad and was really impressed by it. I implemented it, and it was terribly slow. It's runtime grew linearly, but that only really mattered if you had at least a few billion items in your list. I was chatting about this with a grad student friend who casually said something like "Sure, it's slow, but what really matters is that it proves th…

We studied (I believe) this algorithm in my senior year of Computer Science. We talked about the theory side of it that you mention, but this algorithm was also used to demonstrate that "slow linear algorithm" is not faster than "Fast nlogn algorithm" in most real life cases.

I think we got a constant factor of 22 for this algorithm so maybe it was a related one or something.

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

#117

Post by TacticalCoder »

I really enjoyed TFA but this:

> Technically, you could get extremely unlucky: at each step, you could pick the largest element as your pivot. Each step would only remove one element from the list and you’d actually have O(n2) performance instead of O(n)

If adversarial input is a concern, doing a O(n) shuffle of the data first guarantees this cannot happen. If the data is really too big to shuffle, then only shuffle once a bucket is small enough to be shuffled.

If you do shuffle, probabilities are here to guarantee that that worst case cannot happen. If anyone says that "technically" it can happen, I'll answer that then "technically" an attacker could also guess correctly every bit of your 256 bits private key.

Our world is build on probabilities: all our private keys are protected by the mathematical improbability that someone shall guess them correctly.

From what I read, a shuffle followed by quickselect is O(n) for all practical purposes.

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

#118

Post by bo1024 »

TacticalCoder wrote: post #117

I really enjoyed TFA but this: > Technically, you could get extremely unlucky: at each step, you could pick the largest element as your pivot. Each step would only remove one element from the list and you’d actually have O(n2) performance instead of O(n) If adversarial input is a concern, doing a O(n) shuffle of the data first guarantees this cannot happen. If the data is really too big to shuffle, then only shuffle…

You're already using your own randomness to pick the pivot at random, so I don't see why the shuffle helps more. But yes, if your randomness is trustworthy, the probability of more than O(n) runtime is very low.

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

#119

Post by tomrod »

ant6n wrote: post #113
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…

I’m not sure why you use a dictionary with keys 0…999, instead of an array indexed 0…999.

That's just a dict/map with less flexibility on the keys :D

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

#120

Post by B1FF_PSUVM »

enriquto wrote: post #112
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 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…

> this does not mean that the median can be found accurately by your method.

You can do dynamic sampling: e.g. take double the samples, see what decimal in your result budges. Adjust.

Post reply on HN