マクロを使うという考えを1歩進めればいい。
列挙型は、まさにそれ。
たとえばfood型というudonとriceの2つの値だけとることができる列挙型を作り、
食べ物を表す時に列挙型のfoodを利用するようにすれば、
udonnと書いたときに列挙型foodがとることができない値として書き間違えを検出できる。

enum food{udon, rice, soba}
enum food lunch

Cではenumで列挙型をつくる。
上記のようにすると昼飯にはうどんか白米か蕎麦しか食べられないようになる。
ラーメンなどもってのほかである。

配列(array)

同じ型の要素を集めたもの。添え字(index)で識別する。

構造体(structure)

異なる型のデータを集めたもの。C以外の一般ではレコード構造(record structure)と言う。

メンバ(member)
- 構造体の各要素
- ほかの言語ではフィールド(field)という

ポインタ

NULLポインタ
- 何もさしていない状態

Cのポインタは3種類くらいに分類できそうだね

データ構造としてのポインタ
参照渡しのパラメタのためのポインタ
配列参照のためのポインタ

ふむふむ。

この辺はJavaを使ったことがあるので理解できる。

ポインタについては別途学習しなおす必要がありそうやなー。

2007-02-06

定本 Cプログラマのためのアルゴリズムとデータ構造 3-1

文献購読

今度はデータ構造だ。

用語

擬似コーディング
擬似プログラム
段階的詳細化(stepwise refinement)
- 擬似プログラムを細部をつめながらプログラミング言語に置き換えること

抽象データ型(abstract data type)

データの型とその型に対する一連の操作の組

例、「整数の集合」と「和集合をとる操作」の組

抽象データ型に含まれる操作は、別の抽象データ型のデータをパラメタに取れる

抽象データ型の特徴

「データの持つべき性質」と「データに施せる操作」を表す
データの実際の表現方法や、実際の操作については一切規定されていない

カプセル化(encapsulation)

データとそのデータに対する操作手続きの組にすることを、カプセル化という。

カプセル化すると

用意された操作を利用しなければデータの参照・変更ができなくなる。
プログラムの保守開発が楽になる
計算量を改善する際に、プログラム全体ではなく抽象データ型の実現部分にのみ手を触れればよくなる。

2007-02-06

定本 Cプログラマのためのアルゴリズムとデータ構造 2-2-6

文献購読

線形探索法と2分探索法とハッシュ法の短所を比較

短所

線形探索法はデータを登録順に保存しているが、探索が遅い
2分探索法は探索が線形探索より早いが、あらかじめソートが必要だし、データの登録順を保存できない
ハッシュ法はハッシュ関数が便利だが、データを格納する配列が肥大化したり、データの衝突を検出、考慮したりする必要がある。また、データの登録順は保存できない。

アルゴリズムの選択は問題次第である、ということ

Oの小さいアルゴリズムは凝ったものが多い
Oが極めて小さい場合には、凝ったアルゴリズムより、素朴なアルゴリズムの方が早い
プログラミングの手間も考えよう
めったに使わない部分は素朴なアルゴリズムでよい
実行時間とデータ領域のトレードオフも考えよう

定数係数

アルゴリズムの勉強時に定数係数と出てきたら、計算機の速度や、実装言語の選択や、高速なコンパイラなど、アルゴリズム自体ではなくアルゴリズムを運用・実装する環境の早さのことをさしている。

計算量の話は不可避

アルゴリズムの勉強をするときには計算量を常に考えよう。
一般に、プログラムの速さをあげる方法として定数係数を下げるような方法が選ばれることが多い。

早いマシンに乗り換え
cやアセンブラで記述
コンパイラを早いものに

でも、このアプローチでは実際には計算量のオーダーは改善されない。
オーダーのことも考えようね。

2007-02-06

定本 Cプログラマのためのアルゴリズムとデータ構造 2-2-5

文献購読

