2012-04-09

データやスクリプト解析にちょこっとPerlをいじる程度ですが、興味本位で借りた下記の本が思いのほか分かりやすかった。自分の頭の整理をするために内容をまとめてみました。著書には、分かりやすい図と実際のサンプルコードも記載されているので、本ページはあくまでメモ程度。

プログラミングの宝箱アルゴリズムとデータ構造第2版

作者: 紀平拓男,春日伸弥
出版社/メーカー: SBクリエイティブ
発売日: 2011/03/26
メディア: 単行本
購入: 15人クリック: 255回
この商品を含むブログ (31件) を見る

【ソート】
最適なソートはケースバイケース。選ぶ基準は、(1)計算量、(2)計算に必要なメモリの量、(3)安定性、(4)プログラムのコード量、などがある。「どういう状況でソートを使いたいか？」をしっかり把握することが大切。コーディングが楽なものから検討して条件にミートするものを選ぶのも一つの方法。迷った場合は、取り合えずクイックソートかマージソートを使うのがお勧め。

< バブルソート >
先頭から順番に見ていって、左右の並びがおかしいところがあれば入れ替える。最後までたどり着いたら再び先頭に戻って繰りかえす。一度も並べ替えをすることなく先頭から最後まで見終わったら終了する。

< クイックソート >
ある適当な値を決めて、それよりも大きいものは後ろへ、小さいものは前へ移動する。２つに分けたそれぞれのグループの中でまた適当な値を決めてそれよりも大きなものは後ろへ、小さいものは前へ移動する。上記作業を繰りかえし、それ以上グループ分けできなくなったら終了する。（＊）最も良く使われるソートアルゴリズム。C言語の標準ライブラリ「qsort()」という関数ではクイックソートを利用。関数ポインタを使わなければいけない点に注意する。

< マージソート >
全体を小さなブロックに区切る（全体を２つに分ける。分けた２つをそれぞれ２つに分ける。ブロックの大きさが完全に１になるまで分け続ける。）。各ブロック同士をソートしながらつなぎ合わせて、中くらいソート済みブロックにまとめる。同じように中くらいソート済みブロック同士をマージし、大きなソート済みブロックにまとめる。上記を繰り返し、全体がソート済みになったら終了する。

< コームソート >
先頭から遠く離れた距離にある要素同士を比較しながら入れ替える。最後までたどり着いたら再び先頭に戻り、比較する距離を短くして繰りかえす。比較する距離が１になり、かつ、一度も並べ替えをすることなく先頭から最後まで見終わったら終了する。（＊）一回ごとにギャップ（距離）を縮める度合いを「縮小率（だいたい１．３が良いらしい）」という。

< 単純挿入ソート >
ソートがされていないブロック内の要素を一つ取り出し、ソート済みのブロックにリニアサーチを行い、順序のルールに従って適切な位置に挿入する。上記を繰り返し、ソートがされていないブロックがなくなったら終了する。（＊）ほとんど整列が終わっているデータに対して非常に効率が良く、他のソートアルゴリズムと組み合わせて使うことがある。

< ２分挿入ソート >
ソートがされていないブロック内の要素を一つ取り出し、ソート済みのブロックにバイナリサーチを行い、順序のルールに従って適切な位置に挿入する。上記を繰り返し、ソートがされていないブロックがなくなったら終了する。（＊）単純挿入ソートとアルゴリズムの性質は同じ。リニアサーチとバイナリサーチの違いを反映し、データ数が大きい時に有効。

【サーチ】
ランダムに並んだ配列データをサーチするにはリニアサーチが最も高速。データに存在する何らかの周期性や特徴を利用すること（アルゴリズム）で高速化が可能。ただし、データをあらかじめソートする必要があるため、同じデータに対して繰り替えしサーチを行う場合により適している。なお、文字列でもstrcmp()関数などを利用して大小（前後）関係を比較可能である。

< リニアサーチ >
先頭の数値から順番に調べていって、探している数値と同じかどうかを確かめ、探している数値が見つかればその場所（添え字）を返す。（＊）リスト構造のデータの場合、頻繁に検索される値を先頭に集めることで「実際的」にリニアサーチによる検索効率をあげる事が可能。C++標準ライブラリでは、find()関数がリニアサーチに相当する。サーチを始める直前に配列の最後の値を「目的の値」に入れ替えることで、添え字の範囲チェックの確認を省略可能。

