処理速度・メモリの使用量・プログラミングの容易さのトレードオフの理解という点で、 まとめる。

• 単純配列
  • 検索処理O(N),挿入処理O(N)
  • 固定サイズで最大量不定ならメモリ使用効率×、巨大一定
  • 最大データ数が既知ならば、メモリの使用効率は高くできる。
  • プログラミングはそのまんま。
• 昇順配列
  • 2分探索法で検索処理O(log(N)),挿入処理O(N)
• 配列によるヒープ
  • 検索処理O(log(N)),挿入処理(入れ替えがあるとちょっと手間)

• 線形リスト
  • 検索処理O(N),挿入処理O(1)
  • メモリ量はデータに比例(ポインタ分のムダ)
  • スタックや待ち行列などで、最大データ数が分からない場合に便利。
• 循環リスト
  • 待ち行列など
• 双方向リスト
  • エディタなどの前後移動のあるデータ
• 2分木
  • 検索処理O(log(N)),挿入処理O(1)
  • 木の左右のバランスが重要。AVL木=O(log(N)),不均衡=O(N) worst
  • 2つのポインタを持つため、メモリのムダあり。
  • 全データ対象だと再帰などでプログラミングが難しい。
• B木
  • 検索処理O(log_d(N)),d=位数
  • データベースなどの基本技術
• ハッシュ法
  • 検索処理：表サイズ>Nなら、O(1) , 表サイズ<Nなら、O(N)
  • 同一ハッシュ値が求まった場合＝ハッシュ衝突
  • オープンアドレス法(ハッシュ値を求めなおす,イス取りゲーム？)
  • チェイン法(同一ハッシュ値をリスト構造で保存)

グラフィックスの授業は、次回１回のみということで、演習を中心の時間とする。 3次元グラフィックスの説明(ワイヤーフレーム)について簡単にプログラム例を用いて 説明する。プログラム応用では、関数と引数を使いこなせるようになることが目標でもあり、 前回の演習で、ポインタ渡し・配列渡しが含まれるサンプルを見せたこともあり、 今回の資料では『構造体のポインタ渡し』を使用した例となっている。

等測投影・2軸測投影による3次元表示の処理結果から、陰面処理の必要性などを改めて説明。 また、雑談として最近の映画にみられるグラフィックス技術について紹介する。

映画に見られるSFXとグラフィックス技術： ターミネータ2のT-1000や、アビスに見られる透明液体異星人では、 レイトレーシングといった技術が重要であることを示す。 また、毛ふさふさといった者を自然に見せる技術の難しさということで、 成功例：モンスターズインクのサリー、失敗例：Aflacのコマーシャルの猫踊りのフサフサ感を紹介。 また、自然なキャラクターの動きという点で、モーションキャプチャ技術が一般的であることを紹介。 特に近年は、体の動きと顔の動きの同期という点で、ヘルメットに顔撮影のカメラをつけた事例 として、アバターなどを紹介。(パイレーツオブカリビアン2が先の成功事例だが…)

コンピュータアーキテクチャに興味を持つ者としては、で採用されたクラスタリング技術なども重要であり、クラスタリングという単語を紹介。