News for hackers. Stuff that matters.
Re:Deepmind Alphadev: Faster sorting algorithms discovered u... by bloppe on Wednesday June 07, 2023 @08:10PM (#36235434)
Sorting is not a niche topic. Anybody who majored in CS (which is a ton of people these days) will read the abstract and most of the paper thinking "Wow, I can't believe they discovered something better than O(N log N)" because that's usually what people mean when they say "better sorting algorithm". What they discovered here is effectively a new compiler optimization. They should present it as such instead of calling it a new sorting algorithm.

But ya, discovering a new compiler optimization automatically is kinda cool.

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