Ordered sets are speedy

Kevin Day, June 2nd, 2007

Right now I’m reading Structure and Interpretation of Computer Programs, and I just finished the section on representing sets of data. Before reading this book I wouldn’t have thought much about this problem, but it turns out that your code can run a lot faster if you order your sets before manipulating them.

For example, if you want to find the union of two sets without repeating any elements, an unordered representation of sets will require a O(n²) process, wheras an ordered representation of sets can use a O(n) process. I’m guessing that most comp sci majors know this stuff well, but it was a neat surprise to me.

For anyone else reading SICP, here’s my answers to problems 2.59 and 2.62:

2.59. Implement the union-set operation for the unordered-list representation of sets:

(define (union-set set1 set2)
  (define (element-of-set? x set)
    (cond ((null? set) false)
   ((equal? x (car set)) true)
   (else (element-of-set? x (cdr set)))))
  (cond ((null? set1) set2)
 ((element-of-set? (car set1) set2)
  (union-set (cdr set1) set2))
 (else (cons (car set1) (union-set (cdr set1) set2)))))

2.62. Give a O(n) implementation of union-set for sets represented as ordered lists.

(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 set1 (cdr set2)))))))))

0 comments (tags: comp-sci, lisp)