书本 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
不必检查要加入的元素是否存在于列表,它只需简单地将新元素和表用 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)
练习 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
还需要增加一个条件:如果某个元素在两个输入列表中都存在的话,那么还要检查它在已有的结果表中是否存在,如果在结果表里已经有了这个元素,那么就忽略它,否则,就将它加入结果表:
;;; 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-set
和 intersection-set
,算法的系数会比无重复元素的集合要高,随着重复元素的不断增多,带重复元素的集合进行以上三个操作将会越来越慢。
因此,对于插入操作频繁的应用来说,可以使用有重复元素的集合,而对于频繁进行查找、交集、并集这三个操作的应用来说,使用无重复元素的集合比较好。