Programming

13368 readers

2 users here now

All things programming and coding related. Subcommunity of Technology.

This community's icon was made by Aaron Schneider, under the CC-BY-NC-SA 4.0 license.

founded 1 year ago

MODERATORS

[email protected]

AlphaDev discovers faster sorting algorithms (www.deepmind.com)

submitted 1 year ago by [email protected] to c/[email protected]

17 comments fedilink hide all child comments

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.

you are viewing a single comment's thread
view the rest of the comments

[–] [email protected] 2 points 1 year ago (1 children)

This write up talks about sequences of 3 and 4 items… does their full paper generalize to variable sized lists?

[–] [email protected] 3 points 1 year ago* (last edited 1 year ago) (1 children)

From the main section of the paper published in Nature (which is available for free):

Using AlphaDev, we have discovered fixed and variable sort algorithms from scratch that are both new and more efficient than the state-of-the-art human benchmarks. The fixed sort solutions for sort 3, sort 4 and sort 5 discovered by AlphaDev have been integrated into the standard sort function in the LLVM standard C++ library

It seems they did find improvements for sorting variable sized list but only the sort 3, sort 4 and sort 5 algorithms got implemented in LLVM.

[–] [email protected] 3 points 1 year ago* (last edited 1 year ago)

Oh I see! I didn’t realize llvm had specific-count implementation