日記です。なんかあれば書こうと思いますです…。
2006年10月26日(木) データ構造とアルゴリズム
地味に「アルゴリズムとデータ構造」を落としそうな気がして怖い気分になったので図書館で勉強した。
アルゴリズムというのは，まぁプログラムをやっている人なら誰でも知っているという話で，ソートの種類だとかを知ったり，学校でコンピュータを勉強している人は定期テストのためにソートの手順を丸暗記するとか実社会的にかなり無意味なことをしたことがあると思う。漏れも定期テストのために手順そのものではなくソース自体丸暗記したことがある。いや，実際は概念的にどういうことをやればいいのかながわかっていればいいと思うよ。でも「プログラムで答えよ」とある以上正しいプログラムを解答欄にかかなきゃ○もらえないって話で正しいってどういうことかというと教科書嫁ってことだったりするよorz
という格好から，プログラム＝アルゴリズムと考えられがちなんだけど，厳密にいうと違うらしくて，正確にはプログラム＝アルゴリズム+データ構造をいうらしい。ただ，プログラム＝アルゴリズムと定義しちゃう場合もあるらしい。どういうことかというと，学者によってはコンピュータを数学的なモデルとしてあらわして考える人と，コンピュータってようするにメモリやCPUがあるやつだろって考える人と二通りいて，前者だとプログラム＝アルゴリズム，後者はプログラム＝アルゴリズム+データ構造らしい。
前者はアラン・チューリング・マシンというのがそれ。アラン・チューリングたんは，イギリスの人で，ゲイでありながら第二次大戦中ドイツの暗号エニグマを解読するためのコンピュータを開発し，コンピュータのモデルの基礎を築き上げた，イギリスの英雄であり，ハードゲイの中のハードゲイだ。このモデルは当然紙の上の議論だから，このモデルにはメモリというものはあるんだけど，それを有限長として扱っていない。つまりメモリはいくらでも使えるということで，命令も数値もいくらでもこの中にいれられる。だからどんな数でも∞に計算できるとされている。さらに演算速度，つまりプログラムの実行速度も華麗にスルーしているらしい。
つまり，文字通り机上の空論みたいな格好なんだけど，アルゴリズムを純粋に，つまり紙の上では実行可能かどうかを検証できる意味では重要らしい。だからこのモデルではプログラム＝アルゴリズムというわけ。
しかし，実際のメモリとCPUからできているコンピュータだと，扱えるメモリには限りがあるから変数は束縛変数になっちゃうし，プログラムの実行速度もそのハードの仕様（俗に言うアーキテクチャ）に依存していたりして，アルゴリズムをプログラムにして放り込めばいいというわけではなくなってしまった。そのアルゴリズムが理論上正しくても実際はメモリつんでないからダメということがある。たとえば，このコンピュータでは動くゲームがあのコンピュータでは動かないとか。そこで重要になるのがデータ構造。アルゴリズムで使用するデータをどういう構造でほうりこむの？ということを議論したいらしい。講義ではこの部分をスルーされたからわからなかったんだなきっと。
データ構造には，配列とか，構造体とか，ポインタ（変数への参照のことで「ぬるぽ」みたいなものは何もさしていませんみたいなことを示す）とか，そういうものがある。もっとも基本的なデータ構造は数値と文字で，これをどのようにまとめるかが大事になるわけ。実際，成績処理プログラムだと，同じアルゴリズムでも（それぞれの人間の各科目の成績うちこんで登録するだけ）データ構造を構造体を使うと配列より楽になり，処理手順が減るから計算量が減っていいというわけ。
で，アルゴリズム+データ構造を評価するのには計算量という考え方が有効。その他実行時間という考え方もあるんだけど，これはハードのアーキテクチャに地味に依存するので客観的な評価ではないのでだめ。計算量は，文字通りデータ数nをほうりこんだとき何回プログラムが実行されるの？という考え方。基本的には「最大計算量」といって，最悪のケースの結果を使う。ちなみに計算量はO(n)とあらわす。オーエヌ，もしくはｎのオーダーとよぶ。教授はオーエヌとよんでいたのでここではオーエヌと考えてよぶことにする。たとえば，ｎこのデータが登録されていて登録されているデータを線形サーチで探す場合，配列を全部みて探すということで，最悪のケースはｎこの要素全部みてみつからなかない場合だからこのアルゴリズムの計算量はO（ｎ）であるという。ちなみに「こんにちは世界」と表示するプログラムはこれを表示するだけなので誰がどう考えても１回しか実行されないので計算量はO（１）。
一応まぁ，計算量を小さい順から大きい順にならべるとO（ｘ）のｘの部分には
1 logn n nlogn n^k 2^n
という順番で大きくなる。まぁ，n→∞にしてグラフをかくとそういう格好になるらしい。
このへんまでがテストでできなかったところだよな…。
で，次回のテスト範囲でありえそうなのは，スタック，待ち行列，連結リストの３つだろう。
一応それぞれ説明すると，これはリストというものを実現するためのアルゴリズム+データ構造。リストは，普通にnこのデータが入っていて，特定のデータを削除挿入変更できたりできますよというもの。リスト自体はマルチタスク・マルチユーザシステムなどなどで利用されている社会的用途の高いものだといえることもある。
普通に実現すると，計算量が常にO（n）かかってまどろっこしくて仕方ないのでなんとかならないかということでスタック，待ち行列，連結リストが提案された。
スタックはデータの挿入・削除を常に一番最初の要素で行おうというもの。俗に言うFIFOってやつ。ふぁーすといん・ふぁーすとあうとみたいな格好。これは割り込み処理が想定されるプログラムで大変有効で，ある処理中，別の割り込みがあったら今の処理を中断し割り込みを先に計算する，それが終わったらその割り込みをあぼーんしてさっきの処理の途中からを行うというもの。これを行えば，この処理に限っていえばデータの挿入・削除すべてO（１）で行えて効率がいいというわけ。ダイナミックなシステムむきさっ。逆にそういうことをしないシステムの場合，つまりプログラムに優先順位がきまっていない場合これを採用する意味を小一時間といつめたいらしい。
待ち行列は尻尾からデータをいれて（enqueue），先頭からデータをとりだす（dequeue）という考え方。これもデータの挿入する場所とデータをとりだす場所をポインタで参照するようにきめておけば計算量O（１）なのでウマーというわけ。ただし，データ量が多くなると∞のメモリが必要とかありえない理論がうまれてくるのでめんどい格好がある。
これら２つは，挿入とあぼーんは楽なんだけど，データの探索には結局O（ｎ）必要になるし，また，データの途中の要素にデータを挿入することができない欠点がある。そこで連結リストを使う。
連結リストは，まぁデータをセルにカプセル化してまとめようというもの。なにとなにでまとめるかというと，データ本体と次セルへのポインタでまとめる。主に通信システムのパケット（データ分割）なんかはこれが利用される。これで分割して，ポインタを参照しながら元のデータに戻そうというわけ。通信回路の通信容量は地味に限界があるというか，おそろしく少ないデータしかおくれないので，大きなデータは分割しないとやりとりできないわけね。
この構造はわりと便利で，スタックや待ち行列と比べるとデータを挿入・あぼーんする場所がきまってないからO（ｎ）かかって効率悪いんだけど，特定の箇所にデータを挿入したり，また，データの存在のあるなしを調べることもできるので確実性がある。スタックや待ち行列で通信システムを実現すると分割したデータにノイズがまじって紛失したりしてもそれに築かないでつみあげられてしまい，画像や音声だったら元の美しいものがホラーっぽいものに復元されてしまうんだけど，これだったら，ポインタを参照しながらつみあげていけばいいから，みつからなければ「復元不可能だよん」と表示して落ちればいいわけ。
重要なのはポインタで，これがむちゃくちゃだとどうにもならないから，データをあぼーんする時にはそのデータをあぼーんするかわりにそのセルをさしていた別のセルのポインタをどっかまた別のセルにつなぎかえないといけない。まぁ，当たり前だけどね。
挿入する場合も同様。
絶対単位とるぞーーー。っていうかとれなかったらまじでどうなるんだろ…地味に必修だしなこれ。がくがくぶるぶる。
ではでは。
前の日の日記を読む
次の日の日記を読む
目次へ
Webページへ
