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

81–90 of 189 posts

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

#81

Post by someplaceguy »

thrw2486776 wrote: post #76
someplaceguy wrote: post #69

Earlier quoted context omitted.

> 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 n In 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).

> In the article n was set to 5. All of those arrays (except maybe 1) have exactly 5 elements. There is no variance

No, the code was:

    # If there are
> and even if there was, it would be tiny, there is no point in talking about limits of 5-element sequences

So your point is: not all constants are created equal. Which circles all the way back to my original point that this argument is pretty funny :)

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

#82

Post by skrtskrt »

cosmic_quanta wrote: post #12
mgaunard wrote: post #7

You could also use one of the streaming algorithms which allow you to compute approximations for arbitrary quantiles without ever needing to store the whole data in memory.

That is cool if you can tolerate approximations. But the uncomfortable questions soon arise: Can I tolerate an approximate calculation? What assumptions about my data do I to determine an error bound? How to verify the validity of my assumptions on an ongoing basis? Personally I would gravitate towards the quickselect algorithm described in the OP until I was forced to consider a streaming median approximation method…

A use case for something like this, and not just for medians, is where you have a querying/investigation UI like Grafana or Datadog or whatever.

You write the query and the UI knows you're querying metric xyz_inflight_requests, it runs a preflight check to get the cardinality of that metric, and gives you a prompt: "xyz_inflight_requests is a high-cardinality metric, this query may take some time - consider using estimated_median instead of median".

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

#83

Post by nilslindemann »

robinhouston wrote: post #35
nilslindemann wrote: post #31

"ns" instead of "l" and "n" instead of "el" would have been my choice (seen in Haskell code).

The trouble with using this convention (which I also like) in Python code is that sooner or later one wants to name a pair of lists 'as' and 'bs', which then causes a syntax error because 'as' is a keyword in Python. There is a similar problem with 'is' and 'js'.

Sure, naming is hard, but avoid "l", "I", "O", "o".

Very short variable names (including "ns" and "n") are always some kind of disturbance when reading code, especially when the variable lasts longer than one screen of code – one has to memorize the meaning. They sometimes have a point, e.g. in mathematical code like this one. But variables like "l" and "O" are bad for a further reason, as they can not easily be distinguished from the numbers. See also the Python style guide: https://peps.python.org/pep-0008/#names-to-avoid

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

#84

Post by osti »

Xcelerate wrote: post #13
anonymoushn wrote: post #11

Earlier quoted context omitted.

Do you mean topK rather than median, for K small? You certainly cannot build a heap with trillions of items in it.

No, I mean median. Here is an article describing a very similar problem since I can’t link to the leetcode version: https://www.geeksforgeeks.org/median-of-stream-of-running-in...

I'm wondering what heap approach can solve that problem, as I can't think of any. Hopefully OP got a link to the thesis.

The n log n approach definitely works though.

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

#85

Post by fenomas »

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…

Big-O analysis is about scaling behavior - its real-world implications lie in what it tells you about relative sizes, not absolute sizes.

E.g., if you need to run a task on 10M inputs, then knowing that your algorithm is O(N) doesn't tell you anything at all about how long your task will take. It also doesn't tell you whether that algorithm will be faster than some other algorithm that's O(N^2).

But it does tell you that if your task size doubles to 20M inputs, you can expect the time required for the first algorithm to double, and the second to quadruple. And that knowledge isn't arcane or theoretical, it works on real-world hardware and is really useful for modeling how your code will run as inputs scale up.

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

#86

Post by pfdietz »

creata wrote: post #39
Xcelerate wrote: post #19

Earlier quoted context omitted.

Yeah, I thought of that actually, but the interviewer said “very little memory” at one point which gave me the impression that perhaps I only had some registers available to work with. Was this an algorithm for an embedded system? The whole problem was kind of miscommunicated, because the interviewer showed up 10 minutes late, picked a problem from a list, and the requirements for the problem were only revealed when…

With 256 counters, you could use the same approach with four passes: pass i bins the numbers by byte i (0 = most sig., 3 = least sig.) and then identifies the bin that contains the median. I really want to know what a one-pass, low-memory solution looks like, lol.

Perhaps the interviewer was looking for an argument that no such solution can exist? The counterargument would look like this: divide the N numbers into two halves, each N/2 numbers. Now, suppose you don't have enough memory to represent the first N/2 numbers (ignoring changes in ordering); in that case, two different bags of numbers will have the same representation in memory. One can now construct a second half of numbers for which the algorithm will get the wrong answer for at least one of the two colliding cases.

This is assuming a deterministic algorithm; maybe a random algorithm could work with high probability and less memory?

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

#88

Post by throwaway294531 »

If you're selecting the n:th element, where n is very small (or large), using median-of-medians may not be the best choice.

Instead, you can use a biased pivot as in [1] or something I call "j:th of k:th". Floyd-Rivest can also speed things up. I have a hobby project that gets 1.2-2.0x throughput when compared to a well implemented quickselect, see: https://github.com/koskinev/turboselect

If anyone has pointers to fast generic & in-place selection algorithms, I'm interested.

[1] https://doi.org/10.4230/LIPIcs.SEA.2017.24

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

#89

Post by runeblaze »

someplaceguy wrote: post #53

return l[len(l) / 2] I'm not a Python expert, but doesn't the `/` operator return a float in Python? Why would you use a float as an array index instead of doing integer division (with `//`)? I know this probably won't matter until you have extremely large arrays, but this is still quite a code smell. Perhaps this could be forgiven if you're a Python novice and hadn't realized that the two different operators exist,…

I do agree that it is a code smell. However given that this is an algorithms article I don't think it is exactly that fair to judge it based on code quality. I think of it as: instead of writing it in pseudocode the author chose a real pseudocode-like programming language, and it (presumably) runs well for illustrative purposes.
Post reply on HN