"ns" instead of "l" and "n" instead of "el" would have been my choice (seen in Haskell code).
My Favorite Algorithm: Linear Time Median Finding (2018)
31–40 of 189 posts
Re: My Favorite Algorithm: Linear Time Median Finding (2018)
#32One commonly sees the implication that radix sort cannot be used for data types other than integers, or for composite data types, or for large data types. For example, TFA says you could use radix sort if your input is 32-bit integers. But you can use it on anything. You can use radix sort to sort strings in O(n) time.
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 :(
Re: My Favorite Algorithm: Linear Time Median Finding (2018)
#33Around 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...
Re: My Favorite Algorithm: Linear Time Median Finding (2018)
#34Another nice one is O(1) weighted sampling (after O(n) preprocessing).
Re: My Favorite Algorithm: Linear Time Median Finding (2018)
#35"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'.
Re: My Favorite Algorithm: Linear Time Median Finding (2018)
#36Earlier quoted context omitted.
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.
Thanks!!
Re: My Favorite Algorithm: Linear Time Median Finding (2018)
#37Earlier 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…
Yes, radix sort can sort integers in linear O(N) time.
Re: My Favorite Algorithm: Linear Time Median Finding (2018)
#38FTA:
“Proof of Average O(n)
On average, the pivot will split the list into 2 approximately equal-sized pieces. Therefore, each subsequent recursion operates on 1⁄2 the data of the previous step.”
That “therefore” doesn’t follow, so this is more an intuition than a proof. The problem with it is that the medium is more likely to end up in the larger of the two pieces, so you more likely have to recurse on the larger part than on the smaller part.
What saves you is that O(n) doesn’t say anything about constants.
Also, I would think you can improve things a bit for real world data by, on subsequent iterations, using the average of the set as pivot (You can compute that for both pieces on the fly while doing the splitting. The average may not be in the set of items, but that doesn’t matter for this algorithm). Is that true?
Re: My Favorite Algorithm: Linear Time Median Finding (2018)
#39Earlier 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…
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.
Re: My Favorite Algorithm: Linear Time Median Finding (2018)
#40You 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?
There are two kinds:
- quantile sketches, such as t-digest, which aim to control the quantile error or rank error. Apache DataSketches has several examples, https://datasketches.apache.org/docs/Quantiles/QuantilesOver...
- histograms, such as my hg64, or hdr histograms, or ddsketch. These control the value error, and are generally easier to understand and faster than quantile sketches. https://dotat.at/@/2022-10-12-histogram.html