Deepmind의 AlphaDev가 더 빠른 Sort 알고리즘 발견

• C/C++ 레벨의 언어로는 개선이 어렵다고 판단, 어셈블리어 레벨에서 개선을 시도
• 마치 게임처럼 주어진 답에 맞는 답을 내는 알고리즘을 끊임없이 탐색
• LLVM libc++ sorting library 대비 적은 수에선 70% 빠른 성능, 25만개를 넘는 시퀀스에선 1.7% 빠른 성능을 보여줌
• 대부분의 정렬이 짧은 시퀀스에서 일어나기 때문에 여기에 더 집중함
• 단순히 빠른 것이 아니라 알파고의 37수에 비견되는 기발한 접근법을 보여줌
• 해싱 알고리즘도 개선 중

[kuroneko]

AI로 더 나은 알고리즘도 찾을 수 있다니 정말 신기하네요.

[dbs0829]

딥러닝에서 사용하는 optimizer도 최근에는 저런식으로 찾는 시도가 꽤 이루어지고 있더라고요. 성능도 좋고요.

[spark]

"대부분의 정렬이 짧은 시퀀스에서 일어나기 때문에 여기에 더 집중함"이 아니라 그냥 3개, 4개, ... 8개의 정해진 개수의 숫자를 정렬하는 어셈블리 알고리즘을 발견하도록 학습시켰습니다.

[disjukr]

원문을 보면 AlphaDev를 만든 연구진들이 그런 의도를 갖고 학습시켰다는 걸로 보이네요.

We focused on improving sorting algorithms for shorter sequences of three to five elements. These algorithms are among the most widely used because they are often called many times as a part of larger sorting functions. Improving these algorithms can lead to an overall speedup for sorting any number of items.