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

21–30 of 189 posts

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

#21

Post by Aardwolf »

anonymoushn wrote: post #8
exDM69 wrote: post #5

Earlier quoted context omitted.

Problem with radix sorting strings is that it is O(k*N) where k is length of key, in this case it's the second longest string's length. Additional problems arise if you are dealing with null terminated strings and do not have the length stored. Radix sort is awesome if k is small, N is huge and/or you are using a GPU. On a CPU, comparison based sorting is faster in most cases.

No, it's O(N+M) where N is the number of strings and M is the sum of the lengths of the strings. Maybe your radix sort has some problems? I evaluated various sorts for strings as part of my winning submission to https://easyperf.net/blog/2022/05/28/Performance-analysis-an... and found https://github.com/bingmann/parallel-string-sorting to be helpful. For a single core, the fastest implementation among those in parall…

> No, it's O(N+M) where N is the number of strings and M is the sum of the lengths of the strings.

That would mean it's possible to sort N random 64-bit integers in O(N+M) which is just O(N) with a constant factor of 9 (if taking the length in bytes) or 65 (if taking the length in bits), so sort billions of random integers in linear time, is that truly right?

EDIT: I think it does make sense, M is length*N, and in scenarios where this matters this length will be in the order of log(N) anyway so it's still NlogN-sh.

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

#22

Post by fzy95 »

sevensor wrote: post #20
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.

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

"Further analysis of the remedian algorithm" https://www.sciencedirect.com/science/article/pii/S030439751...

This one has a streaming variant.

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

#23

Post by jagged-chisel »

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.

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

#24

Post by Tarean »

Love this algorithm. It feels like magic, and then it feels obvious and basically like binary search.

Similar to the algorithm to parallelize the merge step of merge sort. Split the two sorted sequences into four sequences so that `merge(left[0:leftSplit], right[0:rightSplit])+merge(left[leftSplit:], right[rightSplit:])` is sorted. leftSplit+rightSplit should be halve the total length, and the elements in the left partition must be Seems impossible, and then you think about it and it's just binary search.

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

#25

Post by jagged-chisel »

Xcelerate wrote: post #19
pfdietz wrote: post #16

Earlier quoted context omitted.

You don't need to load trillions of numbers into memory, you just need to count how many of each number there are. This requires 2^32 words of memory, not trillions of words. After doing that just scan down the array of counts, summing, until you find the midpoint.

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…

That “miscommunication” you mention has been used against me in several interviews, because I was expected to ask questions (and sometimes a specific question they had in mind) before making assumptions. Well, then the 30min becomes an exercise in requirements gathering and not algorithmic implementation.

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

#26

Post by Tarean »

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

But that stores all elements into memory?

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

#27

Post by anonymoushn »

Aardwolf wrote: post #21
anonymoushn wrote: post #8

Earlier quoted context omitted.

No, it's O(N+M) where N is the number of strings and M is the sum of the lengths of the strings. Maybe your radix sort has some problems? I evaluated various sorts for strings as part of my winning submission to https://easyperf.net/blog/2022/05/28/Performance-analysis-an... and found https://github.com/bingmann/parallel-string-sorting to be helpful. For a single core, the fastest implementation among those in parall…

> No, it's O(N+M) where N is the number of strings and M is the sum of the lengths of the strings. That would mean it's possible to sort N random 64-bit integers in O(N+M) which is just O(N) with a constant factor of 9 (if taking the length in bytes) or 65 (if taking the length in bits), so sort billions of random integers in linear time, is that truly right? EDIT: I think it does make sense, M is length*N, and in sc…

> That would mean it's possible to sort N random 64-bit integers in O(N+M) which is just O(N) with a constant factor of 9 (if taking the length in bytes) or 65 (if taking the length in bits), so sort billions of random integers in linear time, is that truly right?

Yes. You can sort just about anything in linear time.

> EDIT: I think it does make sense, M is length*N, and in scenarios where this matters this length will be in the order of log(N) anyway so it's still NlogN-sh.

I mainly wrote N+M rather than M to be pedantically correct for degenerate inputs that consist of mostly empty strings. Regardless, if you consider the size of the whole input, it's linear in that.

Post reply on HN