[plt-scheme] Scheme efficiency guidelines (or: the fastest way tocalc a cartesian product)
If you use the appropriate tools, cartesian-product can be written in one single line of 93 characters, unnecessary spaces included.
((((lambda(x)((((((x x)x)x)x)x)x))
(lambda(x)(lambda(y)(x(x y)))))
(lambda(x)(write x)x))
"greetings, Jos")
----- Original Message -----
From: Albert Neumüller
To: plt-scheme at list.cs.brown.edu
Sent: Tuesday, September 19, 2006 1:49 PM
Subject: [plt-scheme] Scheme efficiency guidelines (or: the fastest way tocalc a cartesian product)
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)
In Scheme
~~~~~~~~~~
(define-struct onepair (left right))
(define set1 (build-list 2 identity)) = (list 0 1)
(cartesian-product set1)
=
(list (make-onepair 0 0)
(make-onepair 0 1)
(make-onepair 1 0)
(make-onepair 1 1))
There are incredibly many ways of writing a definition which does the cartesian product!
And these definitions can be reordered and rearranged and changed (local etc.) in MANY ways.
Below are a few examples.
Are there some efficiency guidelines for coding in Scheme? (Especially when considering the scheme code below:)
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?)
Is it better to build up a list in normal order or reverse order?
Isn't the use of append, to be avoided when possible?
(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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20060919/3288eef0/attachment.html>
![[logo]](/logo.png){kind=logo}