blob: fba2086788a9f7fdec5f168c4c0843da0b2c4945 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
#lang racket
;; unordered duplicates list
;; linear scan of elements O(n)
(define (element-of-set? x myset)
(cond ((null? myset) false)
((equal? x (car myset)) true)
(else (element-of-set? x (cdr myset)))))
;; can be use if adjoin needs to be fast O(1)
(define (adjoin-set x myset)
(cons x myset))
;; append is linear so union is O(n)
(define (union-set set1 set2)
(append set1 set2))
(union-set (list 1 1 1 1 1 1 1 2 3) (list 2 2 2 2 2 3 'c))
;; Tried to make intersection better for case with lot of duplicates and large n by short circuiting before the linear scan overhead
;; , but it will still have O(n**2) worst case performance
;; not sure about average case
(define (intersection-set set1 set2)
(define (iter s1 s2 result)
(cond ((or (null? s1) (null? s2)) result)
((and
(not (element-of-set? (car s1) result))
(element-of-set? (car s1) s2))
(iter (cdr s1) s2 (cons (car s1) result)))
(else (iter (cdr s1) s2 result))))
(iter set1 set2 '()))
(intersection-set (list 1 2 2 2 2 2 2 2 3) (list 'a 2 1 1 1 1 1 1 1 1 'c))
|
