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 ____________________ Racket Users list: http://lists.racket-lang.org/users
