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

71–80 of 189 posts

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

#71

Post by raincole »

someplaceguy wrote: post #60

I found this part of the code quite funny: # If there are Hell, why not just use 2^140 instead of 5 as the cut-off point, then? This way you'd have constant time median finding for all arrays that can be represented in any real-world computer! :) [1] [1] According to https://hbfs.wordpress.com/2009/02/10/to-boil-the-oceans/

Big-O notation and "real-world computer" don't belong to the same sentence. The whole point of big-O notation is to abstract the algorithm out of real-world limitations so we can talk about arbitrarily large input.

Any halting program that runs on a real world computer is O(1), by definition.

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

#72

Post by danlark »

SkiFire13 wrote: post #59

I wonder what's the reason of picking groups of 5 elements instead of 2 or 8.

3 and 4 elements will fail to prove the complexity is linear

You still can do 3 or 4 but with slight modifications

https://arxiv.org/abs/1409.3600

For example, for 4 elements, it's advised to take lower median for the first half and upper median for the second half. Then the complexity will be linear

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

#74

Post by contravariant »

anonymoushn wrote: post #32
contravariant wrote: post #4

Earlier quoted context omitted.

It should also be noted that radix sort is ridiculously fast because it just scans linearly through the list each time. It's actually hard to come up with something that cannot be sorted lexicographically. The best example I was able to find was big fractions. Though even then you could write them as continued fractions and sort those lexicographically (would be a bit trickier than strings).

Sorting fractions by numerical value is a good example. Previously I've heard that there are some standard collation schemes for some human languages that resist radix sort, but when I asked about which ones in specific I didn't hear back :(

The Unicode Collation algorithm doesn't look fun to implement in radix sort, but not entirely impossible either. They do note that some characters are contextual, an example they give is that CH can be treated as a single character that sorts after C (so also after CZ). Technically that is still lexicographical, but not byte-for-byte.

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

#75

Post by someplaceguy »

raincole wrote: post #71
someplaceguy wrote: post #60

I found this part of the code quite funny: # If there are Hell, why not just use 2^140 instead of 5 as the cut-off point, then? This way you'd have constant time median finding for all arrays that can be represented in any real-world computer! :) [1] [1] According to https://hbfs.wordpress.com/2009/02/10/to-boil-the-oceans/

Big-O notation and "real-world computer" don't belong to the same sentence. The whole point of big-O notation is to abstract the algorithm out of real-world limitations so we can talk about arbitrarily large input. Any halting program that runs on a real world computer is O(1), by definition.

> The whole point of big-O notation is to abstract the algorithm out of real-world limitations so we can talk about arbitrarily large input.

Except that there is no such thing as "arbitrarily large storage", as my link in the parent comment explained: https://hbfs.wordpress.com/2009/02/10/to-boil-the-oceans/

So why would you want to talk about arbitrarily large input (where the input is an array that is stored in memory)?

As I understood, this big-O notation is intended to have some real-world usefulness, is it not? Care to elaborate what that usefulness is, exactly? Or is it just a purely fictional notion in the realm of ideas with no real-world application?

And if so, why bother studying it at all, except as a mathematical curiosity written in some mathematical pseudo-code rather than a programming or engineering challenge written in a real-world programming language?

Edit: s/pretending/intended/

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

#76

Post by thrw2486776 »

someplaceguy wrote: post #69
SkiFire13 wrote: post #62

Earlier quoted context omitted.

Ultimately when an algorithm has worse complexity than another it might still be faster up to a certain point. In this case 5 is likely under that point, though I doubt 2^256 will. In practice you might also want to use a O(n^2) algorithm like insertion sort under some threshold.

> Ultimately when an algorithm has worse complexity than another it might still be faster up to a certain point. Sure, but the author didn't argue that the simpler algorithm would be faster for 5 items, which would indeed make sense. Instead, the author argued that it's OK to use the simpler algorithm for less than 5 items because 5 is a constant and therefore the simpler algorithm runs in constant time, hence my poi…

If you set n=2^140, then sure, it’s constant. If instead you only have nIn the article n was set to 5. All of those arrays (except maybe 1) have exactly 5 elements. There is no variance (and even if there was, it would be tiny, there is no point in talking about limits of 5-element sequences).

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

#77

Post by dataflow »

anonymoushn wrote: post #55
dataflow wrote: post #51

Earlier quoted context omitted.

Oh I see. I've found LSD better in some cases, but maybe it's just my implementation. For MSD, do you get a performance hit from putting your stack on the heap (to avoid overflow on recursion)? I don't just mean the minor register vs. memory differences in the codegen, but also the cache misses & memory pressure due to potentially long input elements (and thus correspondingly large stack to manage). > Some cutting-ed…

> 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!

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

#78

Post by Sharlin »

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’s unambiguously O(n), there’s no lg n anywhere to be seen. It may be O(n) with a bit larger constant factor, but the whole point of big-O analysis is that those don’t matter.

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

#80

Post by raincole »

someplaceguy wrote: post #75
raincole wrote: post #71

Earlier quoted context omitted.

Big-O notation and "real-world computer" don't belong to the same sentence. The whole point of big-O notation is to abstract the algorithm out of real-world limitations so we can talk about arbitrarily large input. Any halting program that runs on a real world computer is O(1), by definition.

> The whole point of big-O notation is to abstract the algorithm out of real-world limitations so we can talk about arbitrarily large input. Except that there is no such thing as "arbitrarily large storage", as my link in the parent comment explained: https://hbfs.wordpress.com/2009/02/10/to-boil-the-oceans/ So why would you want to talk about arbitrarily large input (where the input is an array that is stored in mem…

> (where the input is an array that is stored in memory)?

If the input is an array that is stored in a piece of real-world memory, then the only possible complexity is O(1). It's just how big-O works. Big-O notation is an abstraction that is much much closer to mathematics than to engineering.

> this big-O notation is pretending to have some real-world usefulness...

Big-O notation is not a person so I'm not sure whether it can pretend something. CS professors might exaggerate big-O notation's real-world usefulness so their students don't fall asleep too fast.

> fictional

Theoretical. Just like the other theoretical ideas, at best big-O notation gives some vague insights that help people solve real problems. It gives a very rough feeling about whether an algorithm is fast or not.

By the way, Turing machine is in this category as well.

Post reply on HN