AlphaDev của DeepMind phát hiện thuật toán sắp xếp nhanh hơn

• Đánh giá rằng rất khó cải thiện ở cấp độ ngôn ngữ C/C++, nên đã thử tối ưu ở cấp độ hợp ngữ
• Liên tục tìm kiếm các thuật toán cho ra đáp án đúng theo mục tiêu được cho, giống như một trò chơi
• So với thư viện sắp xếp LLVM libc++, cho hiệu năng nhanh hơn 70% với số lượng nhỏ và nhanh hơn 1,7% với các chuỗi vượt quá 250.000 phần tử
• Vì phần lớn tác vụ sắp xếp xảy ra trên các chuỗi ngắn, nên tập trung nhiều hơn vào phần này
• Không chỉ đơn thuần là nhanh hơn mà còn cho thấy một cách tiếp cận đầy sáng tạo, có thể ví với nước đi thứ 37 của AlphaGo
• Cũng đang cải thiện cả thuật toán băm

[kuroneko]

Thật đáng kinh ngạc khi AI cũng có thể tìm ra những thuật toán tốt hơn.

[dbs0829]

Ngay cả các optimizer dùng trong deep learning, gần đây dường như cũng có khá nhiều nỗ lực tìm ra theo kiểu như vậy. Hiệu năng cũng tốt nữa.

[spark]

"Thay vì kiểu ‘vì phần lớn việc sắp xếp diễn ra ở các chuỗi ngắn nên tập trung nhiều hơn vào đó’, họ đơn giản là huấn luyện nó để tìm ra các thuật toán assembly dùng để sắp xếp một số lượng số cố định gồm 3, 4, ... đến 8 số."

[disjukr]

Xem nguyên văn thì có vẻ nhóm nghiên cứu tạo ra AlphaDev đã huấn luyện nó với chủ đích như vậy.

Chúng tôi tập trung cải thiện các thuật toán sắp xếp cho những dãy ngắn từ ba đến năm phần tử. Đây là một trong những thuật toán được dùng rộng rãi nhất vì chúng thường được gọi nhiều lần như một phần của các hàm sắp xếp lớn hơn. Việc cải thiện các thuật toán này có thể giúp tăng tốc tổng thể cho việc sắp xếp với bất kỳ số lượng phần tử nào.