[plt-scheme] Fractals

Thanks so much for the help!

I improved one little bit of my inner calculation (just switching the
order of two checks, one of which was likely to be much faster on
average) and in practice see a significant speedup (more than twice as
fast).

So I agree, changing my O(n^3) algorithms and making them O(n^2 ln n)
instead, even if the constant is bigger, is the first thing to do;
implementing them in C is last.  But it's good to know how to do it!

Mostly right now the obvious place for big speedup is in my collision
detector (given a new segment, see if it hits one of a bunch of old
ones).  That's a well-known algorithm and ought to be really fast.

Also I use atan in my convex hull algorithm instead of just using y/x
to figure out the smallest slope.  That's another obvious potential
speedup.  Oddly, in timing it, I just made DrScheme unexpectedly
quit!?  Or maybe it was just a freak occurrence.  Let's see.

> (define stuff (build-list 100000 (lambda (x) (make-posn (add1 (random 100)) (add1 (random 100))))))
> (time (begin (map (lambda (p) (atan (/ (posn-y p) (posn-x p)))) stuff)
               'done))

Nope, no crash this time.
The same code without atan runs in about 2/3 the time (200 msec vs 300).
So ... maybe the loop overhead is dominating?  I can't believe that /
is really that close in speed to atan.  Hm, but I was using integers.
Using floats still about the same thing (add1 -> + 1.01 ...), 180 msec
vs 250.

Interesting!

Anyway, none of these kinds of speedups will solve the fundamental
problem of blindly doing exponential-time searches ... so I have to
think too, more's the pity.

Again, thanks to all for your help.
--Joshua Zucker