So-net無料ブログ作成
前の10件 | -

データ数が1万じゃ〜ダメだね [ひとこと言わねば]

C言語でバブルソートのブログラムを書き、データ数1万の並び替えを行ったんだけれど、パソコンの性能が向上しすぎて、データ数が1万くらいだと、エンターキーを押して1秒以内に終わってしまうので、遅さをまったく感じないね。バブルソートの遅さ、効率の悪さを体感するには、どうも、データ数を10万くらいにしないといけないみたい。

データ数nが10万になると、データの比較回数、データの交換回数がともに約n²/2=50億回という膨大な回数になるので、遅さを痛感するよ。「これ、いつになったら終わるんだ」と不安になり、実行を強制終了させてしまったほどだにゃ。
 ――コンパイルするとき、速く計算してくれるように、最適化のおまじない「-O3」を唱えると、結構、速い。ただし、ここまで強力なおまじないを唱えると(最適化オプションをつけると)、コンパイラーが高速化のためにありとあらゆることをしてくれるので、書いたプログラムと出来上がったプログラムはまったく別なものになっている可能性がある(笑)――
明日、紹介する予定の基本選択法(Max法などともいう)は、データの比較回数は50億回でバブルソートと同じなのだけれど、データの交換回数がnオーダーでn²オーダーのバブルソートより速く並び終えることができる。それでも結構時間がかかるので、本当に終わるのかと心配になってしまうほど。

明後日紹介するであろう挿入法だと、基本選択法よりもさらに速く並び替えが終わる。挿入法を改良したシェルソートを使うと、さらに爆速化する。

現在、最も速いと言われるクイックソートまでやるかどうかはいまのところ未定だけどね。
だって、これを使うには再帰処理を理解しないといけない。再帰処理を使わない場合はスタックというデータ構造を理解する必要があるんだもん。それに、このアルゴリズム、整列法を説明するのは、ものすごく厄介だし・・・。文章だけでこれを説明するのは、まず、不可能だね。


いろんな整列アルゴリズムの面白い動画。


上の動画の1番目のやつが基本選択法、2番目が挿入法、3番目の奴がクイックソート。
この動画を見ると、並び替えの早さは、基本選択法>挿入法>クイックソートのように見えるけれど、これは並び替えるデータの数が多さがクイックソート>挿入法>基本選択法であるからそう見えるのであって、実際の並び替えの早さはクイックソート、挿入法、基本選択法の順になる。たぶん、クイックソートと挿入法ではデータの数のオーダーが少なくとも1桁は違っているはず。下手すると、2桁違うかもしれないにゃ。

コッチの動画↓の方がいいのかもしれいないね。


この動画だと、1番目が基本選択法、2番目がバブルソート、3番目が挿入法。この動画を見ると、並び替えの速さが、挿入法>基本選択法>バブルソートの順であることがわかると思うにゃ。

nice!(0)  コメント(0) 

ワクチンなし、高い致死率 豚コレラ上回る家畜伝染病 朝日 [ひとこと言わねば]


nice!(2)  コメント(0) 

ISIS支配地、700平方メートルに縮小 クルド人部隊が発表 CNN [ひとこと言わねば]


nice!(0)  コメント(0) 

ファーウェイ製品の”排除”めぐり 米中の応酬激化 NHK [ひとこと言わねば]


nice!(0)  コメント(0) 

ペンス副大統領「完全非核化まで制裁」 米朝首脳会談前に強調 NHK [ひとこと言わねば]


nice!(0)  コメント(0) 

”性的虐待”で聖職者の地位剥奪 異例の処分 ローマ法王庁 NHK [ひとこと言わねば]



nice!(0)  コメント(0) 

米軍のシリア撤退 独首相「性急」と懸念 欧米間の溝浮き彫りに NHK [ひとこと言わねば]




nice!(0)  コメント(0) 

バブルソート(泡立ち法) [数値解析]

バブルソート(泡立ち法)

 

いま仮に次のような数の列があるとする。

  

これを小さい数から大きい数へならぶ順(昇順)の数の列に変えたいとする。

この最もシンプルな方法は、隣り合う要素の大小関係を比較し、大小が逆転していたら、隣り合う2つの要素を交換するという方法。

