情報科学（ 2 ） 対象のモデル化とデータ構造 （ 2 ）. 連想メモリ（ Associative memory ） 一般的な離散写像をデータモデル化したもの 例 数学の点数 山田 →65 ，鈴木 →83 ，田中 →71 ，山本 →95 ， … cf. 配列は連続した整数の有限部分集合を定義域とする写像.

Presentation on theme: "情報科学（ 2 ） 対象のモデル化とデータ構造 （ 2 ）. 連想メモリ（ Associative memory ） 一般的な離散写像をデータモデル化したもの 例 数学の点数 山田 →65 ，鈴木 →83 ，田中 →71 ，山本 →95 ， … cf. 配列は連続した整数の有限部分集合を定義域とする写像."— Presentation transcript:

1 情報科学（ 2 ） 対象のモデル化とデータ構造 （ 2 ）

2 連想メモリ（ Associative memory ） 一般的な離散写像をデータモデル化したもの 例 数学の点数 山田 →65 ，鈴木 →83 ，田中 →71 ，山本 →95 ， … cf. 配列は連続した整数の有限部分集合を定義域とする写像 コンピュータのメモリの線形アドレスをうまく利用している 膨大な定義域に散らばるデータとその像の対をコンパクトに表現す る 人の名前の集合を辞書順序で並べた巨大な表を作れば，辞書を引くように 写像を計算することができる しかし， 1 つの教室は高々 50 人なので（定義域が小さいので） ムダ 一般的にはハッシュと呼ばれる計算メカニズムを利用して実現 配列のアクセスより時間コストが高い

3 ハッシュ（ Hash ） marks = {" 山田 " => 65, " 鈴木 " => 83, " 田中 " => 71, " 山本 " => 95} marks[" 大田 "] = 75 marks[" 井上 "] = 48 # このようにどんどん定義域を広げていくことができる marks[" 鈴木 "] # 鈴木君の点を訊く # 最初の行と同じことは以下のようにしても可能 marks = Hash.new(0) # 登録されていない学生はとりあえず 0 点に marks[" 山田 "]=65 marks[" 鈴木 "]=83 marks[" 田中 "]=71 marks[" 山本 "]=95 Ruby 中カッコ に注意

4 大きさが不定のデータ構造 配列もレコードもデータを作るときに大きさが決まる あらかじめ必要な大きさが予想できない場合？ 途中で大きさが変化する場合？ 文字列はその典型例 あらかじめ大き目の文字の配列を用意 足りなくなったらもっと大きな配列を用意してコピー このようにシステムが裏方でがんばってくれる場合もある 多様なデータ構造についてシステムががんばってくれる ことは期待できない 不定の大きさのデータ構造にユーザが自分で対処する必要 あらかじめ大き目の配列を用意するのは一つの手 実際の情報が配列のどこまで入っているかを自分で管理 currentMaxarrayBody k+1 k レコード配列 未使用部分 k-1 k+1

5 中身サイズ可変の配列 # Ruby ではちょっと無理のある例だが … FillArray = Struct.new(:currentMax, :arrayBody) # FillArray と，先頭が大文字になっていることに注意 # とりあえずサイズ 100 の配列を用意 fillArray = FillArray.new(0, Array.new(100)) # 第 0 要素に "hello" ，第 1 要素に "world" を入れてみる fillArray.arrayBody[fillArray.currentMax] = "hello" fillArray.currentMax += 1 # currentMax を 1 増やす fillArray.arrayBody[fillArray.currentMax] = "world" fillArray.currentMax += 1 Ruby

6 再帰（ recursion ） 落語の「頭山」 頭の上にできた水溜りを嘆いて，そこに飛び込んでしまった男の噺 ― 自分で自分に飛び込む ? 仕事を下請けに出したら，巡り巡ってその仕事の一部が自分に戻って きた 友達 A のことを紹介しようとして，「 A のいい加減なことといったら， A みたいにいい加減なんだ」と言ってしまった 辞典で「白い」を引いたら「雪のような色」と書いてあったが， 「雪」を引いたら「空から降ってくる，雨が凍った白く冷たいもの」 と書いてあった 「秘妙」という造語の意味を説明をしようとして，「『秘妙』という 言葉の意味は非常に秘妙であり，説明が難しい」と言ってしまった しかし，堂々巡りにならないのであれば， 再帰は非常に強力な計算の原理

7 再帰的定義 簡単な例 階乗の定義 factorial(n) ≡ if n<2 then 1 else n*factorial(n-1) Fibonacci 数の定義 fib(n) ≡ if n<2 then 1 else fib(n-1)+fib(n-2) ちゃんとした再帰的定義は堂々巡りにならず， いつかは終端に達する ある漢和辞典（明解漢和辞典 1927 年 ）の例 九 八に一を足した數 八 七に一を足した數 … 二 一に一を足した數 一 對なき數．數の始め

