[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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: partitions2.rkt
Type: application/octet-stream
Size: 2137 bytes
Desc: not available
URL: <http://lists.racket-lang.org/users/archive/attachments/20140628/b1f5c1bd/attachment-0002.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: partitions1.rkt
Type: application/octet-stream
Size: 1322 bytes
Desc: not available
URL: <http://lists.racket-lang.org/users/archive/attachments/20140628/b1f5c1bd/attachment-0003.obj>