パスワードを忘れた? アカウント作成
この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。

「クイックソート」が商標登録されていた」記事へのコメント

  • たまに、最前線で使われてる実践的なアルゴリズムである、と誤解してる人を見かけるけど、
    実際のところは「初学者にすぐに説明出来るぐらいに簡単な内では一応実用性があるやつ」ぐらいがせいぜい。

    その簡単さ故に、そこで紹介されてる範囲ではクイックソートが最強、という構成の教科書が多いのが原因じゃないかと思うけど。
    あるいは、再帰呼び出しが必要になる分かりやすい例として重宝されているだけか。

    ちゃんと、違うんだぞさっと説明出来るのがこの辺までなだけでこれは実用的じゃないからな、ときちんと注意する必要がある。

    • by Anonymous Coward on 2021年04月12日 17時44分 (#4011688)

      汎用ソートアルゴリズムで、クイックソートを時代遅れにするほど
      早い奴って、具体的にはどれの話?

      >あるいは、再帰呼び出しが必要になる分かりやすい例として重宝されているだけか。
      知ったかぶりしても、こういう所でウソがバレる。

      クイックソートでは再帰呼び出しは使わない。
      再帰呼び出しを使っても書けるだけ。必用なんてとんでもない。

      親コメント
      • by Anonymous Coward on 2021年04月12日 19時22分 (#4011757)

        具体的なソート名が欲しいですね
        ただ、今のソートって内部はイントロソートのようにクイックソートだけでなく組み合わせたソートになっているケースはあるかも
        素朴なクイックソートだと最悪計算量にさせることもできてしまうので
        とはいえ概ね多くのケースではクイックソートを時代遅れと表現するような差は生まれないですね

        親コメント
        • 「2要素間の比較で並べ替えるソート」としては、理論的に最速でも O(n log n) が限界であることは証明されていて、
          クイックソートやマージソート、ヒープソートなどの「速いソート」はどれも O(n log n) なので、
          所詮、同じ計算量オーダーの中でのオーバーヘッドの優越にすぎず、
          「時代遅れにするほど速い奴」なんてのはありえないでしょうね。

          バケットソートやラディックスソートが使える場面なら、そっちの方が桁違いに速いですが、そもそも使える場面が限られるし。

          親コメント
          • by Anonymous Coward on 2021年04月13日 2時30分 (#4011930)

            彼は量子コンピュータの進歩で、すべてのn!の並べ替えが重ね合わさった状態から正しくソートされた状態に波束を収束させることが可能になった未来から来たんだよ。そこではこの量子ボゴソート(?)がすべてのソートアルゴリズムを過去の遺物にしたんだ。

            親コメント
          • by Anonymous Coward

            クイックソートは最悪値のO(N^2)が比較的容易に発生するし、メジャーな処理系のsortにはまず採用されてない

            • by Anonymous Coward on 2021年04月12日 23時54分 (#4011902)

              そんなことない。よくある並べ替えるリストの要素数に応じてソートアルゴリズムを使い分けるケースでクイックソートを使ってるケースもある。

              例えば、.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]

              親コメント
            • by nekopon (1483) on 2021年04月15日 13時02分 (#4013825) 日記
              qsort(3)「あのー」
              親コメント
            • by Anonymous Coward

              O(N^2)になるのは、データが逆順に並んでいるときですね。作為的にやらない限りは容易に発生しないと思いますが。

              • by Anonymous Coward

                というか、実作業で一番クリティカルなのはワーストなんだよなあ。

                うちの上司も困ったことに、「普段の速度稼ぐのは簡単だろ?」と言ってワーストが悪化する案を持ち込んで来るんで騒ぎになるんだが。
                「これなら最速1割早い」「ワーストが1割以上遅くなる」ってよくケンカしている。
                システムの要件が余裕が有るのなら反対しないが、ギリギリで破綻する様な状態でそれ言われても。

          • by Anonymous Coward

            そういや、「最悪でもO(n log n)時間」で「安定(入れ替えなくて良い所は元の順序が保たれる)」で「内部(必要な追加のメモリがO(log n))」な、ある種の究極ソートアルゴリズムは見つかっていないようですが、存在しないことが証明されてるような話なんでしょうか? あるいは有るかどうかもまだ分かっていない未解決問題なんでしょうか?

            • by Anonymous Coward

              元の論文は読んで無いけど、解説によると実用上速くないらしい。
              https://stackoverflow.com/questions/22390951/how-does-the-franceschini... [stackoverflow.com]

            • by Anonymous Coward

              「内部」である、なんて用語は聞いたことないけど一般的なのか?
              括弧の位置がおかしいだけ?

              • by Anonymous Coward

                in-placeなソートアルゴリズムを日本語に訳すと内部ソート。
                内部ソートとしての性質を満たすような、をどう短く形容詞に落とし込めば良いのかは良く知らない。

        • by Anonymous Coward

          煽るタイプの教えてクンにあまり給餌しないでくれないかな

        • by Anonymous Coward

          同意。
          ソートアルゴリズムは研究され尽くしたと言ってもよいくらい歴史がありますが、大規模データのソートなどで門外不出のアルゴリズムがあっても不思議はないかも。ソートアルゴリズムが熱心に研究されていた時代とはデータ量が桁違いなので。

          • by Anonymous Coward on 2021年04月13日 3時48分 (#4011941)

            データのソートではないけど、変わったやり方してるのはいくつかあるね。
            ブロックソートはデータ圧縮以外にもバイオインフォマティクス方面で色々応用されてるぽいし、
            ウェーブレット木(ウェーブレット変換とはあまり関係ない)で
            大量データに対する何種類かの処理を超高速にこなす方法があったり、
            大量データとは無関係だけど秘密計算とか用法だけだと意味不明な奴とかもある。

            # 門外不出というより使用シーンがマイナーな奴は目立たんというだけな気もする。
            # ブロックチェーンを使った演算系の奴をそういう方面で興味津々に見に行ったら絶望した。

            親コメント
        • by Anonymous Coward

          ブラウザがJavaScriptでどうやってソートしてるのか調べてみたけど、ざっと見た感じ、Firefoxはマージソートで、Webkit系はstd::sortを呼んでるぽいから、おそらくイントロソートってことになるね。

      • by Anonymous Coward on 2021年04月12日 21時00分 (#4011830)

        C++のstd::sort()だとイントロソートか何か。
        今時の規格では「最悪時間計算量がO(n log n)の内部ソート」と定められているので少なくともクイックソートでは無理。

        std::stable_sort()は「最悪時関計算量がO(n log n)の安定そーと」と規格で定められてるので、これもクイックソートは該当しない。
        JavaのSort()は安定ソートと規格で定められていて、同じく。
        マニュアルを見ると、それじゃなきゃダメって訳ではないけど、と前置きしてマージソートが例として挙げられてる。

        PythonやRubyやJavascriptも最近では利便性のため安定ソートと明言されたり、
        明言される前から利便性のため、こそっと実装がそうなってたりする。
        マニュアルを見るとPythonは今はTimソートとやららしい。

        実用されてるとしたら、使える既存のライブラリが存在しないようなマイナーな環境で、
        他から移植するにも実装にかけられる時間が足りないか、極端にメモリが小さいかで、
        しょうがなく…とかそういう? そんな例あるのかな。

        親コメント
        • by Anonymous Coward

          イントロソートはクイックソートの亜種でしょ。

          • by Anonymous Coward

            ソートアルゴリズムを性質で分類したら、全く別の枠に収まるぐらいに改良された亜種だけどね。

            その亜種もC++みたいなスピード狂向けの言語でしか標準ライブラリに採用されない程度に人気が無い。
            なんでこんなに不安定なソートが不人気なのか知らないけど。

            あとまあ、でかいデータを扱うソフトウェアほどスピード狂が実装する傾向にあるだろうし、
            その極北のデータベースなんかでは使われてるのかも知れないけど。
            そうなると、世界で最も大量のデータをソートしてるアルゴリズムは? の答えはその手の亜種かも知れない。

            • by Anonymous Coward

              > なんでこんなに不安定なソートが不人気なのか知らないけど。
              ???

              • by Anonymous Coward

                不安定なソートを標準ライブラリに持っているプログラミング言語が少ない。

                不安定・安定の違いは、安定なソートは必要の無いところを入れ替えない。不安定はそういう保証が無い。

                例えば名前順に並んでいる成績表を成績順にソートしたときに、100点のやつが複数人居たとする。安定なソートアルゴリズムだと、100点のやつだけ抜き出すと、そこは名前の順のままになっている。不安定なソートアルゴリズムでソートすると、同点の連中の並び順が揃わない。そういう成績表をそのまま張り出すと不格好な結果になる。

                不格好で済めば良いけど、オークションなんかで、入札金額

            • by Anonymous Coward

              条件を満たすまでは普通にクイックソートするアルゴリズムがクイックソートとは全く別の枠?
              しまいにゃスピード狂とか全く関係ないこと口走ってるし。
              そこは言語規格側でアルゴリズムまで明示してるかどうか程度の話だよ……

              革新的進歩してると思ってたら案外して無かったってのが恥ずかしいのはわからんでもないが……

              • by Anonymous Coward

                クイックソートは「最悪計算量がO(n^2)」の枠。
                イントロソートに改良すると「最悪時関計算量がO(n log n)」の枠。
                アルゴリズムのアイデアの系譜で分類しても実用的な意味はない。
                最終的に出来上がるアルゴリズムの性質が別物という話。

                同じく、言語の規格ではアルゴリズムが明示されてはいない。
                そんなところを規格化したら、より良いアルゴリズムが見つかったら困るだろうに
                その関数やメソッドが満たす性質(安定か不安定か、最悪時関計算量がO(n log n)であるなど)が示されているだけ。
                その条件を満たすアルゴリズムがあれば、実装は何でも良い。

                一般に、不安定なソートの方

            • by Anonymous Coward

              適当に放言してるその文体、元コメの人ですね?

      • by Anonymous Coward on 2021年04月13日 8時39分 (#4011984)

        クイックソートは、マルチスレッド化したときにキャッシュが効きやすいように領域を分割するので、メインメモリに収まるようなデータ列のソートについては、むしろ、時代にマッチしているように思います

        親コメント
      • by Anonymous Coward

        そりゃダムソートだよ。ダムん早いよ。

「科学者は100%安全だと保証できないものは動かしてはならない」、科学者「えっ」、プログラマ「えっ」

処理中...