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

181–189 of 189 posts

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

#181

Post by beyondCritics »

melonmouse wrote: post #180

The linked proof for that median of medians is O(n) feels counterintuitive to me. Here's a (simpler?) alternative. T(0) = 0 T(1) = 1 T(n) = n + T(n/5) + T(7/10*n) We want to prove that: T(n) ≤ C*n It is intuitive that T(a+b) ≥ T(a) + T(b), or in other words, T is superadditive. That can be shown by induction: Induction base: it holds for all a+b T(0+0) = 0 + T(0) + T(0) ≥ T(0) + T(0) Induction step: suppose it holds…

I like the idea to use super additivity, but in a proof you cannot creatively extend T to the reals, this should be fixed.

Here is the slightly mopped up proof i had in mind, when i posted my hints below:

  Let be r>=1 and 0 1 for all 1  0 and
  T(0) := 0
  T(n) := c \* n + T(floor(n/a(1))) + ... + T(floor(n/a(r)))

  Then T(n)  0 !
  Proof by induction: 
  "n=0" : 
   The statement holds trivially.

  "k->n": 
   Let n>=1 and assume the statement holds for all 01 we have floor(n/a(i))

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

#182

Post by davidmurdoch »

neonsunset wrote: post #161
davidmurdoch wrote: post #156

Earlier quoted context omitted.

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.

I was thinking LINQ was optimized to do a single enumeration for cases such as this. Can LINQ be easily, naturally, and idiomatically used with `IEnumerable.Max` and `.Min` to avoid looping twice, or is it more of a more rigorous and intentional optimization the engineer would have to seek out?

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

#183

Post by klyrs »

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

Earlier quoted context omitted.

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.

I agreed with much of what you had to say up until this point. Well, and I'm not about 2-hour interviews either; that's too disruption to my work.

To me, a coding challenge is a conversation piece. I will see some skills like "can the candidate get a software project in their top-listed language on their cv running in less than an hour," and I do judge questions they ask or don't ask. But then, I don't just pull a leetcode challenge from the shelf. My favorite "coding challenge" isn't actually that challenging (which can send leetcode-grinders spiraling); it's about the journey and not the destination.

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

#184

Post by forrestthewoods »

kccqzy wrote: post #100
forrestthewoods wrote: post #98

Earlier quoted context omitted.

> I don't agree with the need for this guarantee. You don’t get to agree with it or not. It depends on the project! Clearly there exist some projects in the world where it’s important. But honestly it doesn’t matter. Because as the article shows with random data that median-of-medians is strictly better than random pivot. So even if you don’t need the requirement there is zero loss to achieve it.

The median-of-median comes at a cost for execution time. Chances are, sorting each five-element chunk is a lot slower than even running a sophisticated random number generator.

Did you read the article? Median-of-median results in fewer comparisons than random.

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

#185

Post by sroussey »

rented_mule wrote: post #140
sroussey wrote: post #130

Earlier quoted context omitted.

Actually, seeking the bias numbers can be quite illuminating.

You're absolutely right! Some learning that we came to later that isn't unrelated to what you're saying... don't just look at metrics (in the case I've described above, it was timings of operations in a large system), but look at histograms for them. You should be able to explain why they have the shape they do. The distributions are so often multimodal, and understanding the modes helps you understand a lot more nua…

Even some regular engineers with experience dealing with many servers will have built up an intuition to exploit.

In fact, this is often where decisions on what metrics to have in the first place come from. Ask why. You can go far without deep stats knowledge!

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

#186

Post by Cleonis »

dataflow wrote: post #173
Cleonis wrote: post #162

Earlier quoted context omitted.

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…

Some feedback (apologies in advance for it being negative): - I mean this kindly, but this is getting a tad bit aggressive. Please let me glance at my own pace (or not glance, if I don't find the interest to), rather than periodically following up with me around the forum to make sure I look at what you wrote. I was much more interested in this problem at the time I came across it than I was in 2019, and I was simila…

Thank you for taking the time to have a look.

About the presentation: I think I agree: once I'm up to the level of discussing Lagrangians and stationary action I should not re-teach integration; the reader will be familiar with that.

That particular presentation grew over time; I agree it is uneven. I need to scrap a lot of it.

The preceding article http://cleonis.nl/physics/phys256/calculus_variations.php Is more an overarching concept.

Also, I'm active on the stackexchange physics forum. Over the years: Hamilton's stationary action is a recurring question subject. Some weeks ago I went back to the first time a stationary action question was posted, submitting an answer. In that answer: I aimed to work the exposition down to a minimum, presenting a continuous arch. https://physics.stackexchange.com/a/821469/17198

three sections:

1. Work-Energy theorem

2. The central equation of the work 'Mécanique Analytique' by Joseph Louis Lagrange (I discuss _why_ that equation obtains.)

3. Hamilton's stationary action

It's a tricky situation. I'm not assuming the thing I present derivation of, but I can see how it may appear that way.

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

#187

Post by rhymer »

mjburgess wrote: post #146
rhymer wrote: post #133

Earlier quoted context omitted.

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 thousan…

Relevance: from the cited paper, the variance of the median estimator is proportional to 1/(n * f^2), where n is the sample size and f is the density at median.

Two observations: 1. With sufficiently large n, you can control your variance to an acceptable level. 2. The factor f is outside of your control. If your problem has a small density around the median, then you'll need to throw more samples to compensate for it.

I think your concern is about #2: you can always construct a pathological distribution to make the sampling-based approach unattainable. The paper provided guidance on what to expect when you apply the sampling-based approach.

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

#188

Post by srcreigh »

jiggawatts wrote: post #176
srcreigh wrote: post #160

Earlier quoted context omitted.

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

I think you meant 2N+2M vs 2N+M, but yes, that’s the point: not reading twice is cheaper because unlike in traditional big-O analysis compute is cheap but data access is very expensive.

Yep, thx.

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

#189

Post by hhmc »

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…

You also can use the fact that for any distribution, the median is never further than 1SD away from the mean.
Post reply on HN