月: 2015年4月

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) を使った処理をおこなうためには集合を扱うためのお約束に則った形に問題を置き換えなければいけないですが、うまく問題を置き換えることができた時には強力な道具になってくれます。

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

SICP

SICP を読んでみる #59 第二章 pp.89-94

問題解答

問2.59

(define (element-of-set? x set)
  (cond ((null? set) #f)
        ((equal? x (car set)) #t)
        (else (element-of-set? x (cdr set)))))

(define (adjoint-set x set)
  (if (element-of-set? x set)
      set
      (cons x set)))

(define (union-set set1 set2)
  (if (null? set1)
      set2
      (adjoint-set (car set1) (union-set (cdr set1) set2))))

(define s1 (list 1 2 3 4))
(define s2 (list 3 4 5 6))

(union-set s1 s2)

問2.60
adjoin-set を変更するだけで対応できる

(define (adjoint-set x set)
  (cons x set))

重複しているアイテムを全て処理しなければいけないので CPU 時間もメモリも負荷は増える。
ただ、オーダー的には一緒。

本文

順序づけられたリストとしての集合

集合の要素をソートした状態で格納した場合の計算量への影響

問2.61,2.62 は手の運動なのでパス。

二進木としての集合、集合と情報検索
このあたりは一通り把握している内容なので問題の中身はきちんと確認しつつ飛ばす。

Maya

Maya2016 devkit はいずこに?

Maya2016 は mental ray が別インストールになったり devkit が別配布になったりいろいろ変わっています。

で、ここで微妙にハマるのが “devkitどこよ?” ってことで。わかり辛かったのでメモ。

https://apps.exchange.autodesk.com/MAYA/en/List/Search?searchboxstore=MAYA&facet=&collection=&sort=dateUpdated%2Cdesc&language=en&query=maya+2016+sdk

ここから見つかるようです。devkit で検索して出てこないのは何を考えてるのかと(ぁ。

SICP

SICP を読んでみる #58 第二章 pp.88-89

問題解答

問2.57

(define (augend s)
	(if (null? (cdddr s))
      (caddr s)
      (cons '+ (cddr s))))

(define (multiplicand p)
  (if (null? (cdddr p))
      (caddr p)
      (cons '* (cddr p))))

問 2.58
a:以下のような感じで構成子や選択子を定義していく

(define v (list 1 '+ 2))

(define (addend s) (car s))
(define (augend s) (caddr s))
(define (sum? x)
  (and (pair? x) (eq? (cadr x) '+)))

b:そのまま解くのは大変そう?一度前置記法に変換する処理を入れるのがいいかも。
→答えを見るとその通りっぽい。コンパイラを書いていた。

本文

2.3.3 例:集合の表現
集合の定義・演算について議論。

SICP

SICP を読んでみる #57 第二章 p.88

問題解答

問2.56

(define (make-exponentiation base exp)
  (cond ((= exp 0) 1)
        ((= exp 1) base)
        (else (list '** base exp))))

(define (exponentiation? x)
  (if (eq? (car x) '**) #t #f))

(define (base x)
  (cadr x))

(define (exponent x)
  (caddr x))

(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp)
         (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make-sum
          (make-product (multiplier exp)
                        (deriv  (multiplicand exp) var))
          (make-product (deriv (multiplier exp) var)
                        (multiplicand exp))))
        ((exponentiation? exp)
         (make-product
          (make-product (exponent exp) (make-exponentiation (base exp) (make-sum (exponent exp) -1)))
          (deriv (base exp) var)))
        (else
         (error "unknown expression type -- DERIV" exp))))


(deriv '(** x 2) 'x)
(deriv '(** x 3) 'x)

問題だけ見るとなんじゃこりゃこんなの解けないよ?って思うんですが、ヒントを元にやってみると簡単で驚きます。こんな簡単な方法で記号微分って表現できるんですね。すごい。

SICP

SICP を読んでみる #56 第二章 pp.85-88

問題解答

問2.54

(define (equal? a b)
  (cond
   ((and (eq? a ()) (eq? b ())) #t)
   ((eq? (car a) (car b)) (equal? (cdr a) (cdr b)))
   (else #f)))

(equal? '(this is a list) '(this is a list))
(equal? '(this is a list) '(this (is a) list))

問2.55
” で quote として解釈されるため。

→不正解。

”abracadabra は (quote (quote abracadabra)) と等価。

本文

2.3.2 記号微分
ここはちょっと感動。ものすごく簡単なルールと実装で記号微分が実現できている。

今日は本のコードを写経して動作確認しておわり。

SICP

SICP を読んでみる #55 第二章 pp.82-85

本文

頑健な設計のための言語レベル

成層設計の考え方を用いることでプログラムを構成するレベル毎に適した抽象手段を持つことができる。

問2.52 は手の運動なのでパス。

2.3 記号データ
シングルクォートをクォートするオブジェクトの前に置くことで、リストや記号を評価される式としてではなくデータオブジェクトとして扱うことができる

gosh> (define a '(1 2 3))
a
gosh> a
(1 2 3)
gosh> (define s1 'apple)
s1
gosh> s1
apple
gosh> (define s2 "apple")
s2
gosh> s2
"apple"
gosh> (define s 'apple)
s
gosh> s
apple

問題解答

問2.53

gosh> (list 'a 'b 'c)
(a b c)
gosh> (list (list 'george))
((george))
gosh> (cdr '((x1 x2) (y1 y2)))
((y1 y2))
gosh> (cadr '((x1 x2) (y1 y2)))
(y1 y2)
gosh> (pair? (car '(a short list)))
#f
gosh> (memq 'red '((red shoes) (blue socks)))
#f
gosh> (memq 'red '(red shoes blue socks))
(red shoes blue socks)