スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

個別のアルゴリズムをつつく3-マージソート。一旦分割♪これマジだよぉ。

このアルゴリズムは 合併法 の考え方をもとに作られたアルゴリズムなんだ。 考え方をリンク先でつついてからこのアルゴリズムをつついてね♪
合併法はつついた?じゃあ、マージソートを一緒につつこう! マージソートの手順は次の通りだピヨォ。


【マージソートの大まかな流れ】
  1. 扱える大きさまでデータを二分割していく。データをつついて割っていくんだ。
  2. 細かに分かれたデータをソートしながら合体させていく。小さいから簡単♪
  3. 全てのデータ片を合体したらあら不思議。データが整列しているよ♪


てな寸法さ。
ドリィちゃん「相変わらず大雑把ね。」
でも、マージソートってイメージはこんなもんじゃない?
ドリィちゃん「まぁね。どうせこの説明は実装のおまけだからね。」
そっそれは酷い・・・でも言い返せない。まぁ、とにかく言語との実装を見て見て♪
ドリィちゃん「ちょっと、拗ねたの。もぉ・・・。仕方がないわね。私が説明しておくわ。
このソートはバブルソートよりも効率がいいと言われているわ。何故かというと、比較回数が少なくなるから。2分割にして比較するところがポイントなんだけど、 比較する場合は両方の先頭だけ比較するだけだし、途中で片一方がなくなったとき、後は残った方を出力するだけになるからね。その辺に注意してコードを見ればいいわ。後、このソートは再帰が伴うわ。覚悟してね。」



【言語ごとの実装例】
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

アルゴリズムの方法論をつつく5-合併法。小さな事からコツコツと

今回は合併法という考え方をつつくピヨ。合併法というのは分割統治法という考えの元で作られたソートアルゴリズムの分類なんだ。 分割統治法については後でソフトウェア工学の記事で詳しく説明するピヨ。 だから今回は簡潔に囀るね。
分割統治法とは問題を解決できない時は、細分化して考えれば解けるという考え方ピヨ。例えば、1兆件のデータをソートする状況を想像してみて。1兆件ものデータをどうやってソートするのだろう。何故この件数が問題なのかというと、 メモリに格納できないから普通のソートアルゴリズムは使えないからなんだ。そこで活躍するのが合併法のソートアルゴリズムなんだ。 合併法ではこのような時は、「 小さく小分けしてソートし、後でそれをまとめればいいじゃん。 」と考えて実装するピヨッ!部屋が散らかった時、部屋を4つの区画と考えて、1区画1日掃除するのと同じピヨね。
という事で、これから個別のアルゴリズムについてつついていくピヨォ~!楽しみにしてね♪

テーマ : 情報処理技術
ジャンル : コンピュータ

個別のアルゴリズムをつつく2-挿入ソート。ちょっと右へ寄ってくださる?

基本的な考え方は アルゴリズムの方法論をつつく4-挿入法。あるべき位置へおけば整列完了! 見てね♪
リンク先で紹介したトランプのイメージでアルゴリズムを捉えるいいよ。もし、それでもピンとこない人は、紙を細かく切ってそこに0~9の数字を書いて、実際にソートしてみるか、満員電車か映画の座席に座るとき「ちょっと右へよって」とおばちゃんやおっちゃんが言っている光景を想像しよう。
でも一番理解が早いのは実装を見る事ピヨ♪これからここへリンクを張っていくよ。楽しみにしてね。


【言語別挿入ソートの実装例】

テーマ : 情報処理技術
ジャンル : コンピュータ

アルゴリズムの方法論をつつく4-挿入法。あるべき位置へおけば整列完了!

今回はまたソートへ戻って挿入法という考え方をつつくピヨ♪ 挿入法の考え方は・・・

データが増える毎に正しい位置へ格納すれば整列している状態を保てる。

という考え方なんだ。言葉では分かりにくいからトランプを思い浮かべてみよう。 トランプをシャッフルして、1枚づつ引いたカードを横へ並べる方法を考えてみるピヨ。ここでは、左から右へ数字が大きくなっているとルールを決めるとしよう。この場合、まず4を引いたとしても他のトランプはないから4をそのまま置くピヨ。

4

次に1を引いたとすると、1は4の前に置かなくちゃならないから・・・ まず4を右へ置いて1の場所を空ける

○  4

そして1のカードを置く

1  4

そしてまた引くと今度は6だった。6の場合は4と比べて大きいから4の右へ置く

1  4  6

えいやぁー。今度は5のカードが出たピヨ。この場合は6の方が大きいから6を右へ置く

