アカウント名:
パスワード:
これですね。https://gigazine.net/news/20230608-alphadev-sort-algorithm/ [gigazine.net]
「3~5要素のソートで最大70%高速化しており、25万要素を超えるような大規模なソートでも約1.7%高速化できたと述べられています。」1.7%でも大したものだとは思うけれども、70%のインパクトから本文を読むとなんかちょっと残念な印象が。
大量データに対応したソートアルゴリズムは、小数を処理するときにはオーバーヘッドが大きすぎてあまり速くないので、今時のソートライブラリは分割統治でデータ数に応じてソートアルゴリズムを切り替えるのが一般的
というのが前提で、「最大5要素の固定要素数ソートアルゴリズム」を高速化、というのが今回の話ですね。だから、3~5要素で最大70%(≒3倍)の高速化が、25万要素ソートの末端で適用されることで、1.7%高速化につながる、と。
ソートというのは、「12個の玉のうち一個だけ重さが違う。天秤を3回使って見つけ出せ」といった数学パズルの複雑版みたいなもので、こういうパズルで「こういう順番で比較していけば、12個のうちどれが当たりでみ見つけ出せる」という比較パターンが回答になるように
ソートも、「こういう順番で比較していけば、元データがどんな並び順であっても、その並び順を判断できる(≒正しく並べ替えられる)」ような比較パターンを構築することがキモになります。
通常のソートアルゴリズムは、汎用的に要素数可変で、それぞれのアルゴリズムで規定されたルールで比較を繰り返すことになりますし、そういうルールで比較すれば正しく並び替えられることをあらかじめ証明されたものが「ソートアルゴリズム」と呼ばれるわけですがが、
要素数固定の処理ルーチンなら、どれとどれを比較していくのかも固定になりますし、
例えば、3要素のソートなら、元データのありえる順番は「1,2,3」「1,3,2」「2,1,3」「2,3,1」「3,1,2」「3,2,1」の6通り。5要素でも元データは120通りしかありませんから、その全データを処理させてみれば、「ありえるどんなデータでもソートできている」=「正しいソートアルゴリズムである」かどうかは機械的に証明可能です。
あとは正しいソートアルゴリズムとして高効率なものをAIベースで探した、ということでしょう。
「最大」と聞くとワースト時の偏りも気になりますね。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
UNIXはシンプルである。必要なのはそのシンプルさを理解する素質だけである -- Dennis Ritchie
既出…と思ったらGIGAZINEか (スコア:2, 参考になる)
これですね。
https://gigazine.net/news/20230608-alphadev-sort-algorithm/ [gigazine.net]
Re:既出…と思ったらGIGAZINEか (スコア:0)
「3~5要素のソートで最大70%高速化しており、25万要素を超えるような大規模なソートでも約1.7%高速化できたと述べられています。」
1.7%でも大したものだとは思うけれども、70%のインパクトから本文を読むとなんかちょっと残念な印象が。
Re:既出…と思ったらGIGAZINEか (スコア:2)
大量データに対応したソートアルゴリズムは、
小数を処理するときにはオーバーヘッドが大きすぎてあまり速くないので、
今時のソートライブラリは分割統治でデータ数に応じてソートアルゴリズムを切り替えるのが一般的
というのが前提で、「最大5要素の固定要素数ソートアルゴリズム」を高速化、というのが今回の話ですね。
だから、3~5要素で最大70%(≒3倍)の高速化が、
25万要素ソートの末端で適用されることで、1.7%高速化につながる、と。
ソートというのは、
「12個の玉のうち一個だけ重さが違う。天秤を3回使って見つけ出せ」
といった数学パズルの複雑版みたいなもので、
こういうパズルで「こういう順番で比較していけば、12個のうちどれが当たりでみ見つけ出せる」という比較パターンが回答になるように
ソートも、「こういう順番で比較していけば、元データがどんな並び順であっても、その並び順を判断できる(≒正しく並べ替えられる)」ような比較パターンを構築することがキモになります。
通常のソートアルゴリズムは、汎用的に要素数可変で、それぞれのアルゴリズムで規定されたルールで比較を繰り返すことになりますし、そういうルールで比較すれば正しく並び替えられることをあらかじめ証明されたものが「ソートアルゴリズム」と呼ばれるわけですがが、
要素数固定の処理ルーチンなら、どれとどれを比較していくのかも固定になりますし、
例えば、3要素のソートなら、元データのありえる順番は「1,2,3」「1,3,2」「2,1,3」「2,3,1」「3,1,2」「3,2,1」の6通り。
5要素でも元データは120通りしかありませんから、
その全データを処理させてみれば、
「ありえるどんなデータでもソートできている」=「正しいソートアルゴリズムである」かどうかは機械的に証明可能です。
あとは正しいソートアルゴリズムとして高効率なものをAIベースで探した、ということでしょう。
Re: (スコア:0)
「最大」と聞くとワースト時の偏りも気になりますね。