Re: [racket-users] Re: Fast way to map over a list many times, changing ONE element each time?
Hi Luke, With 5000 numbers I got the numbers below with a slightly modified benchmark. If one method generates garbage and triggers a garbage collection while running the following method, then the numbers will be unfair. To avoid this I call collect-garbage before calling time. map-once method number 1: cpu time: 2832 real time: 3406 gc time: 1970 cpu time: 1895 real time: 1973 gc time: 1472 cpu time: 1941 real time: 2070 gc time: 1514 map-once method number 2: cpu time: 2212 real time: 2288 gc time: 1687 cpu time: 2320 real time: 2395 gc time: 1766 cpu time: 2344 real time: 2451 gc time: 1815 map-once method number 3: cpu time: 12547 real time: 13146 gc time: 11738 cpu time: 10687 real time: 10824 gc time: 9930 cpu time: 10615 real time: 10786 gc time: 9860 map-once method number 4: cpu time: 1718 real time: 1795 gc time: 1379 cpu time: 1796 real time: 1827 gc time: 1403 cpu time: 1751 real time: 1816 gc time: 1380 map-once method number 5: cpu time: 1311 real time: 1381 gc time: 1081 cpu time: 1346 real time: 1401 gc time: 1119 cpu time: 1375 real time: 1491 gc time: 1129 vector method: cpu time: 1063 real time: 1154 gc time: 365 cpu time: 942 real time: 1024 gc time: 366 cpu time: 921 real time: 1002 gc time: 391 #lang racket ; testing for post on racket mailing list ; https://groups.google.com/forum/#!topic/racket-users/7lkOjjpVa6A ;; Luke (define (map-once/1 f ls) (let M ([sooner null] [later ls]) (if (null? later) null (cons (append sooner (list (f (car later))) (cdr later)) (M (append sooner (list (car later))) (cdr later)) (define (list-set ls i new-val) (let-values ([(sooner later) (split-at ls i)]) (append sooner (list new-val) (cdr later (define (map-once/2 f ls) (for/list ([i (in-naturals)] [elm (in-list ls)]) (list-set ls i (f elm ;; Jon (define (map-once/3 fn xs) (for/list ([i (in-range (length xs))]) (for/list ([(x j) (in-indexed (in-list xs))]) (cond [(= i j) (fn x)] [else x] (define (map-once/v fn xs) (build-vector (vector-length xs) (λ (i) (define v (vector-copy xs)) (vector-set! v i (fn (vector-ref v i))) v))) ;; Jens (define (list-splits xs) (define (loop ys zs) ; xs = (append (reverse ys) yz) (match zs ['() '()] [(cons z zs*) (cons (list ys zs) (loop (cons z ys) zs*))])) (loop '() xs)) (define (map-once/4 f xs) (for/list ([ys+zs (list-splits xs)]) (match ys+zs [(list ys '()) '()] [(list ys (cons z zs)) (append (reverse ys) (cons (f z) zs))]))) (require (only-in srfi/1 append-reverse)) (define (map-once/5 f xs) (for/list ([ys+zs (list-splits xs)]) (match ys+zs [(list ys '()) '()] [(list ys (cons z zs)) (append-reverse ys (cons (f z) zs))]))) ;;; actual testing (define num-test-cases 5000) (define num-runs-per-f 3) (define ls (for/list ([__ (in-range num-test-cases)]) (random))) (define normal-map-onces (list map-once/1 map-once/2 map-once/3 map-once/4 map-once/5)) (for ([map-once (in-list normal-map-onces)] [i (in-naturals)]) (printf "\n\nmap-once method number ~a:\n" (+ i 1)) (for ([__ (in-range num-runs-per-f)]) (collect-garbage) (collect-garbage) (collect-garbage) (time (void (map-once sqr ls) (define v (for/vector ([__ (in-range num-test-cases)]) (random))) (printf "\n\nvector method:\n") (for ([__ (in-range num-runs-per-f)]) (collect-garbage) (collect-garbage) (collect-garbage) (time (void (map-once/v sqr v 2015-06-19 23:08 GMT+02:00 Luke Miles : > My 1000 numbers were so small that they weren't reliable. > > Change the `num-runs-per-f` and experiment yourself, if you'd like. > The code is attached. > > -- > You received this message because you are subscribed to the Google Groups > "Racket Users" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to racket-users+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. > -- -- Jens Axel Søgaard -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] Re: Fast way to map over a list many times, changing ONE element each time?
If you're willing to use vectors, then maybe you're also willing to
use a custom data structure? You could get much better performance
that way. Here's a half-baked example of what I mean. `map-once/h`,
below, returns a (normal list) of hole-lists. ("hole-list" is not a
good name. The offset doesn't really designate a hole in the list, but
the offset where the function should be applied.)
===
#lang racket/base
(require racket/match)
(struct hole-list (xs hole-offset fn))
(define (hole-list-empty? hxs)
(match hxs
[(hole-list (? pair?) _ _) #f]
[_ #t]))
(define (hole-list-nonempty? hxs)
(not (hole-list-empty? hxs)))
(define (hcar hxs)
(match hxs
[(hole-list (cons x _) 0 fn) (fn x)]
[(hole-list (cons x _) _ _) x]))
(define (hcdr hxs)
(match hxs
[(hole-list (cons _ xs) n fn) (hole-list xs (sub1 n) fn)]))
(define-match-expander hcons
(syntax-rules ()
[(_ x xs) (and (? hole-list?)
(? hole-list-nonempty?)
(app hcar x)
(app hcdr xs))]))
(define-match-expander hnull
(syntax-rules ()
[(_) (and (? hole-list?)
(? hole-list-empty?))]))
(define (hole-list->list hxs)
(match hxs
[(hnull) '()]
[(hcons x xs) (cons x (hole-list->list xs))]))
(define (map-once/h fn xs)
(for/list ([i (in-range (length xs))])
(hole-list xs i fn)))
On Fri, Jun 19, 2015 at 4:33 PM, Luke Miles wrote:
> I timed all these with `sqr` on a list of 1 `(random)`.
>
> Luke's (my) first one:
> cpu time: 4706 real time: 4699 gc time: 3673
>
> Luke's second one:
> cpu time: 5401 real time: 5393 gc time: 4136
>
> Jon's first one:
> cpu time: 9734 real time: 9728 gc time: 8007
>
> Jon's second one (tested on a vector of course):
> cpu time: 1198 real time: 1195 gc time: 883
>
> Jens' first one:
> cpu time: 5622 real time: 5618 gc time: 4800
>
> Jens' second one:
> cpu time: 4393 real time: 4391 gc time: 3935
>
>
> I thought Jens' second one would be faster. The vector's results are
> promising.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Racket Users" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to racket-users+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
--
You received this message because you are subscribed to the Google Groups
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] Re: Fast way to map over a list many times, changing ONE element each time?
My 1000 numbers were so small that they weren't reliable. Change the `num-runs-per-f` and experiment yourself, if you'd like. The code is attached. -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout. map-once.rkt Description: Binary data
Re: [racket-users] Re: Fast way to map over a list many times, changing ONE element each time?
Hi Luke, What are the result on lists of length 1000? Also can you post the benchmarking code? /Jens Axel 2015-06-19 22:33 GMT+02:00 Luke Miles : > I timed all these with `sqr` on a list of 1 `(random)`. > > Luke's (my) first one: > cpu time: 4706 real time: 4699 gc time: 3673 > > Luke's second one: > cpu time: 5401 real time: 5393 gc time: 4136 > > Jon's first one: > cpu time: 9734 real time: 9728 gc time: 8007 > > Jon's second one (tested on a vector of course): > cpu time: 1198 real time: 1195 gc time: 883 > > Jens' first one: > cpu time: 5622 real time: 5618 gc time: 4800 > > Jens' second one: > cpu time: 4393 real time: 4391 gc time: 3935 > > > I thought Jens' second one would be faster. The vector's results are > promising. > > -- > You received this message because you are subscribed to the Google Groups > "Racket Users" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to racket-users+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. > -- -- Jens Axel Søgaard -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
[racket-users] Re: Fast way to map over a list many times, changing ONE element each time?
I timed all these with `sqr` on a list of 1 `(random)`. Luke's (my) first one: cpu time: 4706 real time: 4699 gc time: 3673 Luke's second one: cpu time: 5401 real time: 5393 gc time: 4136 Jon's first one: cpu time: 9734 real time: 9728 gc time: 8007 Jon's second one (tested on a vector of course): cpu time: 1198 real time: 1195 gc time: 883 Jens' first one: cpu time: 5622 real time: 5618 gc time: 4800 Jens' second one: cpu time: 4393 real time: 4391 gc time: 3935 I thought Jens' second one would be faster. The vector's results are promising. -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