1  4   ○  6

そして空白の部分に5のカードを置くピヨッ♪

1  4  5  6

こんな具合にして挿入する位置を探して行くのが挿入法だピヨ。 説明しにくいから基本挿入法を例につついたけど、考え方は変わらないピヨ。それじゃあ、これから個別のアルゴリズムをつついていくピヨ。楽しみにしてね。

テーマ : 情報処理技術
ジャンル : コンピュータ

アルゴリズムの方法論をつつく3-番兵法。見張り番で効率UP。

前回の線形探索法 はひとつづつ調べるという単純明快なアルゴリズムピヨ。だけど、単純ゆえに効率も悪かったんだ。 具体的に言うと、最後まで到達したか毎回判定 するのが非効率的ピヨ。この末尾判定処理は 初めから求める値があればなくせる 余分な処理ピヨッチ♪ でも無いから困っているんだから、何らかの工夫が必要となるんだ。 その工夫は答えを聞けば単純明快、探している値を最後に用意すればいいんだ。ちょっとズルイ気もするけど、そうすればカウント変数はいらないピヨ。 その代り最大データ数+1の領域が必要となるピヨ。 でも、1つぐらい領域をとっても毎回判定するよりましだよね。
いつものように下にプログラム言語ごとの実装例へのリンクを張っていくピヨ。 ちびちび作っていくから、楽しみしてね♪


【番兵法(番犬法)の実装例】
  • C++・・・値固定型。

テーマ : 情報処理技術
ジャンル : コンピュータ

アルゴリズムの方法論をつつく2-線形探索。仕方がない、逐一調べよう。

新人教師田中は、今日も頭を抱えていました。それにみかねた山田は呆れつつ声をかけました。
山田「どうしたのぉん」
田中「それが、光原君のデータを探しているんですが、ディクスが書類の山で、どうやって見つけたらいいのかわかりません。」
山田「はぁ、何をしているの?まったく・・・ほんと愚図よねぇ。そんなんで教師出来るのん?」
田中「そんな事言わずにまたマジック見せて下さいよぉー」
山田「アルゴリズムをマジックという時点で見込ないわん。でも、まぁ、あちきに付き合ってくれるのなら教えてあげてもいいわよん。」
田中(恐ろしい・・・でも背に腹は代えられない!)「分かりました。僕に出来る範囲で付き合いましょう。」
山田「じゃあねぇ、こんなカオスな場合は線形探索法をやるわん。」
田中「それはどんなマジックですか?」
山田「それわねぇん。逐一探すのよん。」
田中「えっ!それだけ?」
山田「お馬鹿!整列していないデータを探す場合、逐次探索しかないでしょう!あんたが初めから机の上を整理整頓していればこんなことにはならなかったのよん。」
田中「ごもっともです。わかりました。一枚一枚書類を探しましょう。」


ストーリーを読めば何となくわかると思うけど、線形探索(別名:逐次探索)とは、その名の通り逐一データを探すアルゴリズムピヨォッ!初めからデータを整理整頓しておかないのが悪いピヨね。 このアルゴリズムは勿論、あまり効率は良くないピヨ。 だから探索アルゴリズムはソートアルゴリズムとの併用が望ましいピヨ。
線形探索法は基本的に単純なアルゴリズムなので、実装については下にリンクを張っていくピヨ。


【線形探索法】

テーマ : 情報処理技術
ジャンル : コンピュータ

個別のアルゴリズムをつつく1-バブルソート。バブルバスガール♪

今回はソートアルゴリズムの基礎バブルソートをつつくピヨ。バブルソートの考え方は

隣と比べて、隣の方が小さければ交換する。これを全ての要素に対して行えば整列している状態になる。

というものピヨ。この考えは文字では分かりにくいから例を挙げてつつくピヨ。



【例:0~9がある場合】
簡単な例としてこんなデータを整列する事を想像しよう。

ごちゃごちゃだ・・・
9  3  5  6  2  8  7  0  1  4

バブルソートでは、まずは最初の数値9と3を比べる。そして、3の方が小さいから交換するピヨ。チェーンジ!

まだまだごちゃごちゃだ・・・
3  9  5  6  2  8  7  0  1  4

次は2番目の数値9と5を比べるピヨォ。もちろん5の方が小さいからまたチェーンジ!

9「俺また移動かよ・・・」
3  5  9  6  2  8  7  0  1  4

このようにして最後まですると・・・

9「俺最後まで移動された。これって左遷ってやつかなorz」
3  5  6  2  8  7  0  1  4  9

