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

161–170 of 189 posts

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

#161

Post by neonsunset »

davidmurdoch wrote: post #156
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…

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

IEnumerable.Max and .Min are the same as they were just significantly faster through the use of SIMD: https://github.com/dotnet/runtime/blob/ebbebaca1184940f06df6...

You could implement a similar (and simpler) fast path for types with contiguous memory by performing min and max per iteration instead.

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

#162

Post by Cleonis »

dataflow wrote: post #153
Cleonis wrote: post #148

Earlier quoted context omitted.

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.

If I don't hear back in a week or so I will remind you, I hope that's OK with you.

I'm aware your expectations may be low. Your thinking may be: if textbook authors such as John Taylor don't know the why, then why would some random dude know?

The thing is: this is the age of search machines on the internet; it's mindblowing how searcheable information is. I've combed, I got to put pieces of information together that hadn't been put together before, and things started rolling.

I'm stoked; that's why I'm reaching out to people.

I came across the ycombinator thread following up something that Jess Riedel had written.

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

#163

Post by justinpombrio »

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…

I wasn't saying that you could get within 1% of the true median, I was saying you could find an element in the 49th to 51st percentile. In your example, the 49th percentile would be -90 and the 51st percentile would be 90, so the guarantee is that you would (with very high probability) find a number between -90 and 90.

That's a good point, though, that the 49th percentile and 51st percentile can be arbitrarily far from the median.

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

#164

Post by KMag »

mnw21cam wrote: post #147
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.

I used to ask how to find the 10th percentile value from an arbitrarily ordered list as an interview question. Most candidates suggested sorting, and then I'd ask if they could do better. If they got stuck, I'd ask them which sorting algorithm they'd suggest. If they suggested quicksort, then I could gently guide them down optimizing quicksort to quickselect. Most candidates made the mistake of believing getting rid of half the work at every division results in half the work overall. They realized it was significantly faster, but usually didn't realize it was O(N) expected time.

If we had time, I'd ask about the worst-case scenario, and see if they could optimize heapsort to heapselect. Good candidates could suggest starting out with selectsort optimistically and switching to heapselect if the number of recursions exceeded some constant times the number of expected recursions.

If they knew about median-of-medians, they could probably just suggest introselect at the start, and move on to another question.

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

#165

Post by ted_dunning »

jiggawatts wrote: post #143
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 ."

And if you really want to impress, you reach into your pack and pull out the pens you carry just in case you run into dry pens at a critical moment.

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

#166

Post by ted_dunning »

ssfrr wrote: post #124
fanf2 wrote: post #40

Earlier quoted context omitted.

There are two kinds: - quantile sketches, such as t-digest, which aim to control the quantile error or rank error. Apache DataSketches has several examples, https://datasketches.apache.org/docs/Quantiles/QuantilesOver... - histograms, such as my hg64, or hdr histograms, or ddsketch. These control the value error, and are generally easier to understand and faster than quantile sketches. https://dotat.at/@/2022-10-12-h…

Do these both assume the quantile is stationary, or are they also applicable in tracking a rolling quantile (aka quantile filtering)? Below I gave an algorithm I’ve used for quantile filtering, but that’s a somewhat different problem than streaming single-pass estimation of a stationary quantile.

Most quantile sketches (and t-digest in particular) do not assume stationarity.

Note also that there are other bounds of importance and each has trade-offs.

T-digest gives you a strict bound on memory use and no dynamic allocation. But it does not have guaranteed accuracy bounds. It gives very good accuracy in practice and is very good at relative errors (i.e. 99.999th percentile estimate is between the 99.9985%-ile and 99.9995%-ile)

KL-sketch gives you a strict bound on memory use, but is limited to absolute quantile error. (i.e. 99.99%-ile is between 99.9%-ile and 100%-ile. This is useless for extrema, but fine for medians)

Cormode's extension to KL-sketch gives you strict bound on relative accuracy, but n log n memory use.

Exponential histograms give you strict bounds on memory use, no allocation and strict bounds on relative error in measurement space (i.e. 99.99%-ile ± % error). See the log-histogram[1] for some simple code and hdrHistogram[2] for a widely used version. Variants of this are used in Prometheus.

The exponential histogram is, by far, the best choice in most practical situations since an answer that says 3.1 ± 0.2 seconds is just so much more understandable for humans than a bound on quantile error. I say this as the author of the t-digest.

[1] https://github.com/tdunning/t-digest/blob/main/core/src/main...

[2] https://hdrhistogram.org/

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

#167

Post by ted_dunning »

ssfrr wrote: post #99
sevensor wrote: post #20

Earlier quoted context omitted.

I’ve definitely had situations where a streaming quantile algorithm would have been useful, do you have any references?

Here's a simple one I've used before. It's a variation on FAME (Fast Algorithm for Median Estimation) [1]. You keep an estimate for the current quantile value, and then for each element in your stream, you either increment (if the element is greater than your estimate) or decrement (if the element is less than your estimate) by fixed "up -step" and "down-step" amounts. If your increment and decrement steps are equal,…

The state of the art has moved well beyond these algorithms. See these

https://github.com/tdunning/t-digest https://www.sciencedirect.com/science/article/pii/S266596382... https://arxiv.org/pdf/2102.09299

And, as I mentioned else-thread, exponential histograms are the best choice in almost all practical situations.

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

#168

Post by ted_dunning »

jagged-chisel wrote: post #23
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…

> … I didn’t realize the interview task was to re-implement someone’s PhD thesis in 30 minutes... What a bullshit task. I’m beginning to think this kind of interviewing should be banned. Seems to me it’s just an easy escape hatch for the interviewer/hiring manager when they want to discriminate based on prejudice.

Banning stupid interview questions is a bad idea for job applicants since they are such a good indication of bullshit job culture.

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

#169

Post by ted_dunning »

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…

That's a bullshit question.

My own response would have been a variant on radix-sort. Keep an array of 256 counters, and make a pass counting all of the high bytes. Now you know the high byte of the median. Make another pass keeping a histogram of the second byte of all values that match the high byte. And so on.

This takes four passes and requires 256 x 8 byte counters plus incidentals.

In a single pass you can't get the exact answer.

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

#170

Post by jagged-chisel »

KMag wrote: post #164
mnw21cam wrote: post #147

Earlier quoted context omitted.

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.

I used to ask how to find the 10th percentile value from an arbitrarily ordered list as an interview question. Most candidates suggested sorting, and then I'd ask if they could do better. If they got stuck, I'd ask them which sorting algorithm they'd suggest. If they suggested quicksort, then I could gently guide them down optimizing quicksort to quickselect. Most candidates made the mistake of believing getting rid…

ETA: You said "used to" and I didn't acknowledge that. This is targeted at that kind of interview, not you directly.

---

Had some "lucky" candidate stumbled upon an optimization you had never seen before, would you recognize it? If so, would you be honest and let them keep their discovery? After all, this isn't work for hire ...

Moving on. Did these interviews reflect the day-to-day work these software engineers would be performing if they were accepted? I guarantee your business isn't going to recoup millions of dollars because someone, in their day-to-day, hit on an optimation of an existing algorithm. Nor is it likely they'll be discovering wonderful new money-saving algorithms for your business.

If you're a pure research lab, employing PhD candidates and PhDs, maybe this kind of interview does indicate the required skills.

Post reply on HN