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: jensaxelsoega...@gmail.com > [mailto:jensaxelsoega...@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.k...@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 > ____________________ Racket Users list: http://lists.racket-lang.org/users
