Hi Eric, Thanks for taking a look.
On my computer (mac) your vector version is 3 times faster than the hash one: cpu time: 189 real time: 189 gc time: 3 cpu time: 53 real time: 53 gc time: 0 cpu time: 186 real time: 185 gc time: 3 cpu time: 58 real time: 58 gc time: 0 cpu time: 199 real time: 204 gc time: 2 cpu time: 56 real time: 56 gc time: 0 cpu time: 200 real time: 205 gc time: 3 cpu time: 58 real time: 57 gc time: 0 cpu time: 181 real time: 180 gc time: 2 cpu time: 64 real time: 64 gc time: 0 #t /Jens Axel 2014-06-28 18:10 GMT+02:00 Eric Dobson <eric.n.dob...@gmail.com>: > I took a look and for a while nothing I did sped it up, (likely > already racket was doing the optimizations I was doing by hand). But I > got a factor of 4 speed up on the vector code over the hash code by > not checking for exact 0, but instead using #f as the sentinal value. > Growing the vector by a a factor of 2 had some improvement as well but > didn't get the vector code faster than the hash code. > > https://gist.github.com/shekari/3bccee6e0d5948181f1a > > On Sat, Jun 28, 2014 at 8:43 AM, Jos Koot <jos.k...@gmail.com> wrote: >> When calling partitions once only the vector grows once only. Another case >> is when partitions is called many times with increasing argument. In that >> case the vector has to be copied every time. Therefore I would prefer the >> mutable hash. >> >> I have thought of combining the two seperate loops for negative and positive >> k into one loop, but as it is not certain that the loops have the same >> length, this complicates the loop with an extra if-clause cq cond-clause. >> >> Nevertheless, I think the main gain is obtained by using a recurrent formula >> for the computation of >> (- n (* k (add1 (* 3 k)))) and >> (- n (* k (sub1 (* 3 k)))) and >> more importantly avoiding to compute >> (/ (+ 1.0 (flsqrt (+ 1.0 (* 24.0 n)))) 6.0) >> for every instance the partitions count has not yet been memorized. >> It where the inexact operations that made me think. >> >> Another thing that could be tried is to sepatare both loops for even and odd >> k such as to avoid the test on the partity of k. I did not (yet) try that. >> This would lead to a total of 4 loops. >> >> Anyway, code should be readable and fast (in that order). Therefore >> complicating the code much for a slight gain of speed may be the wrong thing >> to do. MHO >> >> 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 16:51 >>> To: Neil Toronto >>> Cc: Jos Koot; Racket Users List >>> Subject: Re: [racket] FW: q about code for partitions >>> >>> 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 -- -- Jens Axel Søgaard ____________________ Racket Users list: http://lists.racket-lang.org/users
