アカウント名:
パスワード:
これですね。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ベースで探した、ということでしょう。
「最大」と聞くとワースト時の偏りも気になりますね。
いくつかの入力例でテストしてOKでしょってAI様がアルゴリズム出して、本当に正しく問題解くアルゴリズムか人間が頑張って証明するのね
でも「いくつかの例」の数を膨大にしとけば偶然は防げるし、そもそも候補が既知の最短行数であることは担保されてて差分を見るだけなんだから、楽しそうではある。
２０年３０年以上前からある既知の技術で新規性は無くね？C/C++やアセンブラでコード自己改変/生成しながらJITで最適化するとか。
富豪的プログラミングとか贅沢を覚えて忘れちゃったのかもしれないけど。ロストテクノロジー化＆車輪の再発明になるのはなんだかなぁ。
少なくともこれは富豪的な手法でコード生成してるだろうし、これってJITで最適化してるの？
うーん全然違うJITにAIを使うと勘違いしたのかしら
https://news.ycombinator.com/ [ycombinator.com]GIGAZINEの更に元ネタ
今回の記事はこのスレですねhttps://news.ycombinator.com/item?id=36228125 [ycombinator.com]
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
日本発のオープンソースソフトウェアは42件 -- ある官僚
既出…と思ったらGIGAZINEか (スコア:2, 参考になる)
これですね。
https://gigazine.net/news/20230608-alphadev-sort-algorithm/ [gigazine.net]
Re: (スコア: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)
「最大」と聞くとワースト時の偏りも気になりますね。
Re: (スコア:0)
いくつかの入力例でテストしてOKでしょってAI様がアルゴリズム出して、
本当に正しく問題解くアルゴリズムか人間が頑張って証明するのね
Re: (スコア:0)
でも「いくつかの例」の数を膨大にしとけば偶然は防げるし、そもそも候補が既知の最短行数であることは担保されてて差分を見るだけなんだから、楽しそうではある。
JIT「呼んだ？」 (スコア:0)
２０年３０年以上前からある既知の技術で新規性は無くね？
C/C++やアセンブラでコード自己改変/生成しながらJITで最適化するとか。
富豪的プログラミングとか贅沢を覚えて忘れちゃったのかもしれないけど。
ロストテクノロジー化＆車輪の再発明になるのはなんだかなぁ。
Re: (スコア:0)
少なくともこれは富豪的な手法でコード生成してるだろうし、これってJITで最適化してるの？
Re: (スコア:0)
うーん全然違う
JITにAIを使うと勘違いしたのかしら
Re: (スコア:0)
https://news.ycombinator.com/ [ycombinator.com]
GIGAZINEの更に元ネタ
今回の記事はこのスレですね
https://news.ycombinator.com/item?id=36228125 [ycombinator.com]