[racket] FW: q about code for partitions

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
>