From 5254a0befde355fca2711033f77047cf0bb5c08f Mon Sep 17 00:00:00 2001 From: Mike Vink Date: Mon, 27 Mar 2023 21:58:09 +0200 Subject: moar --- coding-exercises/2/60.rkt | 10 +++++++--- 1 file changed, 7 insertions(+), 3 deletions(-) (limited to 'coding-exercises/2/60.rkt') 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) -- cgit v1.2.3