< バイナリサーチ >
配列のある位置(An)の要素の値と目的の値を比較する。目的の値よりも小さければそれよりも小さい位置、目的の値よりも大きければそれよりも大きい位置(An+1)の要素の値を目的の値と比較する。上記を繰りかえす。ただし、[An, An+1]の範囲で次の位置(An+2)を決めるとする。目的の値が見つかれば終了する。（＊）バイナリサーチをするにはまず配列をソートする必要がある。C標準ライブラリではbsearch()、C++標準ライブラリではBinary_search(), lower_bound(), upper_bound(), equal_range()がバイナリサーチに相当する。

【リスト】
構造体やクラスを使って、データが追加されるたびにmalloc()関数(C++ならnew演算子)でメモリを確保し、既存のリスト（リストの要素「ノード」）の末尾に追加、もしくは、ノードの追加・削除も前後のノードのポインタを書き換えることでリストリンクが可能。末尾のノードには、素地のノードを指し示すポインタの代わりにNULLが入る。データの和がいくつあるのか最初にわからない場合に特に有効。ただし、malloc()/free(), new/deleteなどのメモリアロケーションの処理コストや、メモリ断片化に注意する必要がある。また、一連のデータをリストリンクに従って順番にたどっていくことしか出来ない（データに飛び飛びにアクセス出来ない）。

【スタック】
データを格納する時は必ずデータ配列の末尾に追加する。反対にデータを取り出すときも必ず配列の末尾から取り出す。このやり方に従って扱われるたくさんのデータの集合を「スタック」と呼ぶ。スタックを構成するには、スタックの元となる（実際にデータを格納する）配列の他にスタック頂上を指すポインタを用意する必要がある。

スタックの基本動作は、(1)スタックにデータを追加する：スタックの頂上の次の位置にデータを格納し、同時にスタック頂上を指すポインタを１つだけ進める。スタック頂上にデータを追加することを「プッシュ」するという。(2)スタックからデータを読み出す：スタック頂上を指すポインタの位置からデータを読み出す。(3)スタックからデータを削除する：スタック頂上を指すポインタを１つだけ戻す。スタック頂上からデータを取りのぞくことを「ポップ」するという。データの読み出しと削除は同時に行われることが多く、(2)(3)をまとめてポップと呼ぶこともある。（＊）利用例として、カッコの対応関係を調べたり、逆ポーランド記法した四則演算が挙げられる。

【キュー】
キューにデータが追加されるとデータはキューの最後尾に入る。キューからデータが取り出される時はキューの先頭から取り出させる。キューのために用意する配列サイズを固定し、キューの末尾が配列の最後尾に達した場合に配列の先頭に戻り、そこから再びデータを格納する「リングバッファ」という方法もある。キューを構成するには、十分なサイズの配列と、キューの先頭と末尾を示すポインタを１つずつ用意する必要がある。

キューの基本動作は、(1)キューにデータを追加する：キューの末尾を指すポインタの次の位置にデータを格納し、同時にキュー末尾を指すポインタを１つだけ進める。もし、配列の末尾を越えたら再び配列の先頭に戻る。キューにデータを入れることを「エンキュー」もしくは「プッシュ」と言う。(2)キューからデータを読み出す：キューの先頭位置から値を読み出す。(3)キューからデータを削除する：キューの先頭位置を指すポインタを１つだけ進める。もし配列の末尾を越えてしまったら再び配列の先頭に戻る。キューからデータを読み出し＆削除は「デキュー」もしくは「ポップ」という。（＊）利用例として、バッファ（ネットワークから流れてくるデータやWindowsのメッセージ、印刷ジョブなど次々に発生するデータや要求を順番に適切に処理するまでの間、一時的に溜めておく場所）が挙げられる。

