[plt-scheme] Scheme efficiency guidelines (or: the fastest way to calc a cartesian product)
On Sep 19, 2006, at 7:49 AM, Albert Neumüller wrote:
> Hello!
>
> An invitation:
> How would you write the fastest possible scheme program that
> computes the cartesian product of a set?
>
> Example:
> =================
>
> set1 = {0, 1}
>
> then
>
> cartesian_product = {(0, 0), (0, 1), (1, 0), (1, 1)}
>
>
> Note:
> If set1 has n elements (cardinality 2), then cartesian_product will
> have 2^n pairs (cardinality 2^n)
{0,1} x {a,b,c} = {(0,a),(0,b),(0,c),(1,a),(1,b),(1,c)}
looks like n x m to me.
> Are there some efficiency guidelines for coding in Scheme?
> (Especially when considering the scheme code below:)
Follow the design recipe and read chapter IV in HtDP to get an idea
of "loops" i.e. functions that act on each item in a list (or other
form of structure). Most of the code you get will be just fine for
small sets (a couple of hundred or so elements). It'll become a one-
liner then.
For your next phase, you need to study two things: (1) algorithms and
data structures [a taste of that is in chapter V] and (2) performance
analysis. If your set library turns out to be a bottleneck, study up
on set representations (hash tables, trees, etc).
> Some questions in my mind are:
> Is it better to use an unchanging parameter in a recursive function
> (just passing it through the whole time), or is it better to use a
> local?)
For beginners, I definitely recommend the extra parameter (using a
local to combine the two functions).
> Is it better to build up a list in normal order or reverse order?
If you build it in reverse order from what you need, your program
must use another pass to reverse the list. (I bet there is context
that you're not including with your question.)
> Isn't the use of append, to be avoided when possible?
The use of append sometimes reflects a data representation that's
inappropriate. If it were to be avoided at all cost, it wouldn't be
included with the standard library, right? :-)
Overall: worry about designing programs systematically (this will
often also give you good performance, the design recipe is tuned to
that), then learn to measure performance and how to improve your data
structures when needed.
-- Matthias
>
> (weblink??)
>
>
> Any comments or suggestions will be appreciated!
>
> Kind regards,
> Albert Neumüller
> (The present author has been writing scheme code for 2.5 months and
> is still learning [HTDP])
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
> ;; Data Definition:
>
> ;; A SV is a Scheme value
>
>
> (define-struct onepair (left right))
> ;; A onepair is a structure : (make-onepair l r), where l and r are
> SV (scheme-values)
>
>
>
> ;;===================================================
> ;;cartesian-product1 : (listof SV) -> (listof onepair)
> (define (cartesian-product1 alist)
> (do-cartesian1 alist alist alist))
>
> ;;do-cartesian1 : (listof SV) (listof SV) (listof SV) -> (listof
> onepair)
> (define (do-cartesian1 x y alist)
> (cond
> [(empty? x) empty]
> [(empty? y) (do-cartesian1 (rest x) alist alist)]
> [else (cons (make-onepair (first x) (first y))
> (do-cartesian1 x (rest y) alist))]))
> ;;===================================================
>
> ;; In do-cartesian1 the 3rd parameter ( alist) does not change.
> Hence we can put it into a local:
>
> ;;===================================================
> ;;cartesian-product1b : (listof SV) -> (listof onepair)
> (define (cartesian-product1b alist)
> (local ((define (do-cartesian1b x y)
> (cond
> [(empty? x) empty]
> [(empty? y) (do-cartesian1b (rest x) alist)]
> [else (cons (make-onepair (first x) (first y))
> (do-cartesian1b x (rest y)))])))
> (do-cartesian1b alist alist)))
> ;;===================================================
>
> ;; In do-cartesian1b, the same value (first x) is used in repeated
> recursions (over y). Hence we can pass it as a parameter x-single:
>
> ;;===================================================
> ;;cartesian-product1c : (listof SV) -> (listof onepair)
> (define (cartesian-product1c alist)
> (local ((define (do-cartesian1c x-single x-rest y)
> (cond
> [(empty? y) (cond
> [(empty? x-rest) empty]
> [else (do-cartesian1c (first x-rest)
> (rest x-rest) alist)])]
> [else (cons (make-onepair x-single (first y))
> (do-cartesian1c x-single x-rest (rest
> y)))])))
> (cond
> [(empty? alist) empty]
> [else (do-cartesian1c (first alist) (rest alist) alist)])))
> ;;===================================================
>
> ;; If order does not matter then we can use, where we end up with a
> reversed result:
>
> ;;===================================================
> ;;cartesian-product2 : (listof SV) -> (listof onepair)
> (define (cartesian-product2 alist)
> (local ((define (do-cartesian2 x y growing-result)
> (cond
> [(empty? x) growing-result]
> [else (do-cartesian2 (rest x)
> y
> (cartesian-with-fixed-x2 (first
> x) y growing-result))]))
> (define (cartesian-with-fixed-x2 single-x y growing-result)
> (cond
> [(empty? y) growing-result]
> [else (cons (make-onepair single-x (first y))
> (cartesian-with-fixed-x2 single-x (rest
> y) growing-result))])))
> (do-cartesian2 alist alist empty)))
> ;;===================================================
>
> ;; In do-cartesian2 the 2nd parameter (y) is always equal to the
> outer paremeter alist, hence we can remove it:
> ;; (unfortunately cartesian-product2b actually seems to perform
> worse than cartesian-product2!! why?)
>
> ;;===================================================
> ;;cartesian-product2b : (listof SV) -> (listof onepair)
> (define (cartesian-product2b alist)
> (local ((define (do-cartesian2b x growing-result)
> (cond
> [(empty? x) growing-result]
> [else (do-cartesian2b (rest x)
> (cartesian-with-fixed-x2b
> (first x) alist growing-result))]))
> (define (cartesian-with-fixed-x2b single-x y growing-result)
> (cond
> [(empty? y) growing-result]
> [else (cons (make-onepair single-x (first y))
> (cartesian-with-fixed-x2b single-x (rest
> y) growing-result))])))
> (do-cartesian2b alist empty)))
> ;;===================================================
>
> ;; In cartesian-with-fixed-x2b, the 3rd parameter is fixed. Hence
> we can use a local:
>
> ;;===================================================
> ;;cartesian-product3 : (listof SV) -> (listof onepair)
> (define (cartesian-product3 alist)
> (local ((define (do-cartesian3 x growing-result)
> (cond
> [(empty? x) growing-result]
> [else (do-cartesian3 (rest x)
> (local ((define (cartesian-with-
> fixed-x3 single-x y)
> (cond
> [(empty? y) growing-
> result]
> [else (cons (make-
> onepair single-x (first y))
>
> (cartesian-with-fixed-x3 single-x (rest y)))])))
> (cartesian-with-fixed-x3
> (first x) alist)))])))
> (do-cartesian3 alist empty)))
> ;;===================================================
>
> ;; In cartesian-with-fixed-x3, the 1st parameter ( single-x) doesn
> not change. Hence we can add it to a local expression:
>
> ;;===================================================
> ;;cartesian-product3b : (listof SV) -> (listof onepair)
> (define (cartesian-product3b alist)
> (local ((define (do-cartesian3b x growing-result)
> (cond
> [(empty? x) growing-result]
> [else (do-cartesian3b (rest x)
> (local ((define single-x (first x))
> (define (cartesian-with-
> fixed-x3b y)
> (cond
> [(empty? y) growing-
> result]
> [else (cons (make-
> onepair single-x (first y))
>
> (cartesian-with-fixed-x3b (rest y)))])))
> (cartesian-with-fixed-x3b
> alist)))])))
> (do-cartesian3b alist empty)))
> ;;===================================================
>
>
> ;; Using append
>
> ;;===================================================
> ;;cartesian-product4 : (listof SV) -> (listof onepair)
> (define (cartesian-product4 alist)
> (local ((define (do-cartesian4 x)
> (cond
> [(empty? x) empty]
> [else (append (do-cartesian4 (rest x))
> (cartesian-with-fixed-x4 (first x)
> alist))]))
> (define (cartesian-with-fixed-x4 single-x y)
> (cond
> [(empty? y) empty]
> [else (cons (make-onepair single-x (first y))
> (cartesian-with-fixed-x4 single-x (rest
> y)))])))
> (do-cartesian4 alist)))
> ;;===================================================
>
> ;; Swapping arguments of append (faster):
>
> ;;===================================================
> ;;cartesian-product4b : (listof SV) -> (listof onepair)
> (define (cartesian-product4b alist)
> (local ((define (do-cartesian4b x)
> (cond
> [(empty? x) empty]
> [else (append (cartesian-with-fixed-x4b (first x) alist)
> (do-cartesian4b (rest x)))]))
> (define (cartesian-with-fixed-x4b single-x y)
> (cond
> [(empty? y) empty]
> [else (cons (make-onepair single-x (first y))
> (cartesian-with-fixed-x4b single-x (rest
> y)))])))
> (do-cartesian4b alist)))
> ;;===================================================
>
> ;; In cartesian-with-fixed-x4b, the 1st parameter (single-x) does
> not change. Hence we pull it into a local:
>
> ;;===================================================
> ;;cartesian-product4c : (listof SV) -> (listof onepair)
> (define (cartesian-product4c alist)
> (local ((define (do-cartesian4c x)
> (cond
> [(empty? x) empty]
> [else (append (local ((define single-x (first x))
> (define (cartesian-with-fixed-
> x4c y)
> (cond
> [(empty? y) empty]
> [else (cons (make-onepair
> single-x (first y))
> (cartesian-with-
> fixed-x4c (rest y)))])))
> (cartesian-with-fixed-x4c alist))
> (do-cartesian4c (rest x)))]))
> )
> (do-cartesian4c alist)))
> ;;===================================================
>
> (define mylist (build-list 2 identity))
>
> (cartesian-product1 mylist)
> (cartesian-product1b mylist)
> (cartesian-product1c mylist)
> (cartesian-product2 mylist)
> (cartesian-product2b mylist)
> (cartesian-product3 mylist)
> (cartesian-product3b mylist)
> (cartesian-product4 mylist)
> (cartesian-product4b mylist)
> (cartesian-product4c mylist)
>
>
> ;(time (cartesian-product1 mylist))
> ;(time (cartesian-product1b mylist))
> ;(time (cartesian-product1c mylist))
> ;(time (cartesian-product2 mylist))
> ;(time (cartesian-product2b mylist))
> ;(time (cartesian-product3 mylist))
> ;(time (cartesian-product3b mylist))
> ;(time (cartesian-product4 mylist))
> ;(time (cartesian-product4b mylist))
> ;(time (cartesian-product4c mylist))
>
>
> _________________________________________________
> For list-related administrative tasks:
> http://list.cs.brown.edu/mailman/listinfo/plt-scheme
![[logo]](/logo.png){kind=logo}