SICP

SICP を読んでみる #68 第二章 pp.109-110

問題解答

問2.74
パス

本文

メッセージパッシング

手続き名毎に内部で実際に呼び出す処理を振り分ける。

データを生成すると実態は手続きが帰ってきて、そのデータ(手続き)に対して必要な演算の名前を渡すことで必要な結果を得ることができる

問題解答

問2.75
手の運動なのでパス。

問2.76
汎用演算 :
型・演算の追加共にシステム全体に対して影響を及ぼす。

データ主導流 :
新しい型が追加された場合に、その型に対応したパッケージを用意する。新しい演算が追加された場合、全てのパッケージに対して新しい演算を定義する。そのため、型の追加に対しては全体への影響は少ないが演算の追加に対してはシステム全体に影響を及ぼす。

メッセージパッシング流 :
新しい型が追加された場合に、全てのパッケージに対して新しい型を定義する。新しい演算が追加された場合、その演算に対応した手続きを定義する。そのため、型の追加に対してはシステム全体に影響を及ぼすが、演算の追加に対してはシステム全体に影響が少ない。

ここまで来たけど、イマイチ用語が肌に馴染んでいない感がある。構成子とかパッケージとか演算とか、SICP 的な用語の感覚が何だか曖昧。

SICP

SICP を読んでみる #67 第二章 pp.108-109

コードの入力と内容の確認がおわったので問題に戻ります。

問題解答

問2.73
b.
和の微分は (u+v)’ = u’+v’
積の微分は (uv)’ = uv’+u’v

(define (deriv-package)
  (define (deriv-sum exp var)
    (make-sum (deriv (addend exp) var)
              (deriv (augend exp) var)))

  (define (deriv-product exp var)
    (make-sum
     (make-product (multiplier exp)
                   (deriv  (multiplicand exp) var))
     (make-product (deriv (multiplier exp) var)
                   (multiplicand exp))))

  (put 'deriv '+ deriv-sum)
  (put 'deriv '* deriv-product))

こんな感じ? put/get がないのでちゃんと動作確認ができない。
ちょっと(かなり)手抜きで、答えを見ながら完全に動作するコードをコピペして動作を確認。

SICP

SICP を読んでみる #65 第二章 pp.99-105

本文

問題の解答をするためには本文で解説されているコードを一通り打ち込まないとやっぱりダメですね。
めんどくさいけどこれも練習なので今更ながら打ち込み。

汎用複素数システムのぶぶんまでの打ち込みが完了して、今日は終了。

SICP

SICP を読んでみる #64 第二章 p.108

ゴールデンウィークもあっという間におわり、通常営業に戻ります。

問題解答

問2.73
a.
(get ‘deriv…) の部分がわからない → P.106 で解説済だった。
‘deriv の表からオペレータを取得して微分計算をおこなうようにしている。
number? や variable? は微分の計算ではなく、他の処理とは異なるため同列に扱うことができない。

b 以降は明日。全く集中できなかった。。。。

SICP

SICP を読んでみる #63 第二章 pp.98-108

SICP の朝練を始める前にちょっとだけと思って仕事をしてしまって、結果朝練をする時間が無くなってしまうというのがお約束パターンとしてあるようで、ここ数日もそんな感じです。朝に作業をしてしまった分時間をずらして勉強をしようと思っても何だかんだで結局できなくなってしまうので、このパターンにハマらないように気をつけないといけないです。

問題解答

問2.70~2.72 はパス。

本文

2.4 抽象データの多重表現
複素数のように、同一の内容を複数の方法で表現することができる場合、状況によってどちらが最適かは変わってくる。
また、時間とともに要求が変わってきた時にデータ表現も柔軟に対応できるようにする必要がある。
このような場合でもプログラムの一部分だけ手を入れることで対応できるようにする。

2.4.1 複素数の表現
演算によって実座標・虚座標での表現と絶対値・偏角での表現どちらが適しているかかわる。また、どちらの表現を使用していてもプログラマの観点からは任意の表現方法でアクセスした時の値が取得できると有用な場合が多い。

