From mboxrd@z Thu Jan  1 00:00:00 1970
Message-ID: <56156a60fc995930065001592e6f105a@vitanuova.com>
To: 9fans@cse.psu.edu
Subject: Re: [9fans] Rstat needs three size fields?
From: rog@vitanuova.com
In-Reply-To: <008601c34591$54e87200$d2944251@insultant.net>
MIME-Version: 1.0
Content-Type: text/plain; charset="US-ASCII"
Content-Transfer-Encoding: 7bit
Date: Wed,  9 Jul 2003 15:58:30 +0100
Topicbox-Message-UUID: f00af5a4-eacb-11e9-9e20-41e7f4b1d025

> > yes, tis true, but only temporarily
>
> tis true it's a god-awful algorithm.

for the kind of thing i think matt was thinking of,
something like (limbo for brevity, i'm afraid):

	items: list of Item;
	while((item := getnextitem()) != nil)
		items = item :: items;
	a := array[len items] of Item;
	for(i := 0; items != nil; items = tl items)
		a[i++] = hd items;

the amount of data copying is only O(n); if i'd been
expanding an array, it would have been O(n log n).

that's doesn't seem bad *algorithmicly* although the heap overheads
might be bad in practise.

i confess to having used this technique before.  i'm probably missing
something crucial.

why is it a "god-awful algorithm"?