[racket] FW: q about code for partitions

Thanks for the conversion. I hope the code can be useful.

Strange timing differences. I would expect a vector to be faster, but I am no expert on the inside of Racket. Looking at profiles with (partitions 10000) I see no special parts taking relatively exorbitant much more time in one version than in the other one. 

Sorry I can't help you on this. Maybe experts of the team can shed light?

Best wishes, Jos

 

> -----Original Message-----
> From: jensaxelsoegaard at gmail.com 
> [mailto:jensaxelsoegaard at gmail.com] On Behalf Of Jens Axel Søgaard
> Sent: sábado, 28 de junio de 2014 12:07
> To: Jos Koot
> Cc: Neil Toronto; Racket Users List
> Subject: Re: [racket] FW: q about code for partitions
> 
> 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
>