2.4.2 タグつきデータ
データにタグをつけ、どのような形式で表現されたものなのかを判別できるようにする。その上で表現形式毎に適切な手続きを用意して、共通のインターフェースを持つ手続き内で、実際に呼び出す手続きを切り替える。

今ならクラス化をすれば簡単にできる内容。

2.4.3 データ主導プログラミングと加法性
・汎用インターフェースは全ての表現を知らなければいけない
・表現は別々に設計できるが、システム全体で名前が被らないことを保証しなければいけない

→パッケージを定義し、実装をその中に隠蔽する

SICP

SICP を読んでみる #62 第二章 p.98

問題解答

問2.69

(define (successive-merge  trees)
  (if (= (length trees) 1)
      trees
      (letrec* ((l (length trees))
                (carTrees (take trees (- l 2)))
                (cdrTrees (drop trees (- l 2)))
                (leaf (make-code-tree (car cdrTrees) (cadr cdrTrees)))
               (successive-merge (adjoin-set leaf carTrees))
               )
      ))

(define (generate-huffman-tree pairs)
  (successive-merge (make-leaf-set pairs)))

(define pairs (list (list 'A 2)
                    (list 'B 2)
                    (list 'C 1)
                    (list 'D 1)))
(define hTree (generate-huffman-tree pairs))
(define code (encode '(A D A B B C A) hTree))
(decode code hTree)

Lisp への信心が足りなさすぎて、処理をコードに落とすところでものすごく時間がかかっちゃいます。

細かい処理で時間をとられがちなので、letrec* とか take とか drop とか、SICP では言及されてないけど存在する便利機能も今後はある程度調べて使っていこうかと思います。

ちなみに解答例は違うアプローチ。

(define (successive-merge set)
 (if (= (length set) 1) (car set)
     (let ((sorted-set (sort set (lambda (x y) (< (weight x) (weight y))))))
       (successive-merge 
        (cons (make-code-tree (car sorted-set) (cadr sorted-set))
              (cddr sorted-set))))))

ソートして、頭から繋げていくのか。たしかにこっちの方が自然ですよね、、、、

SICP

SICP を読んでみる #61 第二章 pp.94-98

一日空いてしまったので復習から。

問題解答

問2.68

(define (encode-symbol symbol tree)
  (define (it symbol tree code)
    (cond ((null? symbol) '())
          ((leaf? tree) code)
          ((element-of-set? symbol (symbols (left-branch tree)))
           (it symbol (left-branch tree) (append code '(0))))
          ((element-of-set? symbol (symbols (right-branch tree)))
           (it symbol (right-branch tree) (append code '(1))))
          (else (error "bad symbol" symbol))))

  (it symbol tree '()))

(define (encode message tree)
  (if (null? message)
      '()
      (append (encode-symbol (car message) tree)
              (encode (cdr message) tree))))

(encode '(A D A B B C A) sample-tree)

答えはでたけど何かコードが汚い。

Programming, Python

set なにそれおいしいの?

昨日、Python文法詳解を詳解する会 #3に参加してきました。第三回の主な内容は文字列と集合(set)だったんですが、 set ってよく知らないと何それおいしいの?状態だったりします。というか、自分も以前はそんな感じでした。

Python には配列として list があって、大抵のことはこれで事が済んでしまいます。list なら順番は保持してくれるし同じ値も格納することができます。それに対して set では順番が保持されないし同じ値を格納することもできません。一見するとすごく不便です。

set は、 l = list(set(l)) のように重複する要素を無くした list にするためにしか使わないという人は多いのではないでしょうか。

でも、実は set ってものすごく使える子なんですね。

set の何が嬉しいかっていうのを説明するには集合っていうものが何なのか?っていうことを説明したほうがいいんですが、細かい話をしだすとキリがないので気になる人は集合っていうキーワードで調べてみてください(丸投げ。

ここではあんまり詳しくなくても今日から使える set の使い方ということで、実例をあげて紹介します。

連番ファイルの抜けチェック

何かスクリプトを組む時に、あるデータ A と 別のデータ B が同じか、違うならどこが違うか?を比較したい時がよくあります。

映像業界では動画を扱う必要があるので画像を連番ファイルとして扱うことが日常的にあります。この時、一部のファイルが無くなってしまっているということが多々あります。

ファイルが 10 個とか 20 個とか少なければ目でも確認できますが、動画の連番ファイルは一秒で 24 個とか 30 個のファイルができます。10 秒で 240~300、一分なら 1440 とか 1800 個のファイルが一つのディレクトリ内にできます。ファイルの抜けがあるかどうかは総ファイル数を確認すればできます(後述の通り、本当はできないですが)。問題は、ファイルが少なかったり多かったりしたときです。

1440 個ファイルがなければいけないのに、1438 個しかファイルがなかった場合、どのファイルが無いのか確認しなければいけません。目視で確認?できなくはないですけど時間もかかるし見落としてしまったら再度チェックの必要があります。もっと悪いことに、正しいファイルは 1437 個で、本当はあってはいけないファイルが 1 個紛れ込んでいるかもしれません。こうなったらもう手あげです。こういうときはプログラムの出番です。

簡単に書くとこんな感じでしょうか。


import os
d = 'path/to/renban'
fname = 'hoge.%04d.exr'
nfile = 1000

for i in range(nfile):
    path = os.path.join(d, fname % i)
    if not os.path.exists(path):
        print 'missing file :', path

はい。これで一応抜けているファイルのチェックはできるようになりました。でも、これだと余分なファイルがあった時にきづけないです。細かいことをしようとすると os.listdir() でファイル一覧を取得して、えいやっといろんな処理を書かないといけないです。めんどくさいです。めんどくさすぎて禿げてしまいます。

そういうときに、集合の比較という問題に落とし込んでしまいます。

連番ファイルのチェックという問題は、結局のところ

  • 実際に存在するファイルの一覧
  • 本来存在すべきファイルの一覧

の二つを比較するということです。一覧を集合と読み替えると、まさに集合演算の最も得意とする処理内容になります。そこで、コードにしてみましょう。まずはそれぞれの一覧(集合)を作ります。


import os
d = 'path/to/renban'
fname = 'hoge.%04d.exr'
nfile = 1000

# 実際に存在するファイルの一覧
existingFiles = set(os.listdir(d))

# 本来存在すべきファイルの一覧
theoreticalFiles = set([fname % i for i in range(nfile)])

これで集合ができました。あとは、この二つを好きなように集合演算すればいいだけです。


#本来あるべきなのに無いファイルを表示
print theoreticalFiles - existingFiles 

#存在すべきでないファイルを表示
print existingFiles - theoreticalFiles 

どうでしょう。引き算をするだけで欲しい情報が得られてしまいました。プログラムで逐次処理する例と比べて段違いに簡単で、かつ処理内容をちょっと変えるだけでいろいろな情報を得ることができるようになっています。

集合演算

ここで何をやっているのかを簡単に説明します。

最初に作成した existingFiles と theoreticalFiles は下図のような関係にあります。赤い丸が existingFiles、青い丸が theoreticalFiles です。赤丸と青丸が重なっている部分は両方に含まれるファイル、重なっていない部分はどちらか片方にしか含まれないファイルになります。

集合演算では、この丸を使って足したり引いたりといった演算を行うことができます。今回おこなったのは下図の二つの演算です(existingFiles と theoreticalFiles だと長いので、A と B に置き換えています)。みての通り、それぞれにしか含まれない要素だけを取り出すことができています。

もちろん、これだけではなく他にもいろいろな演算をおこなうことができるので、目的に応じて必要な情報を得ることができます。

まとめ

今回のような内容は、集合論の勉強をしたことのある人なら当たり前だよっていう内容ですが、知っていると知らないとでやりたいことを実現するためのアプローチが全く異なってくるといういい例です。

もちろん、集合(set) を使った処理をおこなうためには集合を扱うためのお約束に則った形に問題を置き換えなければいけないですが、うまく問題を置き換えることができた時には強力な道具になってくれます。

皆さんも身の回りの問題を置き換えて簡単に表現できないか考えてみてください。