[plt-scheme] Scheme efficiency guidelines (or: the fastest way to calc 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))
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20060919/ffd11793/attachment.html>