<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN"> <HTML> <HEAD> <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=ks_c_5601-1987"> <META NAME="Generator" CONTENT="MS Exchange Server version 6.5.7036.0"> <TITLE>RE: [racket] FW: q about code for partitions</TITLE> </HEAD> <BODY>  I timed a version unrolling the loops for even and odd k. I see no speed up. Just to let you know. Jos > -----Original Message----- > From: Matthew Flatt [<A HREF="mailto:mflatt@cs.utah.edu">mailto:mflatt@cs.utah.edu</A>] > Sent: domingo, 29 de junio de 2014 8:47 > To: Jens Axel S┆gaard > Cc: Jos Koot; Racket Users List > Subject: Re: [racket] FW: q about code for partitions > > It looks like "partitions2.rkt" ends up calling a contract-wrapped > variant of `exact-zero?`. If I change `ref!` to > > (define (ref! n thnk) > (let ([v (vector-ref cache n)]) > (if (zero? v) > (let ([new-v (thnk)]) > (vector-set! cache n new-v) > new-v) > v))) > > then "partitions2.rkt" is much faster. > > At Sat, 28 Jun 2014 12:06:34 +0200, Jens Axel S┆gaard wrote: > > 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: > > > > <A HREF="http://pasterack.org/pastes/12166">http://pasterack.org/pastes/12166</A> > > <A HREF="http://pasterack.org/pastes/16085">http://pasterack.org/pastes/16085</A> > > > > 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@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: > > > <A HREF="http://lists.racket-lang.org/users">http://lists.racket-lang.org/users</A> > > > > > > > > -- > > -- > > Jens Axel S┆gaard > > > > > > > -------------------------------------------------------------- > ---------------- > > [application/octet-stream "partitions2.rkt"] [~/Desktop & > open] [~/Temp & open] > > > > > > > -------------------------------------------------------------- > ---------------- > > [application/octet-stream "partitions1.rkt"] [~/Desktop & > open] [~/Temp & open] > > ____________________ > > Racket Users list: > > <A HREF="http://lists.racket-lang.org/users">http://lists.racket-lang.org/users</A> </BODY> </HTML>