Re:Deepmind Alphadev: Faster sorting algorithms discovered u...
by recursive on Wednesday June 07, 2023 @08:26PM
(#36235529)
70% better than O(N log N) is still O(N log N).
Re:Deepmind Alphadev: Faster sorting algorithms discovered u...
by ummonk on Wednesday June 07, 2023 @08:55PM
(#36235775)
It's 70% better than O(1). The algorithms it found are for sort3, sort4, and sort5, which were poorly optimized in LLVM's libc++.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u...
by pclmulqdq on Thursday June 08, 2023 @12:10PM
(#36244270)
It may have also laundered those from open-source code that wanted to optimize sort3, sort4, and sort5.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u...
by saiojd on Wednesday June 07, 2023 @09:16PM
(#36235925)
I see your point. I just went over the abstract again and I totally agree.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u...
by Dylan16807 on Thursday June 08, 2023 @01:07AM
(#36237471)
> because that's usually what people mean when they say "better sorting algorithm"
Is it really? I've heard of a few "better sorting algorithms" and it's never meant that in my experience.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u...
by cubefox on Thursday June 08, 2023 @12:26PM
(#36244540)
When people say "sorting algorithm" they mean something like bubble sort or merge sort.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u...
by qumeric on Thursday June 08, 2023 @12:37PM
(#36244700)
Tbh people who majored in CS are supposed to know that it was proven long ago that better than O(N log N) sorting (in general case) is impossible.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u...
by elcomet on Saturday June 10, 2023 @04:09AM
(#36268661)
I hope people majoring in CS will not think that, as they learned that n log n is the theorically best complexity for a sort algorithm. They will rather think that they found an algorithm with better constants in front of n log n.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u...
by Zacharias030 on Saturday June 10, 2023 @04:27PM
(#36274742)
true that
But ya, discovering a new compiler optimization automatically is kinda cool.