アカウント名:
パスワード:
たまに、最前線で使われてる実践的なアルゴリズムである、と誤解してる人を見かけるけど、実際のところは「初学者にすぐに説明出来るぐらいに簡単な内では一応実用性があるやつ」ぐらいがせいぜい。
その簡単さ故に、そこで紹介されてる範囲ではクイックソートが最強、という構成の教科書が多いのが原因じゃないかと思うけど。あるいは、再帰呼び出しが必要になる分かりやすい例として重宝されているだけか。
ちゃんと、違うんだぞさっと説明出来るのがこの辺までなだけでこれは実用的じゃないからな、ときちんと注意する必要がある。
汎用ソートアルゴリズムで、クイックソートを時代遅れにするほど早い奴って、具体的にはどれの話？
＞あるいは、再帰呼び出しが必要になる分かりやすい例として重宝されているだけか。知ったかぶりしても、こういう所でウソがバレる。
クイックソートでは再帰呼び出しは使わない。再帰呼び出しを使っても書けるだけ。必用なんてとんでもない。
具体的なソート名が欲しいですねただ、今のソートって内部はイントロソートのようにクイックソートだけでなく組み合わせたソートになっているケースはあるかも素朴なクイックソートだと最悪計算量にさせることもできてしまうのでとはいえ概ね多くのケースではクイックソートを時代遅れと表現するような差は生まれないですね
「2要素間の比較で並べ替えるソート」としては、理論的に最速でも O(n log n) が限界であることは証明されていて、クイックソートやマージソート、ヒープソートなどの「速いソート」はどれも O(n log n) なので、所詮、同じ計算量オーダーの中でのオーバーヘッドの優越にすぎず、「時代遅れにするほど速い奴」なんてのはありえないでしょうね。
バケットソートやラディックスソートが使える場面なら、そっちの方が桁違いに速いですが、そもそも使える場面が限られるし。
彼は量子コンピュータの進歩で、すべてのn!の並べ替えが重ね合わさった状態から正しくソートされた状態に波束を収束させることが可能になった未来から来たんだよ。そこではこの量子ボゴソート(?)がすべてのソートアルゴリズムを過去の遺物にしたんだ。
クイックソートは最悪値のO(N^2)が比較的容易に発生するし、メジャーな処理系のsortにはまず採用されてない
そんなことない。よくある並べ替えるリストの要素数に応じてソートアルゴリズムを使い分けるケースでクイックソートを使ってるケースもある。
例えば、.net 5 の Array.Sort メソッドでは、
このメソッドでは、次のように introspective sort (introsort) アルゴリズムが使用されます。- パーティションサイズが16要素以下の場合は、 挿入並べ替え アルゴリズムが使用されます。- パーティションの数が 2 * Log Nを超えている場合 ( n は入力配列の範囲)、 heapsort アルゴリズムが使用されます。- それ以外の場合は、 クイックソート アルゴリズムを使用します。
https://docs.microsoft.com/ja-jp/dotnet/api/system.array.sort?view=net-5.0 [microsoft.com]
O(N^2)になるのは、データが逆順に並んでいるときですね。作為的にやらない限りは容易に発生しないと思いますが。
というか、実作業で一番クリティカルなのはワーストなんだよなあ。
うちの上司も困ったことに、「普段の速度稼ぐのは簡単だろ？」と言ってワーストが悪化する案を持ち込んで来るんで騒ぎになるんだが。「これなら最速1割早い」「ワーストが1割以上遅くなる」ってよくケンカしている。システムの要件が余裕が有るのなら反対しないが、ギリギリで破綻する様な状態でそれ言われても。
そういや、「最悪でもO(n log n)時間」で「安定(入れ替えなくて良い所は元の順序が保たれる)」で「内部(必要な追加のメモリがO(log n))」な、ある種の究極ソートアルゴリズムは見つかっていないようですが、存在しないことが証明されてるような話なんでしょうか? あるいは有るかどうかもまだ分かっていない未解決問題なんでしょうか?
元の論文は読んで無いけど、解説によると実用上速くないらしい。https://stackoverflow.com/questions/22390951/how-does-the-franceschini... [stackoverflow.com]
「読んで無い」
「内部」である、なんて用語は聞いたことないけど一般的なのか？括弧の位置がおかしいだけ？
in-placeなソートアルゴリズムを日本語に訳すと内部ソート。内部ソートとしての性質を満たすような、をどう短く形容詞に落とし込めば良いのかは良く知らない。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
日々是ハック也 -- あるハードコアバイナリアン
クイックソートはオワコンなので問題無し (スコア:-1)
たまに、最前線で使われてる実践的なアルゴリズムである、と誤解してる人を見かけるけど、
実際のところは「初学者にすぐに説明出来るぐらいに簡単な内では一応実用性があるやつ」ぐらいがせいぜい。
その簡単さ故に、そこで紹介されてる範囲ではクイックソートが最強、という構成の教科書が多いのが原因じゃないかと思うけど。
あるいは、再帰呼び出しが必要になる分かりやすい例として重宝されているだけか。
ちゃんと、違うんだぞさっと説明出来るのがこの辺までなだけでこれは実用的じゃないからな、ときちんと注意する必要がある。
ウソばっか (スコア:1)
汎用ソートアルゴリズムで、クイックソートを時代遅れにするほど
早い奴って、具体的にはどれの話？
＞あるいは、再帰呼び出しが必要になる分かりやすい例として重宝されているだけか。
知ったかぶりしても、こういう所でウソがバレる。
クイックソートでは再帰呼び出しは使わない。
再帰呼び出しを使っても書けるだけ。必用なんてとんでもない。
Re: (スコア:1)
具体的なソート名が欲しいですね
ただ、今のソートって内部はイントロソートのようにクイックソートだけでなく組み合わせたソートになっているケースはあるかも
素朴なクイックソートだと最悪計算量にさせることもできてしまうので
とはいえ概ね多くのケースではクイックソートを時代遅れと表現するような差は生まれないですね
Re:ウソばっか (スコア:1)
「2要素間の比較で並べ替えるソート」としては、理論的に最速でも O(n log n) が限界であることは証明されていて、
クイックソートやマージソート、ヒープソートなどの「速いソート」はどれも O(n log n) なので、
所詮、同じ計算量オーダーの中でのオーバーヘッドの優越にすぎず、
「時代遅れにするほど速い奴」なんてのはありえないでしょうね。
バケットソートやラディックスソートが使える場面なら、そっちの方が桁違いに速いですが、そもそも使える場面が限られるし。
Re:ウソばっか (スコア:1)
彼は量子コンピュータの進歩で、すべてのn!の並べ替えが重ね合わさった状態から正しくソートされた状態に波束を収束させることが可能になった未来から来たんだよ。そこではこの量子ボゴソート(?)がすべてのソートアルゴリズムを過去の遺物にしたんだ。
Re: (スコア:0)
クイックソートは最悪値のO(N^2)が比較的容易に発生するし、メジャーな処理系のsortにはまず採用されてない
Re:ウソばっか (スコア:1)
そんなことない。よくある並べ替えるリストの要素数に応じてソートアルゴリズムを使い分けるケースでクイックソートを使ってるケースもある。
例えば、.net 5 の Array.Sort メソッドでは、
このメソッドでは、次のように introspective sort (introsort) アルゴリズムが使用されます。
- パーティションサイズが16要素以下の場合は、 挿入並べ替え アルゴリズムが使用されます。
- パーティションの数が 2 * Log Nを超えている場合 ( n は入力配列の範囲)、 heapsort アルゴリズムが使用されます。
- それ以外の場合は、 クイックソート アルゴリズムを使用します。
https://docs.microsoft.com/ja-jp/dotnet/api/system.array.sort?view=net-5.0 [microsoft.com]
Re:ウソばっか (スコア:1)
Re: (スコア:0)
O(N^2)になるのは、データが逆順に並んでいるときですね。作為的にやらない限りは容易に発生しないと思いますが。
Re: (スコア:0)
というか、実作業で一番クリティカルなのはワーストなんだよなあ。
うちの上司も困ったことに、「普段の速度稼ぐのは簡単だろ？」と言ってワーストが悪化する案を持ち込んで来るんで騒ぎになるんだが。
「これなら最速1割早い」「ワーストが1割以上遅くなる」ってよくケンカしている。
システムの要件が余裕が有るのなら反対しないが、ギリギリで破綻する様な状態でそれ言われても。
Re: (スコア:0)
そういや、「最悪でもO(n log n)時間」で「安定(入れ替えなくて良い所は元の順序が保たれる)」で「内部(必要な追加のメモリがO(log n))」な、ある種の究極ソートアルゴリズムは見つかっていないようですが、存在しないことが証明されてるような話なんでしょうか? あるいは有るかどうかもまだ分かっていない未解決問題なんでしょうか?
Re: (スコア:0)
元の論文は読んで無いけど、解説によると実用上速くないらしい。
https://stackoverflow.com/questions/22390951/how-does-the-franceschini... [stackoverflow.com]
Re: (スコア:0)
「読んで無い」
Re: (スコア:0)
「内部」である、なんて用語は聞いたことないけど一般的なのか？
括弧の位置がおかしいだけ？
Re: (スコア:0)
in-placeなソートアルゴリズムを日本語に訳すと内部ソート。
内部ソートとしての性質を満たすような、をどう短く形容詞に落とし込めば良いのかは良く知らない。