Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

Instead of repeating yourself, can you link to some actual information?

still will win no matter how measure speed

Speed is measured with time. You can keep saying algorithmic complexity is speed, but that will never make it reality.

If you want to argue against heap sort, then you need to argue

That's not how it works. Other sorts take a fraction of the time. I showed you this already.

I'll let someone else calculate the big-O expressions again considering locality of reference, etc.

This was never about algorithmic complexity, that's something that you hallucinated. Not only that, but you do realize that other sorts have the same complexity as heap sort right? There a lot of ways to sort with n log n.

You are trying to argue something that isn't real to make a point that no one cares about and has nothing to do with this thread.

"in general" is not very specific.

The main issue is the big-O expression. Again, if win in the big-O expression, then, in the assumptions of the context, for sorting n keys for all sufficiently large n will win.

Sure, maybe the heap sort O( n log(n) ) is wrong. In that case, maybe could beat heap sort.

How could O( n log(n) ) be wrong? Well for large enough n, could encounter virtual memory paging that would make the cost of a comparison grow with n and an algorithm that had better locality of reference and less paging might win. So, for such a context, would have to redo the big-O derivation.

Merge sort is based on comparing keys two at a time, and that was the assumption in Gleason's argument. So, Gleason's argument should also apply to merge sort. Some people prefer heap sort or quick sort because they are in place and merge sort is not.

I wrote and you quoted:

It is this point that has much of the academic computer science community saying that no sorting algorithm based on comparing keys two at a time can beat heap sort.

> I think you're the only one saying that.

Also Gleason, Knuth, and much of the academic computer science community.

> Where did you get this idea? I just showed you a quicksort being 10 times faster than a heap sort.

Your "10 times" is not for all values of number of keys n. The crucial issue is the big-O expression, and your "10 times" says next to nothing about the big-O expression.

Again, the big-O expression is crucial because winning in the big-O expression means winning for all sufficiently large n, and that is, sadly, the only really meaningful means we have of comparing "in general" two pieces of code.

Instead, sure, if in a particular application have an upper bound on n, say, always less than 10,000,000, then use the code that is fastest from 1 to 10,000,000 or in expectation on the probability distribution of n from 1 to 10,000,000 in the particular application. Or, maybe in some application don't care about the average execution time but definitely always want execution time faster than some given T milliseconds for all n from 1 to 10,000,000. Okay, pick the code that best achieves this.

Gleason's work didn't cure cancer, exceed the speed of light, say what is in the center of a black hole, say what happened before the big bang or will happen after the heat death of the universe, .... Instead, Gleason stated and proved a theorem in applied math. The theorem shows what is the best possible given the assumptions. Similarly for what Knuth said about heap sort and Gleason's theorem. A lot of progress in pure/applied math and science is like that -- not everything but just a specific result given some specific assumptions.

Or, assume that Joe has a new computer, 1000 cores, 10 GHz clock, 500 GB first level cache, and writes some really careful code in assembler that makes full use of the 1000 processors, to sort 10 billion 32 bit numbers via bubble sort. Then it runs in O(n^2), that is, for some constant k_Joe runs in

k_Joe n^2 = k_Joe (10^10)^2

milliseconds.

Along comes Bill with a PC based on a 64 bit single core processor with a 2 GHz clock. Bill's code uses heap sort. Then Bill's code runs in O( n log(n) ) or for some constant k_Bill runs in

k_Bill (n log(n) ) =

k_Bill (10^10 log(10^10) )

milliseconds.

And Bill is a bit sloppy and uses an interpretive language so the constant k_Bill is large.

Then the ratio of running times is

(k_Joe / k_Bill) (n / log(n) )

Well, assume for simplicity and without loss of generality that the log has base 10. Then

log(n) = log(10^10) = 10

so that

n / (log(n)) = 10^10 / 10

= 1,000,000,000

