[plt-scheme] Scheme efficiency guidelines (or: the fastest way to calc a cartesian product)
How about -
(define (cartesian-product s)
(apply append (map (lambda (x) (map (lambda (y) (cons x y)) s)) s)))
-Srikumar
On Sep 19, 2006, at 7:49 PM, plt-scheme-request at list.cs.brown.edu wrote:
> Send plt-scheme mailing list submissions to
> plt-scheme at list.cs.brown.edu
>
> To subscribe or unsubscribe via the World Wide Web, visit
> http://list.cs.brown.edu/mailman/listinfo/plt-scheme
> or, via email, send a message with subject or body 'help' to
> plt-scheme-request at list.cs.brown.edu
>
> You can reach the person managing the list at
> plt-scheme-owner at list.cs.brown.edu
>
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of plt-scheme digest..."
>
>
> [Please handle PLT Scheme list administrative tasks through the Web:
> http://list.cs.brown.edu/mailman/listinfo/plt-scheme]
>
>
> Today's Topics:
>
> 1. Re: MzScheme on the alioth benchmarks (Matthew Flatt)
> 2. Scheme efficiency guidelines (or: the fastest way to calc a
> cartesian product) ( Albert Neum?ller )
>
>
> ----------------------------------------------------------------------
>
> Message: 1
> Date: Tue, 19 Sep 2006 16:06:22 0800
> From: Matthew Flatt <mflatt at cs.utah.edu>
> Subject: Re: [plt-scheme] MzScheme on the alioth benchmarks
> To: Ewan Higgs <ewan_higgs at yahoo.co.uk>
> Cc: plt-scheme at list.cs.brown.edu
> Message-ID: <20060919080627.67F03650085 at mail-svr1.cs.utah.edu>
> Content-Type: text/plain; charset=UTF-8
>
> At Mon, 18 Sep 2006 16:04:59 +0100 (BST), Ewan Higgs wrote:
>> I took a quick glance at the
>> MzScheme scores on the Alioth benchmarks[1] to compare
>> it with Python (a popular scripting language) and
>> noticed that MzScheme wasn't doing so well.
>>
>> Has anyone looked into this before? If so, do they
>> happen to know if it's a compiler issue? Would it be
>> possible to try porting Termite to MzScheme and use a
>> Termite implementation to boost the score?
>
> I expect that Termite is implemented on top of continuations, which is
> the root of the problem for MzScheme's threads --- so porting Termite
> seems unlikely to help.
>
> Improving thread/continuation performance definitely requires changing
> the run-time system.
>
> Matthew
>
>
>
> ------------------------------
>
> Message: 2
> Date: Tue, 19 Sep 2006 13:49:23 +0200
> From: " Albert Neum?ller " <albert.neu at gmail.com>
> Subject: [plt-scheme] Scheme efficiency guidelines (or: the fastest
> way to calc a cartesian product)
> To: plt-scheme at list.cs.brown.edu
> Message-ID:
> <a66b35110609190449q7b7bc8e7l2590de8158b4dd2c at mail.gmail.com>
> Content-Type: text/plain; charset="iso-8859-1"
>
> 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://list.cs.brown.edu/pipermail/plt-scheme/attachments/
> 20060919/ffd11793/attachment.html
>
> End of plt-scheme Digest, Vol 13, Issue 28
> ******************************************
![[logo]](/logo.png){kind=logo}