[racket] FW: q about code for partitions

I timed a version unrolling the loops for even and odd k. I see no speed up.
Just to let you know.
Jos


> -----Original Message-----
> From: Matthew Flatt [mailto:mflatt at cs.utah.edu] 
> Sent: domingo, 29 de junio de 2014 8:47
> To: Jens Axel Søgaard
> Cc: Jos Koot; Racket Users List
> Subject: Re: [racket] FW: q about code for partitions
> 
> It looks like "partitions2.rkt" ends up calling a contract-wrapped
> variant of `exact-zero?`. If I change `ref!` to
> 
>  (define (ref! n thnk)
>    (let ([v (vector-ref cache n)])
>      (if (zero? v)
>          (let ([new-v (thnk)])
>            (vector-set! cache n new-v)
>            new-v)
>          v)))
> 
> then "partitions2.rkt" is much faster.
> 
> At Sat, 28 Jun 2014 12:06:34 +0200, Jens Axel Søgaard wrote:
> > Hi,
> > 
> > I have converted your code to Typed Racket and made two versions.
> > The first version use a hash as cache and the second 
> version us a vector.
> > 
> > Timings show that the vector version is 1.5 to 2 times 
> slower than the
> > hash version.
> > 
> > I don't understand this. Is there anything that can be done 
> to improve it?
> > 
> > The two versions can be seen here in color:
> > 
> >     http://pasterack.org/pastes/12166
> >     http://pasterack.org/pastes/16085
> > 
> > They are also attached.
> > 
> > I used (time (begin (partitions 50000) 0)) as benchmark.
> > 
> > 
> > 
> > 
> > 2014-06-28 9:54 GMT+02:00 Jos Koot <jos.koot at gmail.com>:
> > > Sorry, forgot to post the following to the users list.
> > >
> > > Hi,
> > > count partitions, much faster and exact.
> > > You may want to put the hash or part of it within 
> function p such as to
> > > avoid spllling much memory.
> > > Jos
> > >
> > > #lang racket
> > >
> > > (require math/number-theory)
> > >
> > > (define p-hash (make-hash '((0 . 1))))
> > >
> > > (define (p n)
> > >  (hash-ref! p-hash n
> > >   (λ ()
> > >    (+
> > >     (let loop ((k 1) (m (sub1 n)) (s 0))
> > >      (if (< m 0) s
> > >       (loop (add1 k) (- m (add1 (* 3 k))) (if (odd? k) (+ 
> s (p m)) (- s (p
> > > m))))))
> > >     (let loop ((k -1) (m (- n 2)) (s 0))
> > >       (if (< m 0) s
> > >        (loop (sub1 k) (+ m (* 3 k) -2) (if (odd? k) (+ s 
> (p m)) (- s (p
> > > m))))))))))
> > >
> > > (time (for ((n (in-range 0 1000))) (p n)))
> > > (time (for ((n (in-range 0 1000))) (partitions n)))
> > > (void (time (p 10000)))
> > >
> > > (for/and ((n (in-range 0 1000))) (= (partitions n) (p n)))
> > >
> > > (read-line)
> > >
> > > ; results with racket:
> > > ; cpu time: 16 real time: 16 gc time: 0
> > > ; cpu time: 8845 real time: 8845 gc time: 111
> > > ; cpu time: 577 real time: 578 gc time: 0
> > > ; #t
> > >
> > >
> > >
> > > ____________________
> > >   Racket Users list:
> > >   http://lists.racket-lang.org/users
> > 
> > 
> > 
> > -- 
> > --
> > Jens Axel Søgaard
> > 
> > 
> > 
> --------------------------------------------------------------
> ----------------
> > [application/octet-stream "partitions2.rkt"] [~/Desktop & 
> open] [~/Temp & open]
> > 
> > 
> > 
> --------------------------------------------------------------
> ----------------
> > [application/octet-stream "partitions1.rkt"] [~/Desktop & 
> open] [~/Temp & open]
> > ____________________
> >   Racket Users list:
> >   http://lists.racket-lang.org/users
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20140629/585b3bf4/attachment-0001.html>