The vector grows only once, so that's not it. Below is a version where vector-ref! was removed. This brings the timings closer to each other. It seems that the hash version still is slightly faster though.
Is there anything else that can be improved? #lang typed/racket/base (provide partitions reset-partitions-cache) (require math/private/number-theory/types) ;;; Partitions are computed using Euler's algorithm: ; k k(3k+1) k(3k-1) ; p(n) = sum (-1) [ p( n - --------- ) + p( n - --------- ) ] ; k>=1 2 2 ; http://en.wikipedia.org/wiki/Partition_(number_theory) (define cache-size 1) (: cache (Vectorof Integer)) (define cache (make-vector cache-size 0)) (vector-set! cache 0 1) (: reset-partitions-cache : -> Void) (define (reset-partitions-cache) (set! cache-size 1) (make-vector cache-size 0) (set! cache (make-vector cache-size 0)) (vector-set! cache 0 1)) (: grow-cache : Natural -> Void) (define (grow-cache n) (cond [(> cache-size n) (void)] [else (define n+1 (+ n 1)) (define new-cache (make-vector n+1 0)) (vector-copy! new-cache 0 cache) (set! cache-size n+1) (set! cache new-cache)])) (: loop1 : Integer Integer Integer -> Integer) (define (loop1 k m s) (cond [(< m 0) s] [else (loop1 (+ k 1) (- m (+ (* 3 k) 1)) (if (odd? k) (+ s (p m)) (- s (p m))))])) (: loop2 : Integer Integer Integer -> Integer) (define (loop2 k m s) (cond [(< m 0) s] [else (loop2 (- k 1) (+ m (* 3 k) -2) (if (odd? k) (+ s (p m)) (- s (p m))))])) (: p : Integer -> Integer) (define (p n) (define cached (vector-ref cache n)) (cond [(exact-zero? cached) (define pn (+ (loop1 1 (- n 1) 0) (loop2 -1 (- n 2) 0))) (vector-set! cache n pn) pn] [else cached])) (: partitions : Integer -> Integer) (define (partitions n) (cond [(< n 0) 0] [else (grow-cache n) (p n)])) 2014-06-28 16:26 GMT+02:00 Neil Toronto <neil.toro...@gmail.com>: > 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 >> -- -- Jens Axel Søgaard ____________________ Racket Users list: http://lists.racket-lang.org/users
