Possible culprit: growing the vector by 1 instead of by powers of 2. Also, vector-ref! may not be especially fast. In particular, it always applies a higher-order function, but hash-ref! only does that when an entry is missing.
Neil Sent from my iPhone > On Jun 28, 2014, at 7:04 AM, "Jos Koot" <jos.k...@gmail.com> wrote: > > 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