具体的には、まず、{3,2,1}の(3,2)を比較する。3と2の大小関係が逆転しているので、3と2を交換し(2,3)にする。すると、

  

になる。

次に、{2,3,1}の(3,1)の大小関係を比較すると、順序が逆転しているので、3と1を交換し、(1,3)にする。

すると、

  

になる。

これで、最も大きい3を右端に並べられことができた。

 

ということで、{2,1,3}の部分列、部分集合

  

の要素を昇順に並べ替えればいいだろう。

(2,1)を比較すると、これは順序が逆転しているので順序を交換し、(1,2)にすると、

  

になる。

以上のことをまとめると、

  

と、隣り合う要素の大小関係を比較し、順序が逆転していたら両者を交換することによって、{3,,1}を昇順に{1,,3}にできる。

こういう数の列の並び替えをバブルソート(泡立ち法)という。

 

では、もっと複雑な

  

の場合について考える。

(4,2)は順序が逆転しているので、2つの要素を交換すると、

  

になる。

次に、(4,5)を比較すると、この順序は逆転していないので、交換せずにそのまま。

  

次に、(5,1)を比較すると、順序が逆転しているので、交換する。

  

次に、(5,3)を比較すると、順序が逆転しているので、2つの要素を交換する。

  

これで最も大きな5が右端に並べられた。

というわけで、今度は、

  

を同様に昇順に並べ替えればよい。

  {2,4,1,3}→{2,4,1,3}→{2,1,4,3}→{2,1,3,4}

これで、最大の4を右端に持ってくることができたので、4を取り除いた部分集合

  {2,1,3}

を同様に並び替えると、

  {2,1,3}→{1,2,3}→{1,2,3}

になる。

これですべて昇順に並び替えることができたのだけれど、{1,2,3}の最大値3を取り除いた部分集合

  {1,2}

を昇順に並び替える。

  {1,2}→{1,2}

これで並び替えの作業はおしまい。

これで、{2,4,5,1,3}を昇順に{1,2,3,4,5}と並び替えることができた。

 

さらに一般的につぎのような数の列、集合があるとする。

  

これを昇順に並び替える方法、アルゴリズムは次のようなものになるだろう。

 

do i=nn−1,n−2、・・・,2

 do j=1,2,・・・,i−1

  a(j)a(j+1)の大小を比較してa(j)a(j+1)を交換

 end do j

end do i

 

フォートラン的な記述ですが・・・。

 

これを元にFortranのプログラムを作ると、次のようになる。

 

! バブルソート
parameter(n=5)
integer a(n)
integer dummy

a(1)=4; a(2)=2; a(3) = 5; a(4)=1; a(5)=3

do i=n, 2, -1
    do j=1,i-1
        if (a(j).gt.a(j+1)) then !順序が逆転していたら交換
            dummy = a(j)
            a(j)=a(j+1)
            a(j+1)=dummy
        end if
    end do
end do

write(*,*) a

end

 

バブルソートを用いると、昇順にデータを並び替えられるのですが、この方法は、データの比較・交換の回数が最悪、

  

n²/2回。

n=100ならば最悪5000回、n=1000ならば50万回、n=1万ならば5千万回と、データの数nが大きくなると、データの比較・交換回数が大きくなりすぎるので、実際の並び替え、ソーティングでバブルソートが使われることはない。

 

まぁ、パソコンといえども、現在は処理速度、計算速度がトンデモなく速いから、データ数が1万くらいあってもバブルソートですぐに並び終えるので、データ数が1万くらいまでならば、最も基本的なバブルソートで十分に実用に足りると思うけれど、コンピュータの能力が低かったときは、バブルソートの遅さは致命的だったんだケロよ。

 

次回は、バブルソートよりも少しだけ早くソーティングが可能になる方法を紹介するにゃ。

 

 


nice!(0)  コメント(0) 

日独外相会談 機密情報保護協定などの協議促進で一致 NHK [ひとこと言わねば]


nice!(0)  コメント(0) 

中小企業狙ったサイバー攻撃深刻化 知らぬ間に情報流出も NHK [ひとこと言わねば]


nice!(0)  コメント(0) 
前の10件 | -