Aritalab:Lecture/JSBi/Test/CompSci
m (→探索に用いるもの) |
(→ソート・整列) |
||
| Line 83: | Line 83: | ||
==ソート・整列== | ==ソート・整列== | ||
| − | * クイックソート ... 与えられた配列をだいたい半分にしながら並び替え。平均的計算量O(n log n), 最悪はO(n<sup>2</sup>) | + | * クイックソート ... 与えられた配列をだいたい半分にしながら並び替え。平均的計算量O(n log n), 最悪はO(n<sup>2</sup>)。実用上いちばん速いといわれる |
| − | * マージソート ... 与えられた配列を正確に半分にしながら並び替え。計算量は常にO(n log n) | + | * マージソート ... 与えられた配列を正確に半分にしながら並び替え。計算量は常にO(n log n) |
| − | * バブルソート ... 配列中で隣り合った組を発見するたびに入れ替えをおこなう。計算量はO(n<sup>2</sup>) | + | * バブルソート ... 配列中で隣り合った組を発見するたびに入れ替えをおこなう。計算量はO(n<sup>2</sup>)で非実用 |
| − | * 挿入ソート ... 新しく追加する要素の位置を、配列中をスキャンして探す。殆ど並んでいるデータを微修正するのには使える。。計算量はO(n<sup>2</sup>) | + | * 挿入ソート ... 新しく追加する要素の位置を、配列中をスキャンして探す。殆ど並んでいるデータを微修正するのには使える。。計算量はO(n<sup>2</sup>) |
| + | |||
| + | {| class="wikitable" | ||
| + | ! 関数名 || 特徴 || 平均計算量 || 最悪計算量 || 順番の保存 | ||
| + | |- | ||
| + | | クイックソート || 実用上最速 || O( n log<sub>2</sub>n ) || O( n<sup>2</sup> ) || no | ||
| + | |- | ||
| + | | マージソート || 外部記憶に便利 || O( n log<sub>2</sub>n ) || O( n log<sub>2</sub>n ) || yes | ||
| + | |- | ||
| + | | バブルソート || 実用ではない || O( n<sup>2</sup> ) || O( n<sup>2</sup> ) || yes | ||
| + | |- | ||
| + | | バケツソート || 対象サイズが既知の場合 || O( n ) || O( n ) || yes | ||
| + | |} | ||
==大量データの表現・格納・処理== | ==大量データの表現・格納・処理== | ||
Latest revision as of 13:14, 24 November 2012
Contents |
[edit] ハードウェア
[edit] 計算機のCPUについて
CPU (Central Processing Unit) とは中央演算処理装置のこと。略してプロセッサ。 一番の基本は01のバイナリ命令を解釈して演算を行う部分 (ALU: Arithmetic Logic Unit) と一時的に値を格納するレジスタが、主記憶メモリとバスでつながれた構造を持つ。
一般的にマルチコアと呼ばれるプロセッサは、演算処理部分とレジスタのセットを複数が、単一の主記憶につながった構造を持つ。最近耳にするGPU (Graphics Processing Unit) は、画像処理用にメモリ間のデータ転送や浮動小数点の演算を並列処理で高速化する装置のこと。以前はグラフィックアクセラレータなどと呼ばれていたものが汎用化したもの。
[edit] プログラムはどうやって動くのか
プログラミング言語（ソースコード）は人間が読んでわかる形だが、最終的にCPUが扱う機械（マシン）語レベルではバイナリ(01)列。 人が扱う高級言語から、機械語に「翻訳」する手法には大きく分けて2種類ある。
- コンパイラ ... ソースコードを特定の計算モデル上で解釈し、処理を最適化する翻訳
- インタープリタ ... 原則、ソースコードのコマンドをマシン語レベルの処理にそのまま対応させる翻訳
コンパイラとインタープリタは翻訳手法であり、言語そのものと結びつく概念ではない。 ただし一般には、プログラムを書いてすぐに動く言語(Lisp, Perl, Ruby, Python, etc.)と、一度「コンパイル」して実行形式ファイルを作成する言語(C, Java, Fortran, etc.)に分けられる。
[edit] データ構造
計算機上にデータを記述する際に、利用形態にあわせて適切な表現法を用いると効率よく処理できる。
[edit] 基本データ構造
- 配列 ... 決まった個数のデータを格納する。データのアドレス（番地）は整数で指定。
- リスト ... 個数が大きく変化するにあわせて伸長・収縮が自在にできる。
- スタック ... 今は昔になってしまった、ばね式のコイン入れの仕組み。最後に入れた要素が最初に取り出される。
- キュー ... 先頭から入れ、末尾から取り出す筒のこと。最初に入れた要素から順に取り出す。
[edit] 配列とリストの違い
プログラミング言語には配列 (array) という概念があります。メモリ空間の一定領域を確保し、ブロックとして利用するのが配列データ構造です。配列には大きな欠点があります。細切れになったメモリ空間を効率良く利用できないのです。そこで小さな領域を数珠のようにつなぐ対策が考えられます。それがリスト構造です。
| 名前 | 構造 | 利点 | 欠点 |
|---|---|---|---|
| Array | 一定領域のブロック | x番目の要素位置をすぐに計算できる | まとまった記憶域が必要で、全体サイズの変更は困難 |
| List | 細切れ領域をつないだもの | 細切れの記憶域を活用でき、挿入や削除が楽 | x番目の要素は辿らないとわからない |
リスト構造の欠点はアクセスの手間です。配列で10番目の要素を知りたい場合、配列であれば先頭アドレス＋データサイズ×10 によって値が格納されるアドレスを計算できますが、リストはこれができません。要素を１つずつ辿っていく必要が生じます。
[edit] スタックとキューの違い
スタック、キューともリスト構造の一種です。一昔前になりますが、バネ式のコインケースという商品がありました。硬貨を一枚ずつ上から入れることができますが、取り出すときも上から一枚ずつしか取り出せません。これがスタックです。それに対し、一枚ずつ入れたものを入れた順に反対側から一枚ずつ取り出せるようにしたものがキューです。
| 名前 | 動作 | 用途 |
|---|---|---|
| Stack | 先入れ後出し (LIFO: last-in first-out) | 深さ優先探索 |
| Queue | 先入れ先出し (FIFO: first-in first-out) | 幅優先探索 |
[edit] 探索に用いるもの
- ツリー ... 代表的なものは二分木。構造を絵に描くと一番よく理解できる。 頂点数がn個ある場合、枝の数はn-1本になる。
- ハッシュ ... 各要素の値から一定のルールで整数値（ハッシュ・キー）を計算し、その値を元に配列中に格納する手法。実用的。
[edit] 二分探索と木構造
配列の中身が既にソートしてあり、初めから末尾まで昇順になっている場合を考えましょう。ある要素が配列の中に含まれるか判断するには、二分探索という手法を使えます。
- 二分探索
- 探す要素を key とし、配列 V の先頭と最後の位置を記録する h = 0, t = N-1 (配列サイズ)
- 真ん中の要素 x = V[(h + t) / 2] と key を比較する
- 一致していたら終了
- 一致していない場合
- x が key より大きかったら key は 先頭から x までの中にあるはず。t を x で置き換える
- x が key より小さかったら key は x から末尾までの中にあるはず。h を x で置き換える
- t = h になっていたら終了
- ステップ2に戻る
この手法は候補の数を半分ずつに減らします。つまり、要素の数が N 個あったら log2N ステップで目的とする要素 key の有無を調べられます。
この手法をリストに対しておこなえるようにするのが木構造です。木構造は二分探索の手順をデータ構造として表現した形になっています。ハッシュ表は配列とあわせて用います。ハッシュ関数は入力 key にたいして格納される位置 x を返すので、実用上、定数時間（データ量に比例しない一定時間）で要素の検索ができます。
| アルゴリズム | データ構造 | 探索に要する時間 |
|---|---|---|
| 線形探索 | リスト、配列 | N |
| 二分探索 | 木、配列 | log2N |
| ハッシュ探索 | 配列とハッシュ関数 | 定数時間 |
[edit] ソート・整列
- クイックソート ... 与えられた配列をだいたい半分にしながら並び替え。平均的計算量O(n log n), 最悪はO(n2)。実用上いちばん速いといわれる
- マージソート ... 与えられた配列を正確に半分にしながら並び替え。計算量は常にO(n log n)
- バブルソート ... 配列中で隣り合った組を発見するたびに入れ替えをおこなう。計算量はO(n2)で非実用
- 挿入ソート ... 新しく追加する要素の位置を、配列中をスキャンして探す。殆ど並んでいるデータを微修正するのには使える。。計算量はO(n2)
| 関数名 | 特徴 | 平均計算量 | 最悪計算量 | 順番の保存 |
|---|---|---|---|---|
| クイックソート | 実用上最速 | O( n log2n ) | O( n2 ) | no |
| マージソート | 外部記憶に便利 | O( n log2n ) | O( n log2n ) | yes |
| バブルソート | 実用ではない | O( n2 ) | O( n2 ) | yes |
| バケツソート | 対象サイズが既知の場合 | O( n ) | O( n ) | yes |
[edit] 大量データの表現・格納・処理
[edit] 関係データベース
エクセルのような表を組み合わせてデータを表現する。表を作る際に最低限必要な情報だけを記述し、残りは表計算によって導出する。関係演算と呼ばれる系では、集合演算に加えて、表からの行・列の選択(select, project)、表の結合(join)により汎用的な論理体系と同等の表現能力を持つことが知られている。
[edit] オブジェクト型
まとまったデータをカプセル化して隠蔽する概念をオブジェクト指向と呼ぶ。 各オブジェクトは、その中身にアクセスして処理するためのメソッドを備えており、この概念を取り入れたプログラミング言語 (例えばC++, Java)やデータベースが開発されている。
[edit] クラスタリング
- k-近傍 (nearest neighbor) ... 各データから最も距離が近いk個を選んでクラス分けをする
- 自己組織化マップ ... 各データを最も近い要素に少しずつにじり寄らせていってクラス分けをする
[edit] 機械学習
- サポートベクトルマシン (SVM) ... 平面上にばらつく2群を直線で分けるには、両群の各点からその直線におろした垂線の足の長さを最大化する場合が最適になる（マージン最大化）。これを多次元に拡張し、マージンを最大にする超平面を探すアルゴリズムをSVMという。近年はデータ集合を非常に高次元の特徴空間に射影し（射影する関数をカーネル関数と呼ぶ）、特徴空間上で超平面による分割をおこなう手法が主流。
- ニューラルネットワーク ... 脳のシナプス回路をモデルにして作られた機械学習手法。タンパク質の二次構造予測に良く用いられる。
[edit] 状態遷移
[edit] オートマトン
○と→を結んだ状態遷移のチャートそのもの。
[edit] マルコフ連鎖 (Markov chain)
○と→を結んだ状態遷移で、次に移動する場所を現在いる状態のみに依存して（つまり今までどの状態を巡ってきたかを無視して）決定する場合をマルコフ連鎖という。
