[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