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

41–50 of 189 posts

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

#41

Post by [deleted] »

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 :(

[deleted]

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

#42

Post by mabbo »

I learned about the median-of-medians quickselect algorithm when I was an undergrad and was really impressed by it. I implemented it, and it was terribly slow. It's runtime grew linearly, but that only really mattered if you had at least a few billion items in your list.

I was chatting about this with a grad student friend who casually said something like "Sure, it's slow, but what really matters is that it proves that it's possible to do selection of an unsorted list in O(n) time. At one point, we didn't know whether that was even possible. Now that we do, we know there might an even faster linear algorithm." Really got into the philosophy of what Computer Science is about in the first place.

The lesson was so simple yet so profound that I nearly applied to grad school because of it. I have no idea if they even recall the conversation, but it was a pivotal moment of my education.

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

#43

Post by dataflow »

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…

If you have a million 1-character strings and one string of length 1 million, how many steps would your LSD radix sort take? And (if it's indeed linear in the total input size like you say) how do you make it jump over the empty slots without losing real-world efficiency in other cases?

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

#44

Post by zelphirkalt »

You can simply pass once over the data, and while you do that, count occurrences of the elements, memorizing the last maximum. Whenever an element is counted, you check, if that count is now higher than the previous maximum. If it is, you memorize the element and its count as the maximum, of course. Very simple approach and linear in time, with minimal book keeping on the way (only the median element and the count (previous max)).

I don't find it surprising or special at all, that finding the median works in linear time, since even this ad-hoc thought of way is in linear time.

EDIT: Ah right, I mixed up mode and median. My bad.

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

#45

Post by jagged-chisel »

Xcelerate wrote: post #17
jiggawatts wrote: post #14

Earlier quoted context omitted.

I've heard of senior people applying for jobs like this simply turning the interview question around and demanding that the person asking it solve it in the allotted time. A surprisingly high percentage of the time they can't.

This company receives so many candidates that the interviewer would have just ended the call and moved on to the next candidate. I get the notion of making the point out of principle, but it’s sort of like arguing on the phone with someone at a call center—it’s better to just cut your losses quickly and move on to the next option in the current market.

And we, as software engineers, should also take that advice: it's better to just cut your losses quickly and move on to the next option in the current market.

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

#46

Post by gcr »

zelphirkalt wrote: post #44

You can simply pass once over the data, and while you do that, count occurrences of the elements, memorizing the last maximum. Whenever an element is counted, you check, if that count is now higher than the previous maximum. If it is, you memorize the element and its count as the maximum, of course. Very simple approach and linear in time, with minimal book keeping on the way (only the median element and the count (p…

This finds the mode (most common element), not the median.

Wouldn't you also need to keep track of all element counts with your approach? You can't keep the count of only the second-most-common element because you don't know what that is yet.

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

#47

Post by anonymoushn »

dataflow wrote: post #43
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…

If you have a million 1-character strings and one string of length 1 million, how many steps would your LSD radix sort take? And (if it's indeed linear in the total input size like you say) how do you make it jump over the empty slots without losing real-world efficiency in other cases?

It's MSB radix sort. I think LSB radix sort is not generally as useful because even for fixed-size inputs it often makes more passes over most of the input than MSB radix sort.

Your comment makes me think it would be swell to add a fast path for when the input range compares equal for the current byte or bytes though. In general radix sorts have some computation to spare (on commonly used CPUs, more computation may be performed per element during the histogramming pass without spending any additional time). Some cutting-edge radix sorts spend this spare computation to look for sorted subsequences, etc.

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

#48

Post by zelphirkalt »

mabbo wrote: post #42

I learned about the median-of-medians quickselect algorithm when I was an undergrad and was really impressed by it. I implemented it, and it was terribly slow. It's runtime grew linearly, but that only really mattered if you had at least a few billion items in your list. I was chatting about this with a grad student friend who casually said something like "Sure, it's slow, but what really matters is that it proves th…

Does the fact, that any linear time algorithm exist, indicate, that a faster linear time algorithm exists? Otherwise, what is the gain from that bit of knowledge? You could also think: "We already know, that some algorithm exists, there might be an even faster algorithm!" What makes the existence of an O(n) algo give more indication, than the existence of an O(n log(n)) algorithm?

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

#49

Post by cfors »

danlark wrote: post #33

Around 4 years ago I compared lots of different median algorithms and the article turned out to be much longer than I anticipated :) https://danlark.org/2020/11/11/miniselect-practical-and-gene...

Just wanted to say thank you for this article - I've read and shared this a few times over the years!

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

#50

Post by anonymoushn »

zelphirkalt wrote: post #48
mabbo wrote: post #42

I learned about the median-of-medians quickselect algorithm when I was an undergrad and was really impressed by it. I implemented it, and it was terribly slow. It's runtime grew linearly, but that only really mattered if you had at least a few billion items in your list. I was chatting about this with a grad student friend who casually said something like "Sure, it's slow, but what really matters is that it proves th…

Does the fact, that any linear time algorithm exist, indicate, that a faster linear time algorithm exists? Otherwise, what is the gain from that bit of knowledge? You could also think: "We already know, that some algorithm exists, there might be an even faster algorithm!" What makes the existence of an O(n) algo give more indication, than the existence of an O(n log(n)) algorithm?

If you had two problems, and a linear time solution was known to exist for only one of them, I think it would be reasonable to say that it's more likely that a practical linear time solution exists for that one than for the other one.
Post reply on HN