8 リスト構造（ list ） 必要な分だけをつないで使う 例 道順の説明 交差点ごとに直進，右折，左折を示す " 直進 " " 右折 "" 直進 "" 左折 " どこも指して いないことを 意味するポイ ンタ null また は nil " 直進 "" 右折 "" 直進 "" 左折 " " 直進 " いきなり途中の交差点が増えても（減っても）大丈夫 構造のほかの場所に影響を与えないで情報更新 [ex] 配列で同じことをしたらどうなるか ? 2 つのフィールドをもつセ ル ポインタは切ったり 張ったりできる

9 木構造（ tree ） 数式の構造は木構造になじむ / ＋ 1 － 3* **2 5* 数式を扱おうとすると，因数分解や展開 でどんどん数式の形が変わる． このようにあらかじめデータの大きさも 形も予測できない場合，ポインタを使っ て自由に大きさを変えられるとうれしい

10 再帰的データ構造 リスト構造 ::= セル | nil | 数や文字列などの基本データ型 セル ::= リスト構造とリスト構造の対 木構造 ::= 変数名 | 数 | 木構造と演算子と木構造の 3 組 ::= は「定義」の意味 | （縦棒）は「または」と読む リスト構造も木構造もいろいろなものがある． ここに示したのはその一例

11 再帰的データ構造定義の例 # 中置記法の数式に合わせて Expr = Struct.new(:left, :operator, :right) # 前のスライドの例を無理やり作ってみた Expr.new( Expr.new(3, :*, Expr.new(:x, :**, 2)), :-, Expr.new(5, :*, :x)), :/, Expr.new(:y, :+, 1)) Ruby :left と :right に Expr が出てくるので，本来 再帰的なデータ構造定 義だが， Ruby では陽 に Expr と書かなくてよい ので再帰であることが 見えにくい

12 基礎的なデータモデル スタック ここではオブジェクトとして定義（ Ruby のオブジェク ト） キュー （待ち行列） 同じデータモデルの実現にもいろいろなデータ構造が ある グラフ構造（地下鉄路線図） 目的に合ったデータ構造の設計

13 スタック（ stack ） 後入れ先出し（ Last-in First-out ）でデータを貯めるもの 原義：干草などを積み重ねたもの コンピュータ（特にプログラミング言語の処理系）では重要な概 念 しかし，「後入れ先出し」は一般社会では使わないことが推奨さ れる スーパーの倉庫「先入れ先出しを守れ」（賞味期限がある） 片付かない机の上は先入れ先出しがしにくい構造 例外：トランプの独り遊びには頻出 基本操作 push データを積む pop データを取り出す，降ろす （降ろさないで見るだけの操作も 通常はある） empty? 空っぽ？と聞く top bottom

14 スタックの定義 class Stack def initialize(size) # new のときの初期化 @data = Array.new(size) @pos = -1 # @pos がスタックのトップを表す．最初はボトムを指す -1 ． end def push(obj) # obj がプッシュされるデータ @pos += 1 # @pos = @pos + 1 と同じ意味 @data[@pos] = obj # 前頁の図では上のほうが番地が大きい end def pop @pos -= 1 # 先にトップへのポインタを減らす @data[@pos + 1] # ∵ 最後の式が値となるため end def empty?() @pos == -1 end end Ruby この定義の後に 試してみよう s = Stack.new(100) s.push :abc s.push :def p s.pop

15 キュー（待ち行列， queue ） 先入れ先出し（ First-in First-out ）でデータを貯めるもの 要するに先着順（ First-Come First-Service ） OS ，ネットワーク，シミュレーション，探索などで使われる 基本操作 enqueue データをキューに並ばせる（末尾につける） dequeue キューの先頭からデータを取る empty? キューが空？ top last tail この順に並んでる

16 キューの３通りのデータ構造 （ 1 ） 配列 top=i last=j i j 配列 top=m last=n m n 列の最大長さよりも大きい １次元配列を用意し，それを 循環的に使う top と last のほかにキューの 長さを表す変数を使うことも ある 変数 tail が，次にデータが 入るところの添え字を表す 方法もある（こちらのほうが 普通） １次元配列とそれの添え字を値としてとる 2 個の変数で 表す まず，複雑なデータ構造の定義がしにくい言語での方法

17 配列 top=i last=j i j 配列 top=m last=n m n enqueue

18 配列 top=i last=j+1 i j+1 配列 top=m last=n m n enqueue

19 配列 top=i last=j+1 i j+1 配列 top=m last=n m n enqueue

20 配列 top=i last=j+1 i j+1 配列 top=m last=n+1 mn+1 enqueue

21 配列 top=i last=j i j 配列 top=m last=n m n dequeue

22 配列 top=i+1 last=j i+1 j top=m last=n m n dequeue 配列

23 top=i last=j i+1 j top=m+1 last=n m+1 n dequeue 配列

