News for hackers. Stuff that matters.
Re:My Favorite Algorithm: Linear Time Median Finding by anonymoushn on Thursday July 25, 2024 @07:00AM (#41067125)
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 parallel-string-sorting was a radix sort, so my submission included a radix sort based on that one.

The only other contender was multi-key quicksort, which is notably not a comparison sort (i.e. a general-purpose string comparison function is not used as a subroutine of multi-key quicksort). In either case, you end up operating on something like an array of structs containing a pointer to the string, an integer offset into the string, and a few cached bytes from the string, and in either case I don't really know what problems you expect to have if you're dealing with null-terminated strings.

A very similar similar radix sort is included in https://github.com/alichraghi/zort which includes some benchmarks, but I haven't done the work to have it work on strings or arbitrary structs.

Re:My Favorite Algorithm: Linear Time Median Finding by Aardwolf on Thursday July 25, 2024 @08:06AM (#41067642)
> 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?

Re:My Favorite Algorithm: Linear Time Median Finding by anonymoushn on Thursday July 25, 2024 @08:26AM (#41067824)
> 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.

Re:My Favorite Algorithm: Linear Time Median Finding by exDM69 on Thursday July 25, 2024 @09:09AM (#41068256)
Yes, radix sort can sort integers in linear O(N) time.
Re:My Favorite Algorithm: Linear Time Median Finding by dataflow on Thursday July 25, 2024 @09:25AM (#41068430)
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 by anonymoushn on Thursday July 25, 2024 @09:32AM (#41068495)
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 by dataflow on Thursday July 25, 2024 @09:52AM (#41068702)
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-edge radix sorts

Where do you find these? :-)

Re:My Favorite Algorithm: Linear Time Median Finding by anonymoushn on Thursday July 25, 2024 @10:08AM (#41068853)
> 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 way. Oops!

> cache misses & memory pressure due to potentially long input elements (and thus correspondingly large stack)

I think this should be okay? The best of these sorts try to visit the actual strings infrequently. You'd achieve worst-case cache performance by passing a pretty large number of strings with a long, equal prefix. Ideally these strings would share the bottom ~16 bits of their address, so that they could evict each other from cache when you access them. See https://danluu.com/3c-conflict/

> Where do you find these? :-)

There's a list of cool sorts here https://github.com/scandum/quadsort?tab=readme-ov-file#varia... and they are often submitted to HN.

Re:My Favorite Algorithm: Linear Time Median Finding by dataflow on Thursday July 25, 2024 @11:08AM (#41069574)
Yeah, what I hate about MSD is the stack explosion.

Otherwise - cool, thanks!

Re:My Favorite Algorithm: Linear Time Median Finding by Cleonis on Friday July 26, 2024 @06:55AM (#41077564)
Hi, I want to respond to a post from you from 2019. (That 2019 thread no longer offers the reply button, otherwise I would reply there of course.) I apologize for using this thread to get my message in.

This is the item I want to respond to: https://news.ycombinator.com/item?id=19768492 When you took a Classical Mechanics course you were puzzled by the form of the Lagrangian: L = T - V

I have created a resource for the purpose of making application of calculus of variations in mechanics transparent. As part of that the form of the Lagrangian L=T-V is explained.

http://cleonis.nl/physics/phys256/calculus_variations.php

http://cleonis.nl/physics/phys256/energy_position_equation.p...

I recognize the 'you are certainly entitled to ask why' quote, it's from the book 'Classical Mechanics' by John Taylor.

Here's the thing: there is a good answer to the 'why' question. Once you know that answer things become transparent, and any wall is gone.

Re:My Favorite Algorithm: Linear Time Median Finding by dataflow on Friday July 26, 2024 @09:19AM (#41078409)
Haha wow, this was definitely random. Thank you for letting me know, I'll take a look when I have the chance.
Re:My Favorite Algorithm: Linear Time Median Finding by Cleonis on Friday July 26, 2024 @12:30PM (#41079945)
If I don't hear back in a week or so I will remind you, I hope that's OK with you.

I'm aware your expectations may be low. Your thinking may be: if textbook authors such as John Taylor don't know the why, then why would some random dude know?

The thing is: this is the age of search machines on the internet; it's mindblowing how searcheable information is. I've combed, I got to put pieces of information together that hadn't been put together before, and things started rolling.

I'm stoked; that's why I'm reaching out to people.

I came across the ycombinator thread following up something that Jess Riedel had written.

Re:My Favorite Algorithm: Linear Time Median Finding by dataflow on Friday July 26, 2024 @06:12PM (#41082784)
Some feedback (apologies in advance for it being negative):

- I mean this kindly, but this is getting a tad bit aggressive. Please let me glance at my own pace (or not glance, if I don't find the interest to), rather than periodically following up with me around the forum to make sure I look at what you wrote. I was much more interested in this problem at the time I came across it than I was in 2019, and I was similarly more interested in 2019 than I am now. During this time I have both (a) come across other explanations that I've found ~semi-satisfactory, and (b) gathered other things to occupy my brain with. While I do get some enjoyment from the topic, refreshing my understanding of analytical mechanics is really not my topmost interest or priority right now. It could easily be months or years before I become interested in the problem again to even think about it.

- I find it rather... jarring to see a sentence like "Summing bars of signed area, in the limit of subdividing into infinitely many bars: that is evaluating the integral" in the middle of an explanation about Lagrangians and the principle of stationary action. Yes... integration is the limit of addition; you should hope your reader knows that well by now. You wouldn't re-teach "multiplication is really just repeated addition" in the middle of a lecture about Fourier series; this feels equally out-of-place. Not only does it make it seem like you don't know your audience, it also wastes the reader's time, and makes it hard for them to find any gems you might have shared.

- I took a quick look at your site and I don't actually see you attempt to explain the rationale for why the quantity of interest is T - V (as opposed to, say, T + V) anywhere. You mention "you are looking for the sweet spot: the point where as the object is moving the rate of change of kinetic energy matches the rate of change of potential energy", but... am I? Really? I certainly wasn't looking for that, nor have any idea why you thought I would be looking for that. It almost seems to assume what you were trying to prove!

Re:My Favorite Algorithm: Linear Time Median Finding by Cleonis on Saturday July 27, 2024 @01:58PM (#41088244)
Thank you for taking the time to have a look.

About the presentation: I think I agree: once I'm up to the level of discussing Lagrangians and stationary action I should not re-teach integration; the reader will be familiar with that.

That particular presentation grew over time; I agree it is uneven. I need to scrap a lot of it.

The preceding article http://cleonis.nl/physics/phys256/calculus_variations.php Is more an overarching concept.

Also, I'm active on the stackexchange physics forum. Over the years: Hamilton's stationary action is a recurring question subject. Some weeks ago I went back to the first time a stationary action question was posted, submitting an answer. In that answer: I aimed to work the exposition down to a minimum, presenting a continuous arch. https://physics.stackexchange.com/a/821469/17198

three sections:

1. Work-Energy theorem

2. The central equation of the work 'Mécanique Analytique' by Joseph Louis Lagrange (I discuss _why_ that equation obtains.)

3. Hamilton's stationary action

It's a tricky situation. I'm not assuming the thing I present derivation of, but I can see how it may appear that way.