diff options
Diffstat (limited to 'coding-exercises/2/60.rkt')
| -rw-r--r-- | coding-exercises/2/60.rkt | 10 |
1 files changed, 7 insertions, 3 deletions
diff --git a/coding-exercises/2/60.rkt b/coding-exercises/2/60.rkt index 3effe1c..fba2086 100644 --- a/coding-exercises/2/60.rkt +++ b/coding-exercises/2/60.rkt @@ -1,20 +1,24 @@ #lang racket ;; unordered duplicates list -;; can be use if adjoin needs to be fast O(1) -;; append is linear so union is O(n) -;; Tried to make intersection better for case with lot of duplicates and large n + +;; 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) |