[racket] Mutable state vs RAM on fire

On May 2, 2012, at 3:05 PM, joshua at anwu.org wrote:

> 
> Hey all,
> 
> Been playing around with some code to multiply polynomials to calculate dice probabilities.
> Is based on a paper by Doron Zeilberger that I read years ago and can't find at the moment.
> 
> My first attempt represented polynomials as lists of coefficient/exponent pairs.
> I tried to make it completely functional, with no set! operations.  You can see it here:
> 
> https://github.com/TurtleKitty/Dice/blob/2fff16e198cb84d725c786ecc624fb9b9468e778/dice.rkt
> 
> It worked, but only to a point.  At 9 or 10 dice, it started blowing up the RAM in my machine.
> I swear I smelled smoke.  It grabbed like 4G and slowed to a crawl.


poly-deg, addterms, and poly-simp can be replaced with one function like this: 

(define (poly-simp p)
  (define-values (a n q)
    (for/fold ((a 0) (n 0) (q '())) ((x (sort p < #:key cdr)))
      (define b (car x))
      (define k (cdr x))
      (if (= n k)
          (values (+ a b) n q)
          (values b k (cons (cons a n) q)))))
  (cons (cons a n) q))

I don't know how to run your stress test, so I will leave this to you. I am not sure it will cut the time. 


> Knowing that the Perl and Javascript versions of this program can calculate distributions for 300 dice in the space of a heartbeat,
> I rewrote the thing to use vectors instead, and altered the polynomial multiplication function to use (begin) and (vector-set!):
> 
> https://github.com/TurtleKitty/Dice/blob/67c2b49707132395f73b43afe111e3904b3898f2/dice.rkt
> 
> It too now calculates three hundred dice without breaking a sweat, but... I feel dirty.


It's also wrong and stylistically bad: 

(define (poly-mul p1 p2)
  (define deg1 (poly-deg p1))
  (define deg2 (poly-deg p2))
  (define noob (make-vector (- (+ deg1 deg2) 1)))
  ;; MF: bug, these were 1s: 
  (for* ([i (in-range 0 deg1)] [j (in-range 0 deg2)])
    (define k (+ i j))
    (define a  (* (vector-ref p1 i) (vector-ref p2 j)))
    (vector-set! noob k (+ (vector-ref noob k) a)))
  noob)



> Can anyone recommend a functional approach that won't melt my motherboard?
> I'm considering hashes, since they have the immutable version of hash-set that vectors seem to lack, but I thought I'd ask the experts.


Do try hash and for/hash. I think you will be pleased with the performance. -- Matthias

p.s. Do report back.