最後まで来たらまた最初から比較交換するピヨ。

3「俺の方が小さいから交換はできないぜ」
3  5  6  2  8  7  0  1  4  9

このように比較して小さかったら何もしないピヨ。うーんもどかしいぃぃ。
後は同じようにして最後まで行くと・・・
9「おい、インドリ。俺はどうせ最後なんだから放っておいてくれ!」
ごめん、ごめん。このように比較するべき回数は減っていくから最後から決まるアルゴリズムと言えるピヨ。 この辺が初心者には難しいと思うピヨ。言語ごとの実装を用意するから デバッガで1行ごとに実行していく とわかりやすいピヨ。出来上がったらこの下にリンクを追加するピヨ。ちょっと待っててね。


【実装リスト】

テーマ : プログラミング
ジャンル : コンピュータ

アルゴリズムの方法論をつつく1-交換法。交換しあったら並んだよ。

前回は選択法という考え方をつついたから、今度は交換法という考え方をつつくピヨ。選択法の場合は、ふさわしい要素を選択するという考え方だったけど、交換法の場合は

要素の交換を繰り返せば結果として整列している

という考え方なんだ。この方法は選択法よりも抽象的なので、実際のアルゴリズムをつつかないとわかりにくいと思うピヨ。だから今回は下手な説明を止めて、交換法に属する実際のアルゴリズムをつつく事にするピヨ。

テーマ : 情報処理技術
ジャンル : コンピュータ

アルゴリズムをつつく4-プログラム言語とアルゴリズムの実装。

これから個別のアルゴリズムの実装をつついていくから、先に実装面をつついておくピヨ。
アルゴリズム実装の際には比較手段扱うデータの量を考える必要があるピヨピヨ。
初心者に比較手段を問えば大概、 「そんなの>演算子で判定すればいいじゃん!そんな当たり前の事聞くなよ。」 と返事が返ってくる。さらに生意気な奴になると、人を小馬鹿にした態度で「お前馬鹿じゃないの?」と言うピヨォー。アー腹が立つーーーーーーーーーーーーー
オッホン。鳥乱してごめん。でもよく考えてみてほしい、対象データは数値とか文字列ではない可能性があるよね。そんな場合比較演算子はあるのかなぁ?無い場合もあり得るピヨ。だから、ムカつくやつには「じゃあさ、全てのオブジェクトに比較演算子が実装されていると思ってんの?」と小馬鹿にした顔で言い返そう。この難題は、実装に使用するプログラム言語の機能によるピヨ。その対処法を列挙してみたピヨ。


【言語種類別対処法】
  • オブジェクト指向機能・・・関数のオーバーロード、演算子のオーバーロードなどを活用しよう。
  • メタプログラミング機能がある言語・・・ジェネリックを活用しよう。C++やDは標準テンプレートライブラリがあるよね。万事解決!
  • 関数型の機能を持つ言語・・・再帰やラムダ式をバリバリ使おう!
  • 何も無い言語・・・仕方がないから型別に専用関数を作ろう。

次に、データ量の場合について囀るピヨ。対象となるデータの量が多い場合格納場所を考える必要があるピヨ。何故かというと、膨大なデータ量をそのまま配列とかに格納するとメモリがパンクする。こんな場合は ファイルデータベース を使用するしかない。こうなると、作業用の場所を考える必要があり、大変困難になるピヨ。という事は当然メモリに負担をかけないような実装が要求されるピヨ。これらの2点に注意して実装する必要があるピヨォー。みんな注意してね

テーマ : 情報処理技術
ジャンル : コンピュータ

個別のアルゴリズムをつつく0-基本選択ソート。主は此処になおれ!

アルゴリズムの方法論をつつく0-選択法。何を選択するの?」の記事で選択法という考え方をつついたから、今度は具体的なアルゴリズムをつっつくピヨ♪何にしようかな・・・決めた!基本選択ソートをつつくピヨッ! 基本選択ソートは最小値を格納する場所を特定しながら選択するやり方 と考えるとわかりやすいピヨ。抽象的な説明では分かりにくいと思うから具体例を挙げるピヨォツ!

【例:0~9がある場合】
簡単な例としてこんなデータを整列する事を想像しよう。

ごちゃごちゃだ・・・
9  3  5  6  2  8  7  0  1  4

基本選択法ではまず位置を決める。もちろん0からピヨ。
0番目に入れる数値は=X
次に1番目~9番目までの数値内で一番小さい数値を探す。
一番小さい数値はもちろん0だよね。だから・・・
0番目に入れる数値は=0
でもちょっとまって!今現在9が居るピヨ。だから場所を変わってもらおう。
その結果データは次のようになるピヨ。