ハッシュ法ですね。
hashing。

ハッシュ関数って何？

キーの値から添え字を得る関数をハッシュ関数という。

たとえば？

例えば、大きさ100の配列を使って、整数のキーをもつデータを扱うには
ハッシュ関数hash(key)を、h(key) = key % 100、などとして
ハッシュ値を得ればよいだろう。

どんな問題が？

ハッシュ法はハッシュ関数の実装によるけど、キーの衝突をなかなか避けられない。
たとえば、上記のハッシュ関数では100で割ったあまりをハッシュ値同じになるキーはすべて衝突してしまう。

解決法は？

キーが衝突したときに、同一のハッシュ値をもつデータをポインタでつないだり、(チェインとかいう)
または、完全に衝突しないようなハッシュ関数を生成したり（完全ハッシュ法とかいう）すればいい。

計算コストは？

通常のはハッシュ関数は基本操作だけで実現できるから、O(1)になる。
ハッシュが衝突し、かつデータの個数が多めになると、衝突の解析にコストがかかる。

コストの発生する原因

コストの大半は衝突や衝突の回避によって生まれる。
よってハッシュ関数の質を高めることがコスト削減につながる。
配列の大きさに対してデータの割合が8割をこえると、
ランダム値によるhashingでは衝突を起こし始める。
そうするとコストがO(1)を超えてしまう。

ハッシュ法は時間と空間のトレードオフ

ハッシュ法はデータ格納領域を十分に用意できる場合には、
関数をそれほど工夫しなくても十分な効果を得られる。
また、関数の選択を正しく行えば、登録や探索のコストを
O(1)に収めたり、近づけたりできる。

2007-02-05

お、もう12時

日記

お、もう日付が変わるなー。
じゃあ、もうおしまいにしよう。
疲れる前に止める。堅苦しくないのが続ける秘訣。

次はハッシュ法だよ。

2007-02-05

定本 Cプログラマのためのアルゴリズムとデータ構造 2-2-3

文献購読

2-2-3はデータ挿入のコストの話。
そうか、検索だけじゃなくて挿入のコストを考えなきゃいけないときも多いよな。

リニアとバイナリのデータ挿入における違い。

リニアはソート不要なので、リストの最後にデータをくっつけるだけ。
一方、バイナリは常にリストがソートされてなきゃ駄目なので、
素朴なアプローチとしては、新しいデータの挿入位置を決めて
挿入位置より後ろのデータを後ろにずらす。
そして、開いた場所に新しいデータを入れることになる。

実装

add_linear(int key, int data){
  /*nはデータ個数（データの挿入位置をあらわす配列番号*/
  if(n >= TABLE_SIZE){ error("too much data.");}
  table[n].key = key;
  table[n].data = data;
}

add_binary(int key, int data){
  int pos;
  pos = 2分探索で挿入位置決定

  配列のpos以降を1つづつずらす

  table[pos].key = key;
  table[pos].data = data;  
}

n個のデータを追加するための計算量

バイナリはn回末尾に挿入するだけなのでO(n)
リニアは、1回の計算に必要な計算量を考えると、挿入位置探索にO(log n)、データずらしは線形時間なのでO(n/2) = O(n)となり、O(max(log n, n, 1))でO(n)も必要になる。さらにこれをn回繰り返すので、合計計算量はO(n^2)となる。

実運用時のことを考える

2分探索法は挿入と検索を同時に行う必要がある場合には向かないことが分かる。
だが、2分探索法は挿入時のコストを軽減することができれば、問題が減りそうだ。

どんなときにコストを減らせる?

最初にすべてのデータをソート可能で、メインでは検索のみの場合

どうやるの？

最初はデータをソートせずに配列に挿入する。
ソートには計算量がO(n log n)のアルゴリズムがあるので、それを使ってソートする

結果は？

結果として挿入にかかるコストがO(n^2)からO(n log n)に激減した。