[plt-scheme] Re: scribblings on PLT Scheme 4.0

Matthew Flatt <mflatt at ...> writes:

> 
> Well, I think it was an interesting comparison. The example shows how
> replacing `append!' with `append' can lead to touching more than twice
> as much memory (and therefore suffer more than a 2x hit) without
> affecting asymptotic complexity.
> 
> Still, at this point, I'm interested in hearing about the overall
> effect on realistic programs (instead of just microbenchmarks) if
> anyone has an example to measure it.
> 
> Matthew

Oops!,

I gave you a version that I was playing with that has two appends.
You can get slightly better times with this one.

----------------------------------------------------

(define (fringe! x:xs)
  (cond
    [(null? x:xs) ()]
    [else
     (let ([x (car x:xs)][xs (cdr x:xs)])
       (cond
         [(null? x) (fringe! xs)]
         [(atom? x) (cons x (fringe! xs))]
         [else
          ((lambda (t)
             (cond
               [(not (null? t)) (append! t (fringe! xs))]
               [else (fringe! xs)]))
           (fringe! x))]))]))

-----------------------------------------------------

The ratio's between the append and append! version is the
same either way, but for completeness sake, this is the better
function.

Thanks,

--kyle
airfoil at bellsouth dot net
schemekeys.blogspot.com