DeepMindのAlphaDev、より高速なソートアルゴリズムを発見

• C/C++ レベルの言語では改善が難しいと判断し、アセンブリ言語レベルでの改善を試みた
• まるでゲームのように、与えられた正解に合う答えを出すアルゴリズムを絶えず探索
• LLVM libc++ sorting library と比べて、少ない件数では 70% 高速で、25万個を超えるシーケンスでは 1.7% 高速な性能を示した
• ソートの大半は短いシーケンスで起きるため、そこにより重点を置いた
• 単に高速なだけでなく、AlphaGoの37手に比肩する独創的なアプローチを示した
• ハッシュアルゴリズムも改善中

[kuroneko]

AIでより優れたアルゴリズムまで見つけられるなんて、本当にすごいですね。

[dbs0829]

ディープラーニングで使うoptimizerについても、最近はああいう形で探す試みがかなり行われているようです。性能も良いです。

[spark]

「ほとんどのソートは短いシーケンスで行われるため、そこにより注力した」という話ではなく、単に3個、4個、…8個の決まった個数の数値をソートするアセンブリアルゴリズムを見つけるよう学習させたのです。

[disjukr]

原文を見ると、AlphaDevを作った研究チームがそのような意図を持って学習させたように見えます。

私たちは、3〜5要素の短いシーケンスに対するソートアルゴリズムの改善に注力しました。これらのアルゴリズムは、より大きなソート関数の一部として何度も呼び出されることが多いため、最も広く使われているものの一つです。これらのアルゴリズムを改善することで、任意の数の項目をソートする際の全体的な高速化につながる可能性があります。