Well, let's account for Joe's 1000 cores to get a ratio of 1,000,000 and Joe's 5 times faster clock speed to get 200,000. Say the interpretative language Bill used is 10 times slower than compiled C for a ratio of

20,000

and say that Joe's hand coding in assembler is 2 times faster than C code for a ratio of

10,000.

So, still Bill's code runs

10,000

times faster than Joe's.

That's an example of, the algorithm that wins in big-O wins for all sufficiently large n, even considering coding in assembler with 1000 cores and a 10 GHz clock.

Sure, for n = 100, maybe Joe's code wins -- I'll let you find the ratio.

That's what the computer science community noticed some decades ago and, thus, settled on big-O as the way to compare algorithms and code. Again, heap sort meets the Gleason bound in worst case. Since in the context the Gleason bound says that O( n log(n) ) is the best can do, the best quick sort can do is tie. And if the quick sort code does not make the partitions carefully, quick sort won't be O( n log(n) ) in worst case and for sufficiently large n will lose by whatever ratio want, 1,000,000:1 if you want.

Look, guys, all this is just from, say, the first week of a ugrad course in computer science.

Arguing with the Gleason bound -- about like arguing with the Pythagorean theorem.

Don't argue with me. Instead, send a question to a comp/sci prof at your local university giving him the URL of this post.

Note that the proposed ML (micro-)algorithms rely heavily on the fact that they are sorting 32-bit or 64-bit integers because they are using conditional moves. A conditional move avoids a branch by converting the instruction to a no-op when the condition doesn't hold. This is fine when moving 4 or 8 bytes because it can be done in a single clock cycle, but you can't apply the same technique when sorting larger objects.

[1] https://dl.acm.org/doi/pdf/10.1145/225058.225173

In a word, you are wrong.

I've been very, very, very clear again, over again, once again, yet again, and you just fail to get it, a simple lesson often just in the first week of an easy, first college course in computer science.

> Other sorts take a fraction of the time. I showed you this already.

Nope. You showed no such thing. Your evidence is meaningless. Heck, even bubble sort could beat heap sort or quick sort under some circumstances.

So, again, sit down, pay attention, listen up: What matters for any measurement of performance in comparing code is the big-O expression. Read this again, again, again, write it on the blackboard 1000 times after school, repeat it to yourself before each meal, going to sleep, waking up. You just pass this off as computational complexity irrelevant to execution time. Here you are just wrong, totally, badly wrong. You seem not to understand this. For any measurement, time, Watts, Joules, comparisons, cycles, any measurement, in the reasonable context, what matters is the big-O expression.

> There a lot of ways to sort with n log n.

Well, merge sort can. Maybe some versions of quick sort can. Okay, there are some ties. I never said there are no ties. But, in the context, can't beat O( n log(n) ) -- the Gleason bound shows this. I've said this over and over and over and over. So, in the context, can't beat heap sort. What you saw in some two pieces of code on 1000 keys is just irrelevant to a meaningful comparison of performance.

> The Gleason bound?

> Instead of repeating yourself, can you link to some actual information?

I gave the information: First in the context heap sort, merge sort, maybe quick sort run in O( n log(n) ) in comparisons and also, in this context, inescapably, in time, cycles, Watts, Joules, whatever. The "faster" is not for n = 1000 but for all sufficiently large n. For n = 1000, anything can happen. Second the Gleason bound says that, in the context, can't sort faster than this. So that's why it's call a "bound", a lower bound on how fast can sort. Third, I gave the reference, D. Knuth's famous book.

The Gleason bound is one of the nicer, most powerful, most useful, most important pieces of work in all of computer science, computer programming, sorting, and computing for any and all purposes, in particular for practical performance, and you just fail to get it.

You have some problems, some blocks in understanding. You just do not want to learn something new to you. You deeply resent this. Your problem is not about computers or applied math but emotional. For your emotional problems, nothing in computing, computer science, or my writing can help you.