2020-01-14

anond:20200114041018

ソートプログラム 太田式(名前適当)一考察

 

バケツソートバブルソートを含むとする)のような単純なソートプログラムを例にとっても

N=1,Bigとき例外となる。プログラム教育ではこういう例外は良くおきるので準正常系のようなものだが、慣例的に例外と呼ぶ

どうように1,1,1,1、のような偏りの大きいデータにたいしてもソートプログラムは特異な処理時間必要とする。

 

ソートは、そのデータの量や質、大きすぎる、小さすぎる、偏りが大きすぎる、小さすぎる

などによって、一般的に言われている特性とはことな特性を示す。

これがもっと標準的ソート例外であり

データや偏りが小さいときコンパイラなどの最適化により、さらに異なる特性を示すことがある。

一般的にはコンパイラ最適化は気にする必要がないが、こういう例外にはなりやすいので、納品などがある場合は1度確認しておいたほうがよい(アセンブラレベルコード確認など方法任意

 

入力の量の偏り、質の偏り、装置特性★ これはどのプログラムでもそうだが、ソート説明やすい。

記事への反応 -
  • ★ソート関数の説明は大体した。 バブルソート、バケツソートであってもN=1,Bigの時には異なる数値を出すことがある。 ましていわんやその他のソート。 当然何でこれだけの数のソート...

    • ソートプログラム 太田式(名前は適当)一考察   バケツソート(バブルソートを含むとする)のような単純なソートプログラムを例にとっても N=1,Bigのときは例外となる。プログラム...

    • バケツソートなんて使う場面は無い おとなしくライブラリのものを使っとけ

      • DLLだったもんでライブラリの電子書名の検証プログラム書くのがめんどかった 連鎖書名をどこまで検証するかむずかしいしな、いちおう、Windowsに信用できる書名がはいっていればOKでも...

        • いちおう、連鎖書名のすべての書名を1つ1つ確認していくようなオプションもコンパイルオプションではあったはず。書いた記憶がある。Forまわすだけやからな。 コンパイルオプショ...

      • 実際、ちょっとしたソートだとバケツソートで十分。N=1といっておいたのは学生のため。現場だとたぶん16ぐらいまではバケツのほうがいい。

        • さすがにどうしてN=16ぐらいまでバケツにするかを数式で理想的なコンピューターで説明しようとすると先生がめんどくさいから1にしといた。 1がそうなら2はどうなの3は?というの...

          • でもいい指摘だな 交換のコストを定数で10としたけど、実際は交換のコストが定数じゃない場合もあるからな

            • お前らのバケツは人力か

              • キーとポインタだけを交換するのではなく、ちいさいと、キーとデータが直で入ってる場合があるからな。そうするとデータの長さが可変長なことがあるからむずかしい。 普通はポイン...

                • そういう意味ではC言語のポインタは正規化されたデータベース構造のほかのテーブルのキーの値に近いのがポインタ 直接テーブル増やすのが配列みたいなイメージか

                  • こういうのは現場で教えていくから、増田にかくと頭でっかちが増えるから、やめてくれってはなしになるんやろうな。

        • バケツソートで十分ならクイックソートでも十分だし、 それならライブラリのものをそのまま使えば良いので わざわざバケツソートを実装する意味がない

記事への反応(ブックマークコメント)

ログイン ユーザー登録
ようこそ ゲスト さん