ちょっとは整理できたかな?
0  3  5  6  2  8  7  9  1  4 
緑色が確定した数値で、黄色は位置が変更された直後の数値だッピヨ♪
次に同じ事をすると・・・その結果は
少しましになったかな??
0  1  5  6  2  8  7  9  3  4 

これを最後まで繰り返すと・・・

0 1 2 3 4 5 6 7 8 9
となるピヨピヨね♪
具体的なプログラムは下の部分にリンクを張っていくピヨ。楽しみにしてね♪


【実装例】

テーマ : 情報処理技術
ジャンル : コンピュータ

プロフィール

Author:インドリ
みなさん、はじめまして、
コンニチハ。

ボクは、無限の夢(infinity dream)を持つネタ好きな虹色の鳥インドリ(in dre)です。
色々な情報処理技術を啄ばむから楽しみにしてね。

http://twitter.com/indori
は別人による嫌がらせ行為です。
私とは関係ないので注意して下さい。
次はなりすましブログなどをするかもしれませんが、ここ以外でブログをするつもりがないので、ここ以外にインドリのブログがあったとしても無視してください。


何度言っても分からない人がいるので、ここにコメント欄へ書き込むときの注意事項を書きます。


一、社会人としてのマナーをわきまえましょう。
一、妄想に基づく書き込みを止めてください。
一、暴言の類は書かないで下さい。
一、某誹謗中傷サイトの書き込みは彼らの妄想に基づく書き込みですから無視して、ここへ書き込まないで下さい。
一、コメント書く前に他のコメントよく読んでから行って下さい。
一、言いがかかり等の行為を禁止します。
一、その他常識的に考えて迷惑なコメントはしないで下さい。


以上のルールを守れない人のコメントは削除します。



利用上の注意
ここに紹介してある文章およびプログラムコードは正確であるように心がけておりますが、内容を保証するものではありません。当サイトの内容によって生じた損害については、一切の責任を負いませんので御了承ください。


執筆したCodeZineの記事


【VB.NETで仮想CPUを作ろう】

  1. VB.NETで仮想CPUを作ろう
  2. レジスタの実装
  3. 仮想CPUのGUI化
  4. テストドライバの改良
  5. CPUの基礎動作の実装
  6. MOV命令の実装
  7. ADD命令実装
  8. SUB命令実装
  9. INC命令&DEC命令の実装と命令長
  10. MLU命令の実装とModR/Mについて
  11. DIV命令の実装とイベント設計について
  12. 機械語駆動式 関数電卓を作ろう!
  13. 機械語駆動式 関数電卓を作ろう! 解答編(前半)
  14. 機械語駆動式 関数電卓を作ろう! 解答編(後半)


【仮想ネットワーク実装でTCP/IPを学ぼう】
  1. TCP/IPの基礎と勘所
  2. ネットワークアクセス層の勘所
  3. インターネット層の勘所
  4. トランスポート層の勘所
  5. アプリケーション層の勘所
  6. セキュリティの基礎と仮想ネットワークの仕様
  7. GDI+と独自プロトコルの定義



【並列化】
インテル Parallel Studioを使って並列化プログラミングを試してみた
並列プログラミングの効率的なデバッグを実現する「Parallel Inspector」


【TBBシリーズ】
  1. インテル スレッディング・ビルディング・ブロックの概要
  2. インテルTBBから学ぶループの並列化
  3. スレッドセーフとインテルTBBのコンテナ
  4. インテルTBBのスレッドクラス


【OpenMPシリーズ】
  1. OpenMPの基礎構文
  2. OpenMPの実行時ライブラリと並列ループ
  3. OpenMPのメモリモデルとfork- joinモデル

最近の記事
最近のコメント
月別アーカイブ
カテゴリ
Ada (9)
COBOL (5)
C (9)
C++ (11)
C# (370)
D (25)
Java (8)
Perl (1)
Ruby (14)
PHP (2)
Boo (2)
Cobra (2)
LISP (6)
F# (33)
HTML (0)
XHTML (0)
CSS (0)
XML (0)
XSLT (0)
Scala (4)
WPF (0)
WF (2)
WCF (0)
LINQ (4)
MONO (5)
Linux (0)
MySQL (0)
ブログ内検索
リンク
最近のトラックバック
RSSフィード
ブロとも申請フォーム

この人とブロともになる

QRコード
FC2カウンター
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。