[racket] FW: q about code for partitions

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.dobson at 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.koot at 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: jensaxelsoegaard at gmail.com
>>> [mailto:jensaxelsoegaard at 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.toronto at 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.koot at 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: jensaxelsoegaard at gmail.com
>>> >>> [mailto:jensaxelsoegaard at 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.koot at 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