欧美日韩一区二区不卡,亚洲视频专区在线,av在线电影网

　　閱讀: 766 評論: 0 作者: 周銀輝發表于 2009-12-08 21:01 原文鏈接

SICP學習筆記（2.3.3）
周銀輝

1，集合作為未排序的表

這基本上相當于在使用for或foreach語句完成所有的操作，效率自然不高。下面是采用這種方式實現的集合：

;=========集合作為未排序的表=======

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

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

(define (intersection-set set1 set2)
(cond ((or (null? set1) (null? set2)) '())
        ((element-of-set? (car set1) set2)
         (cons (car set1) (intersection-set (cdr set1) set2)))
        (else (intersection-set (cdr set1) set2))))

(define (union-set set1 set2)
(cond ((null? set1) set2)
        ((not (element-of-set? (car set1) set2))
         (cons (car set1) (union-set (cdr set1) set2)))
        (else (union-set (cdr set1) set2))))

;test
(define mySet1 '(1 3 4 2 5 7))
(define mySet2 '(1 5 8 6))
(element-of-set? 8 mySet1)
(adjoin-set 8 mySet1)
(intersection-set mySet1 mySet2)
(union-set mySet1 mySet2)

我們注意到，element-of-set?將對集合做線性遍歷，所以其時間復雜度為O(n)，那么自然地，adjoin-set 也為O(n)，而intersection-set與union-set對于set1中的每一個元素都將檢查其是否在set2中，那么其計算步數大概是n*m, 其中，n和m假設為set1和set2的元素個數，所以其時間復雜度為O(n^2)

2，集合作為未排序的表，但集合為“多重集”

所謂多重集，就是集合中的元素可以重復，重復的最大次數稱為集合的“重數”，明顯地，我們向多重集中添加元素以及求集合的并集的時候是不需要檢查元素是否已經存在的，少了檢查也就少了遍歷，這會提高效率。（但求交集時仍是需要檢查的），下面是代碼：

;=========集合作為未排序的表(多重集)=======
;about Multiset : http://en.wikipedia.org/wiki/Multiset

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

(define (adjoin-set x set)
(cons x set))

(define (union-set set1 set2)
(cond ((null? set1) set2)
(else (cons (car set1) (union-set (cdr set1) set2)))))

;test
(define mySet1 '(1 3 1 2 3 7))
(define mySet2 '(1 5 5 6))
(element-of-set? 2 mySet1)
(adjoin-set 2 mySet1)
(intersection-set mySet1 mySet2)
(union-set mySet1 mySet2)

3，集合作為排序的表（升序）

排序的好處是可以消除不必要的遍歷，比如檢查一個元素是否在集合中，其比該集合的第一個元素都小，那么它肯定不在幾何中，沒必要再和集合的其他元素比較了。下面是代碼：

;=========集合作為排序的表(升序)=======

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

(define (adjoin-set x set)
(cond ((< x (car set)) (cons x set))
((> x (car set)) (cons (car set) (adjoin-set x (cdr set))))
(else set)))

(define (intersection-set set1 set2)
(if (or (null? set1) (null? set2))
      '()
      (let ((x1 (car set1)) (x2 (car set2)))
        (cond ((= x1 x2)
               (cons x1
                     (intersection-set (cdr set1)
                                       (cdr set2))))
              ((< x1 x2)
               (intersection-set (cdr set1) set2))
              ((< x2 x1)
               (intersection-set set1 (cdr set2)))))))

(define (union-set set1 set2)
(cond ((null? set1) set2)
        ((null? set2) set1)
        (else
         (let ((x1 (car set1)) (x2 (car set2)))
           (cond ((= x1 x2)
                  (cons x1
                        (union-set (cdr set1) (cdr set2))))
                 ((< x1 x2)
                  (cons x1
                        (union-set (cdr set1) set2)))
                 ((< x2 x1)
                  (cons x2
                        (union-set (cdr set2) set1))))))))

;test
(define mySet1 '(1 3 5 7 9))
(define mySet2 '(1 2 4 6 8))
(element-of-set? 9 mySet1)
(adjoin-set 8 mySet1)
(adjoin-set 5 mySet1)
(intersection-set mySet1 mySet2)
(union-set mySet1 mySet2)

簡單解釋一下：
對于element-of-set?，如果集合為空或者待檢測元素x比集合的第一個元素都小，那么x肯定不再集合中；如果x與集合的第一個元素相等，那么x肯定在集合中（廢話~~）；否則，就檢測x是否在(cdr set)中，即檢測其是否在除去第一個元素后的子集中。這雖然也是一個線性遍歷，復雜度為O(n)，當相比于不排序而言，其不必遍歷完集合的所有元素，所以工作量會小很多。說得更直白一點就是：對于未排序的集合，當你遍歷該集合時，如果在某一時刻未找到一個元素，你只能說“到目前為止還沒找到”，并不代表將來找不到，所以你只有遍歷完整個集合后才能下結論說“的確沒有”，而排序后的集合，當你達到某個上限時，你便可以斷定“即便找下去也不會有的”，所以干脆不找了。

對于adjoin-set，向集合追加元素x時，如果元素x比集合的第一個元素小，那么直接將x放置到集合的最前面；如果x比集合的第一個元素大，那么其應該追加到(cdr set)這個子集中（別搞丟了第一個元素）；如果x和集合的第一個元素相等，那么不追加，直接將集合返回。

對于intersection-set，求集合set1和集合set2的交集，如果set1為空或set2為空，那么交集為空；設set1與set2的第一個元素分別為x1和x2，如果x1等于x2，那么將x1或者x2納為交集元素，然后繼續求(cdr set1)和(cdr set2)的交集；如果x1小于x2，那么很明顯x1被淘汰了，所以繼續拿(cdr set1)和set2做交集，同理，如果x2小于x1，那么x2被淘汰。

對于union-set，求集合set1和集合set2的并集，原理和求交集差不多，只不過不是較小的值被淘汰，而是剛好相反，較小值被納如并集中。

很明顯，上面的求交集和并集的操作的計算步驟大概是（m+n），其中m,n是set1和set2的長度，所以這兩個操作的時間復雜度是O(n)

4，集合作為二叉樹

其實不能一概而論地說這種方式好還是不好，因為這取決于具體的代碼實現，因為在遍歷二叉樹的時候很可能一不小心就寫出了一個“雙遞歸”算法，導致遍歷速度超慢，但畢竟SICP上提到的二叉樹是“平衡二叉樹”，是經過“精心排序”的，利用得好的話，則效率頗高，先貼代碼，再解釋：

;=========集合作為二叉樹=======

(define (entry tree) (car tree))

(define (left-branch tree) (cadr tree))

(define (right-branch tree) (caddr tree))

(define (make-tree entry left right)
(list entry left right))

(define (element-of-tree? x set)
(cond ((null? set) #f)
        ((= x (entry set)) #t)
        ((< x (entry set))
         (element-of-tree? x (left-branch set)))
        (else
         (element-of-tree? x (rigth-branch set)))))

(define (adjoin-tree x set)
(cond ((null? set)
         (make-tree x '() '()))
        ((= x (entry set))
         set)
        ((< x (entry set))
         (make-tree (entry set)
                    (adjoin-tree x (left-branch set))
                    (right-branch set)))
        (else
         (make-tree (entry set)
                    (left-branch set)
                    (adjoin-tree x (right-branch set))))))

;intersection-set 來自于“集合作為排序的表（升序）”

; union-set 來自于“集合作為排序的表（升序）”

(define (union-tree tree1 tree2)
(list->tree (union-set (tree->list-2 tree1) (tree->list-2 tree2))))

(define (intersection-tree tree1 tree2)
(list->tree (intersection-set (tree->list-2 tree1) (tree->list-2 tree2))))

;這個算法是一個“樹形遞歸”
(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 '()))

(define (list->tree elements)
(car (partial-tree elements (length elements))))

(define (partial-tree elts n)
(if (= n 0)
      (cons '() elts)
      (let ((left-size (quotient (- n 1) 2)))
        (let ((left-result (partial-tree elts left-size)))
          (let ((left-tree (car left-result))
                (non-left-elts (cdr left-result))
                (right-size (- n (+ left-size 1))))
            (let ((this-entry (car non-left-elts))
                  (right-result (partial-tree (cdr non-left-elts)
                                              right-size)))
              (let ((right-tree (car right-result))
                    (remaining-elts (cdr right-result)))
                (cons (make-tree this-entry left-tree right-tree)
                      remaining-elts))))))))

;-------------------test----------------------------
(define myTree1
(make-tree 7
             (make-tree 3
                        (make-tree 1 '() '())
                        (make-tree 5 '() '()))
             (make-tree 9
                        '()
                        (make-tree 11 '() '()))))
(define myTree2
(make-tree 3
             (make-tree 1 '() '())
             (make-tree 7
                        (make-tree 5 '() '())
                        (make-tree 9
                                   '()
                                   (make-tree 11 '() '())))))

(define myTree3
(make-tree 5
             (make-tree 3
                        (make-tree 1 '() '())
                        '())
             (make-tree 9
                        (make-tree 7 '() '())
                        (make-tree 11 '() '()))))

(tree->list-1 myTree1)
(tree->list-2 myTree1)

(tree->list-1 myTree2)
(tree->list-2 myTree2)

(tree->list-1 myTree3)
(tree->list-2 myTree3)

(list->tree '(1 3 5 7 9 11))
(list->tree '(1 3 5 7 8))

(define myTree4 (list->tree '(1 3 5 7 9 11)))
(define myTree5 (list->tree '(1 3 5 7 8)))

(tree->list-2 (intersection-tree myTree4 myTree5))
(union-tree myTree4 myTree5)

element-of-tree?函數和adjoin-tree函數與“集合作為排序的表（升序）”的算法是一樣的，因為這里的平衡二叉樹，實際上也是排序的，求并集和交際則是將平衡二叉樹轉化成排序的表，然后利用排序表來計算。
tree->list-1和tree->list-2的不同之處在于前者是一個雙遞歸，后者是尾遞歸（迭代的），所以兩者的效率不在一個數量級上，關于這個嘛，在SICP的1.2.2節講“樹形遞歸”的時候就已經說過了。

5，練習2.59~2.65

答案上文找

6，練習2.66

這個和 element-of-tree?函數的算法幾乎是一樣的：

(define (lookup given-key set-of-records)
(if (null? set-of-records)
      false
      (let ((r (entry set-of-records)))
        (let ((k (key r)))
          (cond ((= given-key k) r)
                ((< given-key k)
                 (lookup given-key (left-branch set-of-records)))
                ((> given-key k)
                 (lookup given-key (right-branch set-of-records))))))))

注：這是一篇讀書筆記，所以其中的內容僅屬個人理解而不代表SICP的觀點，并隨著理解的深入其中的內容可能會被修改

　　發表評論

新聞頻道：谷歌蘋果為爭奪硅谷創業公司大打出手

推薦鏈接：Windows 7專題發布

網站導航：博客園首頁個人主頁新聞社區博問閃存知識庫

文章來源:http://www.cnblogs.com/zhouyinhui/archive/2009/12/08/1618934.html

發表于 2009-12-08 21:01 fanny 閱讀(105) 評論(0) 編輯收藏