🚀 go-pugleaf

In article <44504jINN43m@keats.ugrad.cs.ubc.ca>, c2a192@ugrad.cs.ubc.ca
(Kazimir Kylheku) wrote:

> > Way back when, Kazimir whines that:

> >>Clearly, this is an O(n^2) algorithm.

> >And now for your solution, please..... It's no good calling something stupid
> >without giving at least a hint at a better solution.

> My solution was still O(n^2),

So, you didn't really do any better.  Why don't you come up with a method
that doesn't use any extra space that is faster than O(n^2).

Or maybe, just maybe, you learned that O() notation isn't nearly as
important for algorithm analysis when n is small; the constants the O()
gets rid of become extremely important.

> but well over a 100 times faster.

In every case, or just the typical case for your particular application?

> All I
> did was look for the 128 highest strings in each pass, keeping their
> (16 bit) addresses in a page of 256 bytes.

And the original engineers weren't willing to use up an extra 256 bytes of
RAM.  You made classic space/time tradeoff.  I don't remember how much RAM
the original Apple's came with (I came on the scene when they had 16K of
RAM).  That is a lot of memory to dedicate to something that, by previous
arguments of yours against heap compaction (it's the same thing), just
doesn't happen very often.

For a 4K machine, you'd be wasting 6.25% of the RAM for this.

> Not possible. 8x10000 > 48x1024, right?

You had 48K, and you still needed to compact the string space?  I thought
you said that it was a rare occurance.
-- 
        Nevin ":-)" Liber       nevin@CS.Arizona.EDU    (520) 293-2799