〜arqeeの技術コラム〜
Our diAry EntrY


discription

Birthday
6/Aug/1983

Handle
arqee

2004年08月
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
プロフィール
  • プロフィール画像
  • アイコン画像 ニックネーム:arqee
読者になる
Yapme!一覧
読者になる
Telnet日記「Telnetでスクリプトを動かそう2-1」
  https://yaplog.jp/arqee/archive/17
シェルな話

試験とゲームのお話
update : 08 / 11 / 2004

 最近更新をサボっている私
 単純に言えば「基本情報を取ろう!」という計画のためなのだが。。。ご覧の通り既に飽きが来た模様

 毎日6時間勉強=朝3時間、夜三時間、昼C言語とやっていたのだが、すっごく楽しくない。

 仕方ないかとかって放置していた「某スライムアクション」をやってみる

 おぉ!キュートでプリティーな(死語)スライムを操作してももんじゃを倒していく姿、最高です。久々に連続2時間も遊んでしまった。トルネコなみにはまりそうです

 そいやスライムはDQ6で極めましたな。普通のスライムがマダンテ撃てます。トルネコは時の砂代わりとして活躍してくれるので、ハグレ倒すのになぜか居たのだった。

 そんなスライムとトルネコが好きな私にとってこいつはなかなかのものなですね

 そして気づけば4時。あぁ、C言語やらなきゃ。

 今回はソートアルゴリズムの検証を行っていた。

 あらら、「シェルソートがバブルソートに負けました」。バブルソートの実効時間「4秒」、シェルソートの実効時間「10秒」。。。何故だ!。。。試しに単純挿入法もやってみた。あら?実効時間が「2秒」に縮まったんだけど。。。

 なぜだろう。。。シェーカーソートも実験。うぅ。。。8秒。。。まて、バブルソートに単純挿入法以外勝てませんでしたけど。

 とりあえず、クイックソートとラディクスソートもためさにゃ=まだコーディング終わってない。

 う〜ん、基本情報で学んだアルゴリズムの話が全て壊れそうで怖い。

 一応理由を考えてみた。

 アルゴリズム的なステップ数は、シェルソート、シェーカーソート共に抜群に買っているはずです。ここで重要なのは「ソースとしての効率性」なのかも知れません。

今回の手順

15000件の乱数値(0~99)を発生させdataに格納する。
dataをrestに格納。
時間計測開始。
restに対してソートアルゴリズム読み出し
時間計測終了
ソート結果表示

↑をそれぞれのアルゴリズムに対して行っています。

 ここでふと思った。
 根本的なソース量の違いが問題なのかもしれない。
バブルソートは

for( i=0;i<MAX;i++ )
 for( j=j+1;j<MAX;j++ )
  if( a[i]>a[j] ) SWAP(a[i],[j]);

 のように可能な限り単純なのに対し、シェルソートやシェーカソートは色々なアプローチが無駄なタイムラグを生んだのかもしれない。単純挿入法もなかなか短いし(5行程度)。

 本来ならMIPSFLOPSの計算をするべきだろう。今度あたり確認してみようと思う。




Posted at 21:27 : 与太話 / this blog URL
comments(3) / up

track back
ping url
https://yaplog.jp/arqee/tb_ping/17

comment
name:

love cookie



MIPSFLOPS関係ない

Posted by:こっけー at 06 / 29 / 2008

そうそう、今回はリナックスで確認したけど、
WinowsNT系ならメモリは500KB以上必要になるんですよね。これは使いすぎ。

Posted by:arqee at 08 / 12 / 2004

 ラディクスソートとクイックソートを作成してみました。

 ラディクスソートは私なりの考えで効率化したためか実効時間は「0.5」秒。
 流石自分、ですね^^;

 クイックソート「0.7」秒。さすがです。

 でもラディクスソートの方はメモリ使いすぎな設計なので、大変です。

 まぁ、再帰使うクイックソートも似たようなものでしょ。

 マイラディクスソートの効率は
N * m(固定)です。
配列入れ替えは考慮してません。

今回条件下では
15000 * 2
という 驚異的な結果になります。
参照や代入を考慮しても
15000 * 4 + 20 * 2
となります(はずです)。
バブルソート((15000+1)/2*15000 * 3)のおよそ3000倍から9000倍の速度となるのです。

でも通常のソートの10倍メモリを使います。
今回なら
15000 * 2 * 10 + 10(バイト)
293KBものメモリを利用するのです。

クイックソートの説明は再帰なので省きます。

Posted by:arqee at 08 / 12 / 2004

blog+yapeus=yaplog