in Antarctica

いろんなメモ

SICP

SICP勉強会してるので、 気が向いたら知見書いていけたらなぁと

exe2.63

(define (tree->list-1 tree)
    (if (null? tree)
        '()
        (append (tree->list-1 (left-branch tree))
                        (cons (entry tree)
                              (tree->list-1 (right-branch tree))))))

(define (tree->list-2 tree)
    (define (copy-to-list tree result-list)
        (if (null? tree)
            result-list
            (copy-to-list (left-branch tree)
                          (cons (entry tree) 
                                (copy-to-list (right-branch tree) result-list)))))
    (copy-to-list tree '()))

問題はtree->list1とtree->list2が同じリストを生成するのか、 オーダーはどうかである。 生成されるリストは順序ありリストという縛りがある。

前者は、生成されるリストは 一意に決定されるので、一つに定まる。

後者は、 tree->list1は

f:id:g-hyoga:20170207154923p:plain

こんな感じの順番で評価される

tree->list2は

f:id:g-hyoga:20170207155013p:plain

はこんな感じ.

これだけの違いしかなく、 それぞれ要素数nの場合 tree->list1はn回、 tree->list2(copy-to-list)もn回呼ばれる。

ここでtree->list1はappendを用いてlistの結合をしているので、 さらにO(n)かかる。 tree->list2はconsで済んでいる。

結果的にtree->list1は O(n2)、 tree->list2は O(n)

ハフマン木が面白かったから、 そこまで書こうと思ったけど疲れたから終わり