« 目玉のお●じ | トップページ | 困り果てましたよ、ホント! »

2008年4月 8日 (火)色々あります

おはようございます。本日の当番、プログラマのY.Tです。

今回は「答えは1つではない」というお話です。

同じ結果を出すプログラムでも色々な方法があるのです。
例えば、ソートプログラム。
ざっと挙げるだけでも、バブルソート、シェーカーソート、
クイックソート、バケットソート、etc
色々な方法があります。

では私の経験を交えて軽く説明を。

例えば、バブルソート。
バブルソートとは、値を1つずつ比較して条件を満たしていれば交換する。という方法です。
誰もがまず一番最初に思いつく方法ですね。
実際、私も最初に作ったのはこれでした。
これは、確実ですが処理時間が遅いです。
1つずつ比較するのですから当然です。

これは駄目だということで次に試したのが、バケットソートです。
バケツソート、分布数えソート、などともいいます。
バケットソートとは、データが取り得るすべての値のバケットを用意しておいて、対応するバケットに詰めていき、詰め終わったら順番にバケットから値を取り出していく、という方法です。

バケットソートはバブルソートに比べると相当早いですが、欠点があります。データの取り得る値分のバケットが必要となるのです。

例えば、4バイトのデータ( 4 100000000 1 )という3つの数字をソートしようとすると最大値の100000000。つまり、4*100000000バイト、約400メガバイトのメモリが必要となるのです。たった3つをソートするだけで、これではやってられませんね。
私の場合、最初は自分で思いついて何も考えずに試したのですが、そのPCのメモリが256メガの貧相なPCでして・・・
どうなったかはご想像にお任せします。

その欠点を解決したものがラディックスソートです。
ラディックスソートとは・・・

・・・とまぁ、こんな感じにただ単にソートプログラムといってもたくさんある訳です。投げっぱなしですが、恐ろしく長くなるのでこのあたりで。本当に軽くしか説明していないし、かなり分かりにくいと思いますのでもっと詳しく知りたい方は検索してみてください。いっぱい出てきます。

さて、一口にソートプログラムといってもたくさんありましたよね?
これがプログラムの面白い所で、今回言いたかった事です。
そうです。答えは1つではないんです。
「でも結局は皆、一番速いプログラムを使うんじゃないの?」
と、思われると思います。
確かに、より良いものを求めるなら答えは一つになってしまう事は多々あります。ですが、人それぞれの方法があるから考えるのが楽しいし、分からなかったことを理解した時や、自分で新しい方法を思いついた時はめちゃくちゃ嬉しいです。

ずっと思い出せなかった人の名前を思い出した時の様にスッとしますよ。皆さんも私と一緒に楽しい楽しいプログラムをしてみませんか?

follow us in feedly
result = encodeURIComponent( "http://www.accessgames-blog.com/blog/2008/04/post_3876.html" );document.write( "result = " , result );&media=https%3A%2F%2Ffarm8.staticflickr.com%2F7027%2F6851755809_df5b2051c9_z.jpg&description=Next%20stop%3A%20Pinterest">

| | コメント (0) | トラックバック (0)

« 目玉のお●じ | トップページ | 困り果てましたよ、ホント! »

プログラマー」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック


この記事へのトラックバック一覧です: 色々あります:

« 目玉のお●じ | トップページ | 困り果てましたよ、ホント! »