【再起呼び出し】
ある関数Aの内部で自分自身（関数A）を呼び出して処理を繰りかえすこと。for文やwhile文では、直後に続くコードブロックが繰り返し実行されるのに対して、再起呼び出しでは呼ばれた関数の中身が丸ごと繰り返し実行される。例えば以下のような動作である。
===========================
int 取り出し(箱) {
　箱を開ける；
　while(空になるまで）{
　　箱の中身を１つ取り出す；
　　if（取り出したものが箱）
　　　取り出し（箱）；
　｝
　return 0;
｝
=============================
再帰を使う時の典型的な失敗は、プログラムが永遠に停止しないこと。再帰は、(1)同一処理を繰りかえす、(2)戻り値を再度１の処理に使う、(3)最後の戻り値がどのデータ入力から開始しても同じになることが保障できる、ことが大事。階層構造があり、単純なforやwhile文でかけない時に役立つ。逆に、配列やリスト構造は階層構造を持たないため、積極的に再帰を利用する必要がなく普通のFor文で処理可能である。

【ツリー構造】
リスト構造を少し変えて、「次のノード」を複数持てるようにするだけで実現出来る。持てるノード数が２つのみの場合は、特に２分木と呼ばれる。前のノードは「親ノード」、次のノードは「子ノード」同じ親を持つノードは「兄弟ノード」、子を持たないノードは「葉」、ツリー全体の根本が「根」という。ツリー構造は、全体の一部を取り出しても同じツリー構造（同じルールの分岐構造）になっている。なお、前節の「再帰」は「全体の一部を取り出しても同じような構造をしているデータ（入れ子のようになっているデータ）」を扱うのに向いているため、ツリー構造の処理は再帰が適している。

ツリーはリスト構造と同様、ノードの追加や削除が簡単である。また、データは分岐のルールに従って既に構造化されているため、例えば２分木のサーチもバイナリサーチと同様にO(LogN)となる。２分木のメリットを最も上手に利用しているのが、C++標準ライブラリなどの「マップ」である。マップでは、「”キー”と”値”をセットにして１データとして２分木へ挿入し、キーにある値を指定して検索を行えば、そのキーに対応する値をすばやく検索可能」になる。”キー”に使うデータ型は、値の大小関係さえ定義出来ればいいのでstrcmp()関数などを利用して文字列をキーに出来る。

２分木検索が理想的になるのは、２分木の構造が左右にバランスが取れた形に広がっていて、根から葉までの高さが低いことが重要である。ツリーが常にバランスの取れた形になるようにする方法として、AVL木、B木がある。

< AVL木 >
ノードの追加や削除によって、木全体の子孫間で高さが２以上の差をもった場合に、最も高い子孫の上位にあるノードの親子関係を変えて（回転させて）、（子、親、子）→（孫、子、親）、高さを１以内になるように維持している。

< B木 >
市販のデータベースエンジンにほとんど使われている。例えば、ページサイズが４のB木の場合、追加されたデータによってあふれ出る（４→５）場合に、新たなページを作成し、５つのデータの中の真ん中の値を親ページに、残りの４を２つずつ分けて子ページに振り分けるとともに、親ページに入れた値の左側からは左側のページへリンクを、右側からは右側のページへリンクをはる。B+木では、全データをすべてのデータが最下層（葉ページ）に格納されているため、シーケンシャルアクセスが高速化されている。

【マップとハッシュ】
< ツリーマップ >
”キー”と”値”の構造体を保持する２分木を作る。各ノードはキーの大小関係に基づいて整理する（もしもキーが数値でないなら、何か適当な大小関係の規則を用意する）。検索時には、”検索キー”と同じキーをもつノードを探し出し、そこに格納されているデータを取り出す。

データの追加と削除が比較的高速、データの検索も比較的高速。ただし、データの分布や挿入の順番によって処理速度が大きくかわるなどの問題もある。ツリーマップは、C++標準ライブラリのmapクラス、Javaのmapクラスがある。

< ハッシュマップ >
(1)ハッシュ表を用意する：データへのポインタを格納する配列を用意する。(2)ハッシュ値を決める：データ（文字列）群を（望ましくは線形に、すなわち１対１で）ハッシュ表のサイズ内の数値に変換する関数を定義する。例えば、CRC16/CRC32などの巡回符号方式などフリーのCRC計算ライブラリを用いる。(3)データを格納する：ハッシュ値の対応する位置にデータへのポインタを格納する。(4)データを検索する：検索キーのハッシュ値を計算し、ハッシュ値の該当する位置（ポインタ）を参照する。(5)データを削除する：ハッシュ値を元にデータの位置を特定してそこにあるデータを取り除く。

ハッシュ値が重複することがあるため、(1)同じハッシュ値をもつデータをリスト化、もしくは、２分木にする、(2)ハッシュ値の衝突が生じたらあとから来たデータを前のデータのすぐ次の位置、もしくは、k^2番目に位置にいれて、衝突が起こらなくなるまで続ける（再ハッシュ）、などの方法がある。ハッシュ表の９割程度が使用済みになると、衝突回数が爆発的に増えて実用上の支障が出るため、メモリを十分に用意することがハッシュマップのパフォーマンスを確保する上で重要。

メモリの消費量は多いが、検索スピードはO(1)で高速。Javaには標準のハッシュマップクラスであるHashMap、Hashtableというクラスで、データとなるクラスhashCodeメソッドを利用してハッシュ値を生成可能。C++には標準のハッシュマップクラスが（まだ？）ないが、準クラスライブラリに一部であるSTLを拡張したSGI性のSTLではhash_mapというクラスや、マイクロソフト製のMFCのCMapクラスがハッシュマップクラス。ハッシュテーブルの使用率が増加すると、パフォーマンス低下を防止するためにハッシュテーブルを自動的に拡張するように設計されている。

【浮動小数点と数値計算】
数値計算で問題となる「誤差」は、以下の４タイプ。

< 丸め誤差 >
float型では、例えば「0.1」と「0.100000001」は区別が出来ずともに「0.1000000014901116120」という和になる。

< 桁落ち >
非常に近い値、例えば「1.0000101」と「1.0000100」を引き算した時に、「0.0000001」となるはずが「0.0000001192093」となり、誤差率（20パーセント）が大きく、有効数字が極端に減少する。

< 情報落ち >
「1000000」に「0.00001」を加えても「1000000.00001」とはならず「1000000」のままになる。C言語ではヘッダ内で、float型、double型はそれぞれ「ELT_EPSILON」、「DBL_EPSILON」という定数に浮動小数点判別限界値が定義されている。

< 打ち切り誤差 >
無限級数の計算などを有限で打ち切ることで発生する誤差。時間と精度のトレードオフ関係がある。

【文字列検索】
基本は、先頭から順番に１つ１つ文字を調べていき、文字列パターンが一致するまで進む。検索対象となる文字列の長さをm、検索キーの長さをnとしたときに計算量はO(mn)となる。検索効率を上げるために、KMP法やBM法がある。

< KMP法 >
文字列を比較している時に、「現在進行中の文字列の比較が万一失敗したときに、次にどこから再比較を開始すればいいのか」を把握させることで、検索対象文字列の同じ場所を重複して調べる必要がなくなり、計算量オーダがO(n)となる検索アルゴリズム。ただし、アルゴリズムが複雑になる分のオーバーヘッドも大きい。検索のためのポインタが逆戻りしないという特徴があるため、ディスクやテープの外部ストリーム上のデータを検索するのに用いられる。

< BM法 >
文字列をパターンの”後ろから前に向かって”比較する検索アルゴリズム。文字列を比較中に不一致が生じた文字列が検索キーのパターンに一切含まれない文字の場合に、検索キーの先頭を一気に次の位置へと飛ばすことが可能になる。不一致がパターンの後方で生じやすいため、一度に移動できる量が多く、実用レベルで優れたパフォーマンスを示す。

【バックトラック法と幅優先検索】
< バックトラック法 >
再帰を利用して「試行錯誤」をもれなく行うアルゴリズム。仮定に仮定を重ねてひたすら突き進み、処理が行き詰って上手くいかなくなったら、別の選択肢にすすむために後戻りしてやり直す方法。

< 幅優先検索法 >
動作の基本は、(1)１ステップで実現出来るすべてのパターンを試す。(2)次に２ステップで実現出来るすべてのパターンを試す。(3)３、４、、、で実現出来るすべてのパターンを試す。解に至るまでの最短ルートを試行錯誤によって求めることが可能。「キュー」を用いて実装することが一般的である。

【動的計画法】
全体をいくつかの小問題に分割して、先に一括して小問題の解をすべて得てから、最終的にそれらを組み合わせて問題の解決役立てる。「動的計画法」は、あまり数の多くない小問題に分割可能である場合に有効。

give_up_easyの日記

アルゴリズムとデータ構造

珠玉のプログラミング