I really can't tell but it seems to be a continuation of this work if I read the To-Dos correctly, what do you think? Here it seems to be 1-bit on just the transformer, https://huggingface.co/shi3z/BitNetWikipedia110M
"AlphaDev uncovered new sorting algorithms that led to improvements in the LLVM libc++ sorting library that were up to 70% faster for shorter sequences and about 1.7% faster for sequences exceeding 250,000 elements."
If the thing you have to sort is within a known domain you can definitely beat o(n log(n)). Just expect crazy memory usage.
And that's only not the case in theory. But nobody owns a real Turing machine with infinite tape and truly infinite numbers. It doesn't exist in reality.
You can always divide time by multiplying space with the same factor.
by "general sort" your parent comment means "comparison sort", and the claim (which has been proved, see CLRS intro to algorithms) is that you cannot do it in better than O(n log n) comparisons.
any sort that only uses comparisons is provably not better than n log n. Hence whatever Thorup is, it doesn't work for arbitrary input, and must assume something further, something like "all elements under 1000 or something"
I think the parent's argument is that, since they only evaluated their algorithms on sorting arrays of 32-bit or 64-bit integers, it is fair game to compare against integer sorting algorithms for which we have better complexities than O(nlgn).
This seems like a very valid point for iopq's clarifying point in the context of what still might exist to be discovered in the set of theoretically possible new algorithms, though doesn't change that dheera set the bar much, much higher than most people would agree with.
but the number of elements in the array is also a 32 or 64 bit integer, so you still cannot do better than O(n log n) even with fancy radix sort or whatever
There are many such algorithms. For example, [1] is expected linear time, deterministic O(nlglgn) time and linear space.
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.
The Gleason bound is n log(n) and says that no sorting algorithm based on comparing pairs of keys can be faster. Heap sort meets the Gleason bound so is the fastest possible in this context. Actually the usual versions of quick sort are slower. If the keys are not too long, radix sort is O(n) and faster. All this has been well known for decades. I explained a little more in another post in this thread.
> If the keys are not too long, radix sort is O(n) and faster.
More precisely, if the key length is w, then radix sort is O(w n) operations. In particular, if the n elements are distinct integers for example, w is greater than log(n).
Versions of quick sort differ in how the partitions are determined. A guess is that some of the versions are not worst case O(n log n) for sorting n keys. In that case, for sufficiently large n, on a normal computer, any version of heap sort will beat that version of quick sort in number of comparisons, time in seconds, Joules of energy to run the computer, etc.
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.
Sure, we don't know how big n has to be. In practice, in an actual case, the n might have to be too big for current computers.
Sure, in practice, for some value of n, on some list of n keys, some version of heap sort, and some version of quick sort, the quick sort might run 10 times faster in seconds of elapsed time than heap sort.
I'm not completely sure what you are saying, but do you actually think a heap sort is in general faster than a quicksort or mergesort? You realize that the worst case of a quick sort is easily avoided right? The only way it happens is if you have an already sorted array and you pick your pivots from the minimum or maximum values on every single partition.
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. Where did you get this idea? I just showed you a quicksort being 10 times faster than a heapsort. You can try this for yourself.
Sure, we don't know how big n has to be. In practice, in an actual case, the n might have to be too big for current computers.
This is never going to be true. Quicksort and other sorts exploit locality much better. Partitioning an array gradually makes the sorting more local. That's going to work better relatively to a heap sort as data gets bigger, not worse.
Sure, in practice, for some value of n, on some list of n keys, some version of heap sort, and some version of quick sort, the quick sort might run 10 times faster in seconds of elapsed time than heap sort.
No, on any modern computer other sorts are going to beat a heapsort. It isn't exotic, it is how it works. Even if you have to scan every element first to get a distribution of your elements to choose your pivot, that is still going to be O(n log n) and it will still beat a heap sort.
Heap sorts are not the fastest way to sort. They can be consistent and they can split the time between inserting and extracting elements.
> I'm not completely sure what you are
saying, but do you actually think a heap
sort is in general faster than a quicksort
or merge sort
"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.
Also Gleason, Knuth, and much of the academic computer science community.
Prove it, show me who is saying 'nothing can beat a heapsort'.
says next to nothing about the big-O expression.
Why do you think heap sort is the only n log n sort? Link something that proves what you say.
settled on big-O as the way to compare algorithms and code
Time determines speed, that's what this thread is about. I already linked you a benchmark of 32 million floats. Link me something that actually backs up what you are saying.
Arguing with the Gleason bound -- about like arguing with the Pythagorean theorem.
The only thing that comes up is your comment. I've shown you actual results, you keep saying 'maybe possibly in some scenario I can't show, this other one wins, so it is the fastest'. You are hallucinating a reality that you can't demonstrate.
I guess this is the "I already told you" part of the conversation, but you didn't link a single thing.
All you did was repeat your claim over and over. No benchmarks, no link to 'gleason bound' and nothing but hallucinating hypothetical scenarios and declaring that somehow they would back up your claims that go against literally all benchmarks and computer science knowledge. If I'm wrong, show me some links.
If something runs in less time, it's faster. If something runs in 1/10th the time as something else it is multiple orders of magnitude faster. I don't think I've ever seen someone try to redefine 'faster' before.
You keep trying to equate naive algorithmic complexity and speed, but you haven't even linked anything that shows heapsort is better than other sorts like quicksort at that. You haven't actually linked anything to back up any of what you're saying, even the irrelevant offtopic claims.
Early in my career, I had a really good career going. I paid a lot of attention to writing fast code.
Some of that career was in a Navy lab, and some of the people there wrote fast code by going down to the assembly language and checking each instruction, load, store, etc.
At times that career bumped into some math -- 0-1 integer linear programming, even ordinary linear programming, optimization, e.g., BFGS as elsewhere in this thread, the fast Fourier transform, power spectral estimation, optimal control, stochastic optimal control, classic linear statistics, non-parametric statistics, ill-conditioned matrices, on and on. So, to get a better background in the math, I put my career on hold and went for a Ph.D. in pure/applied math.
In my first semester the faculty wanted me to take their first ugrad computing course. Heck, I'd already taught such a course at/for Georgetown U. But I took the course anyway.
Then in the course, the issue of fast code came up. Soon, by some of the computer science faculty interested in computational complexity, I got slapped around like a butterfly in a hurricane.
Yup, one way, commonly the way first seen, to write fast code is to check each machine instruction, pay attention to caches, locality of reference, etc.
But another way to write fast code is to back off, basically forget about the individual instructions, etc. and take as the criterion number of comparisons of pairs of keys. Right, just f'get about all those other details of the hardware, just what the compiler did with do-while and if-then-else, etc. That's what was catching on, strongly, in computer science at the time.
Sooo, broadly that's two quite different ways to look at how to write fast code.
The Gleason bound? That's in one of the D. Knuth volumes The Art of Computer Programming.
That was A. Gleason, a math prof at Harvard with a spectacular career -- before his Ph.D., solved one of D. Hilbert's famous problems intended to keep mathematicians occupied for the 20th century, was made a Harvard Fellow, joined the math faculty, and never bothered with a Ph.D.
Gleason started with, for any given positive integer n, we will be sorting n keys. Sooooo, how big of a problem is that? Well (from my memory and not looking up my copy of Knuth on a shelf just behind me), assume the keys are distinct, that is, no ties. Then the problem is sorting all n! permutations of the n distinct keys. Then, ... Gleason argued from just counting the permutations and assuming that the sorting was by comparing pairs of keys, that on average could not sort in fewer than O(n log n) such comparisons. So, Gleason just counts comparisons and ignores number of parallel processors, number of levels of cache memories, the details of the instruction set of the processor(s), .... Then, as I recall, Knuth continues on and argues that heap sort achieves the Gleason bound both on average and worst case. Sooooo, in that context, heap sort is the fastest possible.
Right: The class could have had a contest, who can write code for the fastest sort on a certain list of, say, 10,000 names. Some people use quick sort, heap sort, radix sort, shell sort, bubble sort, ....
No telling who will win. Even if several students use heap sort, no telling.
So what CAN we tell? As n grows, even some really inefficient coding, maybe even in an interpretive language, will totally blow away like that butterfly in a hurricane ANY coding of bubble sort. And as I recall, it's possible for quick sort to lose on some permutations unless the partitions are selected carefully -- that is, the worst case performance of some versions of quick sort can fail to achieve the Gleason bound and run slower than even a very inefficient coding of heap sort.
That is, if want to take Gleason's approach, just count comparisons of pairs of keys and look at the big-O results, can't beat heap sort.
A short answer is, if win in the big-O comparison, then, no matter how sloppy the coding, for all sufficiently large n, still will win no matter how measure speed. In short, that's the reason people took big-O very seriously.
Yes, there is more to computational complexity than I've outlined here, and as I've already mentioned, in some contexts there can be more to sorting.
Still, again, in short, in simple terms, in a very important sense, Gleason was right, can't beat the Gleason bound, and can't beat heap sort.
I just wanted to improve my career. I never wanted to be a college professor, teacher, researcher, etc., yet for various reasons I've done all those things.
Now "to improve my career", I want to be a successful entrepreneur. My startup? It might flop, and I can't be sure it won't. But it might be worth $100 billion, and I can't say it won't. Here I've made a little contribution to the teaching of computing, coding, and computer science of sorting. But I'm no college professor. Back to my startup. A Chaired Professor of Applied Math? I don't want to occupy one. If my startup is really successful, maybe I'll fund one.
This wall of text is very bizarre. First, I don't know where you got "gleason bound" from, but if you search for it on google, your comment in this thread is the only thing that comes up.
Second, your "alternative speed" measures are a hallucination.
Sooo, broadly that's two quite different ways to look at how to write fast code.
No there isn't. The one that takes 1/10th the time of the other one is faster. You going off on tangents and making up terms to try to say that a heap sort is the fastest sort (of all the strange things to argue) is nonsense.
> First, I don't know where you got
"gleason bound" from,
For the answer and posted in this thread,
I wrote:
The Gleason bound? That's in one of the
D. Knuth volumes The Art of Computer
Programming.
> Second, your "alternative speed"
measures are a hallucination.
No. Instead, I wrote in this thread:
A short answer is, if win in the big-O
comparison, then, no matter how sloppy the
coding, for all sufficiently large n,
still will win no matter how measure
speed. In short, that's the reason people
took big-O very seriously.
If you want to argue against heap sort,
then you need to argue that in counting
comparisons the big-O expression for heap
sort is wrong and loses out to some other
sorting algorithm.
The Gleason bound assumes that each
comparison costs the same. So you may
want to argue that for n keys, as n grows
the issues of caches, locality of
reference, parallel processors, etc. mean
that the cost of each comparison grows so
that in the big-O competition heap sort
can be beat.
I'll let someone else calculate the big-O
expressions again considering locality of
reference, etc.
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.
> 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 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.
> Instead of repeating yourself, can you link to some actual information?
> I gave the reference, D. Knuth's famous book.
I just Ctrl+F'd "Gleason" in The Art of Computer Programming Vol 1, Vol 2, Vol 3, Vol 4A, and Vol 4B, with no hits in any of the 5 books.
I even looked in the glossaries. There's lots of last names -- Glaisher, Glassey, Gnedenko -- and no "Gleason".
I'm tempted to side with this iteration of CyberD's brutal takedowns on this one. :D
---- EDIT ----
WAIT: I found it in the glossary of Vol 3!
"Gleason, Andrew Mattei, 193, 648."
For this one, case sensitivity got me when I searched "gleason"!
The most relevant bit here seems to be page 193, discussing ways to minimize the average number of comparisons:
```
The minimum possible average number of comparisons, obtained by dividing by N, is never less than lg N and never more than lg N + 0.0861. [This result was first obtained by A. Gleason in an internal IBM memorandum (1956).]
```
"Gleason" is only mentioned in Vol 3.
"Gleason bound" is not used in Vol 3, which must be why it doesn't pop up on Google.
I showed you benchmarks with source code. You showed me nothing.
Heck, even bubble sort could beat heap sort or quick sort under some circumstances.
It isn't going to beat them on 32 million floats, which was what that benchmark showed. And are you now mixing up actual execution time with your other bizarre claims where 'speed' and 'faster' for some reason don't mean less time?
Okay, there are some ties. I never said there are no ties.
You did actually, now you're back peddling hard. Also these don't tie, they are faster because of locality.
Third, I gave the reference, D. Knuth's famous book.
Link something then, link any trace of what you are saying.
The Gleason bound is one of the nicer, most powerful, most useful, most important pieces of work in all of computer science,
Then why is there no evidence that it exists? Link me literally anything you can.
You have some problems, some blocks in understanding.
No, I have evidence and links that back up what I'm saying. You keep repeating the same things with no evidence. Link me literally anything you can find that reinforces your claims.
For your emotional problems, nothing in computing, computer science, or my writing can help you.
> 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.
Definitely more. There are lots of things that might be more optimal in terms of raw complexity but end up having abysmal performance due to things like cache locality. Anything with pointer chasing usually kills performance.
for example, matrix multiplication has all sorts of algorithms with exponent significantly less than 3, but they are nearly all curiosities. In practice, the straightforward N^3 algo is used nearly everywhere
I had a long discussion with Rob Pike once that ended with me saying "you know, I don't think people actually use Strassen on supercomputers" (we were discussing how somebody had managed to show an N*2.37 algorithm or something like that and "it was a new world's record").
