2010年1月31日(第149回)
テスト期間中につき、数学科 長水先生、電子情報工学科 奥田先生、西の3名でお送りしました!
- 第6回めがねワクwakuコンテスト受賞者インタビュー
megane100131.mp3
- 英語の囃子 第24回 吉田三先生、電子情報4年丸山さん
英語の桃太郎を読んでみよう(最終回)
eng100131.mp3
データ構造とアルゴリズムの総括
処理速度・メモリの使用量・プログラミングの容易さのトレードオフの理解という点で、 まとめる。
- 単純配列
- 検索処理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)
- 同一ハッシュ値が求まった場合=ハッシュ衝突
- オープンアドレス法(ハッシュ値を求めなおす,イス取りゲーム?)
- チェイン法(同一ハッシュ値をリスト構造で保存)
グラフィックス技術動向
グラフィックスの授業は、次回1回のみということで、演習を中心の時間とする。 3次元グラフィックスの説明(ワイヤーフレーム)について簡単にプログラム例を用いて 説明する。プログラム応用では、関数と引数を使いこなせるようになることが目標でもあり、 前回の演習で、ポインタ渡し・配列渡しが含まれるサンプルを見せたこともあり、 今回の資料では『構造体のポインタ渡し』を使用した例となっている。
等測投影・2軸測投影による3次元表示の処理結果から、陰面処理の必要性などを改めて説明。 また、雑談として最近の映画にみられるグラフィックス技術について紹介する。
映画に見られるSFXとグラフィックス技術: ターミネータ2のT-1000や、アビスに見られる透明液体異星人では、 レイトレーシングといった技術が重要であることを示す。 また、毛ふさふさといった者を自然に見せる技術の難しさということで、 成功例:モンスターズインクのサリー、失敗例:Aflacのコマーシャルの猫踊りのフサフサ感を紹介。 また、自然なキャラクターの動きという点で、モーションキャプチャ技術が一般的であることを紹介。 特に近年は、体の動きと顔の動きの同期という点で、ヘルメットに顔撮影のカメラをつけた事例 として、アバターなどを紹介。(パイレーツオブカリビアン2が先の成功事例だが…)
コンピュータアーキテクチャに興味を持つ者としては、で採用されたクラスタリング技術なども重要であり、クラスタリングという単語を紹介。
2010年1月24日(第148回)
- 本日は都合により、先週の再放送をお送りいたしました。
メールからMovableTypeへの投稿
MovableTypeへの投稿は、メールでやっているんだけど、 通常のメールアドレスと、MovableType投稿用のアドレスが似ているので、 Thunderbirdのアドレス補完で、自分宛にメールを出すつもりが、 MovableTypeに投稿されるというトラブル発生。 投稿用処理の条件を厳しくして、Cc:,Bcc:付きといった 投稿は無視するようにしてみた。
データベースの応用と動向
B木、B+木の紹介で教科書に記載されている一般的な話はほとんど紹介できたので、 今日は最近のデータベースにからむ技術動向を紹介。
B木とファイルシステム
前回のB木のネタの応用ネタということで、最近のファイルシステムにB,B+が採用されいている 事例を紹介。NTFS(Windows),ReiserFS(unix),B*木を使ったHFS(Mac OS X), データ検索機能のついたWinFSなどの事例を紹介。
データベースエンジンの動向
データベースシステムには、関係データベース、XMデータベース、オブジェクトデータベースがある。(追記)
関係データベースでは、データベースの構成が変更になると、移行処理が大変。 柔軟なデータベースの構造に対応できるようにしたい。
⇒XMLデータベース。XMLを扱うための機能を持つデータベース。 XMLのツリー構造をそのままデータ構造として持つ物。
構造化された複雑なデータを扱う場合には、オブジェクト指向のプログラム言語が利用される。 しかしデータベースは表を元にした表現なので、複雑なデータ構成だと、 それに応じたSQLを発行しないといけない。 このため、プログラマーはオブジェクト指向とRDBの表の考え方の違いを考えながら プログラムを作る必要がある。
⇒オブジェクトデータベース(オブジェクト指向データベース)、データベース自体がオブジェクト指向
データベースを扱うからには情報とシステムも巨大
データベースでは、巨大な個人情報を扱うのがあたりまえ。 SQLインジェクションといったセキュリティ問題をきちんと理解しておかないと、 金銭的な被害も大きくなることを十分意識すべき。
巨大なシステムは、止める事ができない。 しかし、ソフトを作ったり耐故障性能の高いシステムを、 小さい案件で個別に組むのは、手間やコストがかかる。 サーバを借りて動かすことが多い。
サービスの形態で、SaaS(Software as a Service),PaaS(Platform as a Service), IaaS(Infrastructure as a Service)等がある。 最近は、貸し出すサーバが仮想化されたサーバ群で動かし、利用者がどこのサーバで動いているのか意識せずに利用できるようになってきた。⇒クラウドシステム。
クラウドを用いたPaaSでは、Google App Engine , Windows Azuru などが注目されている。 クラウドを用いたIaaSでは、Amazon EC2 あたりが注目されている。
無線LAN接続プロジェクタ
学科の予算にて、4EI,5EIの教室にプロジェクタが付けられた。 映像ケーブルの配線を壁埋め込みとかにすると、工事費がかさむ事から、 無線LAN接続のプロジェクタ(EPSON-EB-1725)が導入された。 無線LANにはアドホック接続で行われ、パソコンに専用ソフトを入れておけば、 映像系の配線なしで使うことができる。 専用ソフトも、Win/7/Vista/XP/2000,Mac OSX/SnowLeopard/Leopard…と幅広く用意されており、 ダウンロードページから導入できる。
簡単と思って実験したら、1つだけ不便なことが…. アドホック接続でつながってしまうので、プロジェクタ接続中は無線LANが使えない…. じゃあLAN接続は有線で….やっぱり配線かよ… 授業でネットしながら説明したいときは、必要画面全部ウィンドウを残しておかないとダメあるね。
追記:(2010/01/25)
WiFiプロジェクタの接続がアドホックだけというのは不便だと思っていて、 製品のマニュアルを読んでみた。 すると、インフラストラクチャモードもちゃんとあった。(あたりまえか…) ということで、学科内には無線LAN環境がそれなりに整っているので、それにつなげればいい。 とおもって、さっそく作業と思ったが『まだリモコンが納品されていない…』とのことで、 作業中断となっちゃった。
iPod Touch のアプリが動かなくなる…
学内でのハンディ端末として使い始めていた iPod touch だけど、 先日よりいきなりApple以外のアプリがすべて動かなくなった。 "iphone アプリ起動しない"と手抜きのキーワードで検索すると、 DRMの認証の問題といった情報が見つかる。対応方法は社外アプリを一旦全部消す! と書いてある。ひとまず初体験なので、全消しした。(有料アプリもあったけど…) でも、よくよく調べてみると、"App Store"で何らかのソフトをインストールすると 起動できるようになると書いてある。次回からは、この手でいこう。
んで、実は2日後にも同じ症状になってしまった。 明確な原因はよく分からないけど、RSS閲覧用にgoogle リーダ対応の無料版を 入れていたけど、起動時によく落ちていた。だから、たぶんコイツが原因だったように思う。 でも改めてこのダメreaderのダメっぷりを紹介しようと探すんだけど、アプリが見つからない。 評判悪くてすぐに消されたんだろうな….
動的メモリの管理方法
malloc() + free() による動的メモリの管理方法について説明を行う。 理解を簡単にするために、確保領域が固定サイズであったときのフリーリストを説明する。
フリーリストとは、free() によって開放された領域をリスト構造で保存しておき、 malloc() 要求があったら、フリーリストの先頭から再利用する手法。 簡単な手抜き実装であれば、初期状態で巨大なmalloc用配列を準備しておき、 その領域すべてをフリーリストとして繋げておけばいい。
通常のmallocは、引数として確保するメモリのbyte数を指定することができるため、 前の説明のように簡単な状況とはならない。 free()によって開放されたメモリ領域はfreelistに保存されるが、 リストにつなぐ際に隣り合った再利用領域は併合される。 malloc()で、フリーリスト内に適切なサイズのメモリブロックが無い場合は、 それより大きい領域を探し、分割される。 このため、malloc+freeの順序が最悪であれば、メモリ空間にヒープホールなどが発生してしまう(メモリの断片化:フラグメンテーション)。
関連する雑談として、同じ断片化(フラグメンテーション)ということで、 ハードディスクの断片化について説明する。 ハードディスクで断片化が発生すると、ムダなシーク時間・回転待ち時間が発生し、 アクセス速度が低下する。 Windowsなどでは、デフラグツールが一般的で、 この処理を行うとハードディスクの実体を覚えている場所を移動させ、 連続したセクタにデータが並ぶように再配置してくれる。
最適化と3次元表示
前回の2次元の座標変換に引き続き、3次元表示について説明を行う。 ただし、グラフィックス処理では、大量のデータ処理から命令の効率よい実行が 求められることが多いので、最適化についても説明を行う。
最適化
C言語のプログラムが機械語に変換されて実行されるが、コンパイル&リンクの間に、 最適化という「効率よく命令が実行するように命令を組み替える処理」が行われる。 オプティマイザによる自動の最適化も重要だけど、複雑なプログラムでは プログラマ自身も最適化を考慮しておくべき。
- CPUの高速化に比べ主記憶(DRAM)のスピードは遅い。このため、キャッシュメモリ(SRAM)を 活用し、利用頻度の高いデータは極力キャッシュに保存されるように命令を書き換えたり、 CPU内のレジスタを極力使うように最適化が行われる。
- 繰り返しの中で変化しない値を何度も計算で求めるのは効率が悪い。 ループの中で変化しない計算はループ前に求めるように最適化をすべき。
- 8bitコンピュータを用いた組み込み系では、CPUが整数の乗算/除算命令が無かったりする。 このため、乗算除算を極力行わないようにすべき。 また、もう少しマシな組み込み系でも、CPUに浮動小数点演算機構が組み込まれていなかったりする。こういうプロセッサでは、浮動小数点演算も極力行わないようにする。
- 最近のコンピュータでは、a*b+c*dといった積和演算や、byteデータ数個に同じ演算を施すといったことが多く、CPUが専用の計算命令を持っている。こういうプロセッサでは、 こういう命令を極力使うように最適化が行われる。
3次元表示
n データを視覚的に表示する場合、3次元表示は重要であり、 簡単な表示では、等軸測投影や2軸測投影といった方法がとられる。 2軸測投影をさらに簡略化した方法で斜軸投影もあるが、 座標軸が直交していないので表示が歪んで見える場合もある。
3次元で見えるためには、遠近法も重要であり、簡単な図法では2消点透視図がとられる。 実際には、投影面と視点による縮小表示などが行われる。
しかし、ここまでの話では、物体の表示座標を求めているだけ。 グラフィックスでは、このあと、陰面処理・光源処理(シェーディング)・テクスチャマッピングといった、 処理が行われる。