练习 2.60

element-of-set

书本 103 页的 element-of-set? 函数可以同时用于重复元素和无重复元素两个版本,它的复杂度为 \(\Theta(N)\)

;;; p103-element-of-set.scm

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

测试

1 ]=> (load "p103-element-of-set.scm")

;Loading "p103-element-of-set.scm"... done
;Value: element-of-set?

1 ]=> (element-of-set? 5 (list 1 3 5 7 9 7 5 3 1))

;Value: #t

1 ]=> (element-of-set? 10086 (list 1 3 5 7 9 7 5 3 1))

;Value: #f

adjoin-set

重复元素版本的 adjoin-set 不必检查要加入的元素是否存在于列表,它只需简单地将新元素和表用 cons 组合起来就行了,复杂度为 \(\Theta(1)\) ;无重复版本因为要检查元素是否存在,所以复杂度为 \(\Theta(N)\)

;;; 60-adjoin-set.scm

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

测试:

1 ]=> (load "60-adjoin-set.scm")

;Loading "60-adjoin-set.scm"... done
;Value: adjoin-set

1 ]=> (adjoin-set 1 (list 2 3 4))

;Value 11: (1 2 3 4)

1 ]=> (adjoin-set 1 (list 1 3 5 7 9))

;Value 12: (1 1 3 5 7 9)

union-set

练习 2.59 的无重复元素集合的 union-set 同样也可以用于有重复元素集合,这个函数的复杂度为 \(\Theta(N^2)\)

;;; 59-union-set.scm

(load "p103-element-of-set.scm")

(define (union-set set1 set2)
    (iter (append set1 set2) '()))

(define (iter input result)
    (if (null? input)
        (reverse result)
        (let ((current-element (car input))
              (remain-element (cdr input)))
            (if (element-of-set? current-element result)
                (iter remain-element result)
                (iter remain-element
                      (cons current-element result))))))

测试:

1 ]=> (load "59-union-set.scm")

;Loading "59-union-set.scm"...
;  Loading "p103-element-of-set.scm"... done
;... done
;Value: iter

1 ]=> (union-set '(1 2 3) '(3 4 5 6))

;Value 11: (1 2 3 4 5 6)

1 ]=> (union-set '() '(1 2 3))

;Value 12: (1 2 3)

intersection-set

有重复元素集合的 intersection-set 函数和无重复元素集合的 intersection-set 很相似,但是重复元素集合的 intersection-set 还需要增加一个条件:如果某个元素在两个输入列表中都存在的话,那么还要检查它在已有的结果表中是否存在,如果在结果表里已经有了这个元素,那么就忽略它,否则,就将它加入结果表:

;;; 60-intersection-set.scm

(load "p103-element-of-set.scm")

(define (intersection-set set another)
    (define (iter set result)
        (if (or (null? set) (null? another))
            (reverse result)
            (let ((current-element (car set))
                  (remain-element (cdr set)))
                (if (and (element-of-set? current-element another)
                         (not (element-of-set? current-element result)))
                    (iter remain-element
                          (cons current-element result))
                    (iter remain-element result)))))
    (iter set '()))

重复元素集合的 intersection-set 函数的复杂度和无重复元素集合的 intersection-set 函数一样,都是 \(\Theta(N^2)\) (虽然多了一个对结果表的检测,但是复杂度不变)。

测试:

1 ]=> (load "60-intersection-set.scm")

;Loading "60-intersection-set.scm"...
;  Loading "p103-element-of-set.scm"... done
;... done
;Value: intersection-set

1 ]=> (intersection-set '() (list 1 2 3))

;Value: ()

1 ]=> (intersection-set (list 1 2 3) (list 1 2 3))

;Value 14: (1 2 3)

1 ]=> (intersection-set (list 1 2 1 2) (list 1 2 1 2))

;Value 15: (1 2)

效率

以下是有重复元素集合和无重复元素集合的几个函数的复杂度对比:

函数 element-of-set? adjoin-set union-set intersection-set
无重复 \(\Theta(n)\) \(\Theta(n)\) \(\Theta(n^2)\) \(\Theta(n^2)\)
有重复 \(\Theta(n)\) \(\Theta(1)\) \(\Theta(n^2)\) \(\Theta(n^2)\)
是否可以共用 不是 不是

可以看出,在复杂度方面,有重复元素集合的 adjoin-set 比无重复元素集合的 adjoin-set 要低一个量级,除此之外,两个版本的其他操作的复杂度都是一样的。

不过尽管如此,在有重复元素的集合进行 element-of-set?union-setintersection-set ,算法的系数会比无重复元素的集合要高,随着重复元素的不断增多,带重复元素的集合进行以上三个操作将会越来越慢。

因此,对于插入操作频繁的应用来说,可以使用有重复元素的集合,而对于频繁进行查找、交集、并集这三个操作的应用来说,使用无重复元素的集合比较好。

讨论

blog comments powered by Disqus