24 キューの３通りのデータ構造 （ 2 ） j レコード（簡略に書いた） array i 変数と配列を一体化したレコードにする方法 ここでは，キューの最後を次に並ぶ場所の添え字にす る さらにキューに並んでいるデータの個数もレコードに 入れる toptaillength ijn n

25 j i toptaillength ijn n enqueue array

26 j+1 i toptaillength ijn+1 enqueue array

27 j i toptaillength ijn n dequeue array

28 j i+1 toptaillength ijn-1 dequeue array

29 キューの３通りのデータ構造 （３） レコードの中で配列の代わりにリスト構造 キューの最大長さが予測できないときに便利 リスト構造は先頭はともかく，末尾にアクセスするのに時間がかか る しかし，工夫すると，先頭も末尾もほぼ同じ速度でアクセス可能 以下はその一例（ほかにいっぱいデータモデル化の方法がある） top last キューへのポインタ 循環リストになっている

30 キューの３通りのデータ構造 （３） 続き top last キューへのポインタ enqueue どちらの操作もキューの長さに依存しない一定時間で処理することが可能 （キューが空から出発する，あるいは空になるときは処理に要注意） top last キューへのポインタ dequeue

31 キューの３通りのデータ構造 （３） 続き top last キューへのポインタ new enqueue どちらの操作もキューの長さに依存しない一定時間で処理することが可能 （キューが空から出発する，あるいは空になるときは処理に要注意） last キューへのポインタ dequeue top

32 キューの３通りのデータ構造 （３） 続き top last キューへのポインタ new enqueue どちらの操作もキューの長さに依存しない一定時間で処理することが可能 （キューが空から出発する，あるいは空になるときは処理に要注意） top last キューへのポインタ dequeue

33 キューのデータ構造 （ 2 ） MyQueue = Struct.new(:top, :tail, :length, :array) def enqueue(q, data) q.array[q.tail] = data q.tail = (q.tail + 1) % q.array.size # % は余りを求める演算 （循環するため） q.length += 1 end def dequeue(q) value = q.array[q.top] q.top = (q.top + 1) % q.array.size q.length-= 1 value end def empty?(q) q.length == 0 end Ruby 試してみよう q = MyQueue.new(0, 0, 0, Array.new(100)) p empty?(q) enqueue(q, :x) p empty?(q) enqueue(q, :y) enqueue(q, :z) p dequeue(q) p empty?(q)

34 キューのデータ構造 （ 3 ） Cell = Struct.new(:value, :next) $ptr = nil def enqueue(data) if $ptr != nil cell = Cell.new(data, $ptr.next) $ptr.next = cell $ptr = cell else $ptr = Cell.new(data, nil) $ptr.next = $ptr end Ruby def dequeue cell = $ptr.next if $ptr.next != $ptr $ptr.next = cell.next else $ptr = nil end cell.value end def empty? $ptr == nil end 一言リマーク： Ruby では．オブジェクトにしないのが 不自然 $ は大域変数の意味

35 地下鉄路線図 http://www.tokyometro.jp/rosen/rosenzu/index.html

36 地下鉄路線図のデータモデル データモデルにして何をしたいかをまず考える 発駅から着駅までの最短の経路を探索する 発駅から着駅までの最も安い経路を探索する 発駅から着駅までの乗り換え回数最小の経路を探索す る 乗り換え所要時間も考慮に入れる？ 発駅から５駅以内で行けるすべての駅を数え上げる 駅名が漢字５文字以上の駅を列挙する JR との乗換駅を列挙する … どの操作が最も頻繁に使われるか，重要かを考 える それらに適したデータモデル化（一つとは限らない） アルゴリズムやプログラミングに関する土地勘が必要 次回以降の講義でそれらの素養を学ぶ

37 地下鉄路線図のデータモデルの一例 (1) linenameupupDdowndownDexchangeList " 東西線 "" 茅場町駅 " 0.50.8 駅のデータの集合として地下鉄路線図を表す 例えば東西線茅場町駅を表すデータ（ Station ） 大文字の D は距離（ Distance ）の意味 東西線日本橋駅のデータ 東西線門前仲町駅のデータ 日比谷線茅場町駅のデータ stationtimeForExchangenextExchange 3 プログラミング言語 で書くのは演習

38 地下鉄路線図のデータモデルの一例 (2) 人が見る時刻表のように路線ごとにまとめて表にしてしまうのでもよい このとき路線名や駅名から連想メモリを使うのではなく，それらに通し番号を つけると配列だけでかなりのことができる 銀座線 丸の内線 東西線 有楽町線 南北線 大江戸線 … ー 中野 0 落合 2.0 高田馬場 1.9 早稲田 1.7 神楽坂 1.2 飯田橋 1.2 … 3134 路線番号 駅番号 所要時間 乗換え 距離 次候補