🚀 go-pugleaf

In article <nevin-2509951503200001@mac-nevin.cs.arizona.edu>,
Nevin ":-]" Liber <nevin@CS.Arizona.EDU> wrote:
>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).

I wasn't a very sophisticated program designer then. I didn't know much
about the analysis of algorithms. I'm sure it could have been possible
to, for instance, do an in-place sort of the string pointers using
an O(n log n) sort, and then crunch them up toward high memory. However
I did have the notion that since the machine is small, n will never
be larger than a certain upper bound, and hence you can treat it as a
constant. It was sufficient to hone the algorithm so that it's constant
improved by a factor of over 100, reducing a two-minute wait to about
a second.

>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.

Exactly. I guess I intuitively knew that.

>You had 48K, and you still needed to compact the string space?  I thought
>you said that it was a rare occurance.

The reason you _had_ to compact the space is because the string
allocator routines in the Apple II ROM would just allocate a string
beneath the free top pointer.  Each time you did a string operation, the
result would get a new place beneath the old top of heap, and the heap
top would get decremented.  There was no effort to re-use free blocks,
or to coalesce free spaces.  I determined this empirically by doing
memory dumps of the heap after certain test cases.  The allocation
methods used by the ROM _guaranteed_ that the heap would collide, even
if you did something seemingly inocuous like:

10 A$ = "A"
20 B$ = A$ : GOTO 20
 
There _might_ have been a check for assigning an equal length string, in
which case the string's existing space would simply be reused; I can't
remember.  In any case, there was simply no _room_ in the BASIC ROMs for
code do heap management of any sort.
-- 
PGP key id is 0xD3C7995D.
Molybdenum 95! Got your ounce of fission byproduct yet?