An interesting article in the July DDJ) in the Algorithm Alley:
"Fast and Small Resizable Arrays", presents a datastructure that
promises just what the subject says. Appending elements has the worst
case of O(sqrt(N)), as is the space wastage (which is the optimum, as
opposed to the usual wastage of O(N), or, more precisely, O(2N/3) when
running out of space and doubling the space and copying over). Go buy
the DDJ or see the paper "Resizable Arrays in Optimal Time and Space"
in http://db.uwaterloo.ca/~eddemain/papers/WADS99a/
(the http://daisy.uwaterloo.ca/~eddemain/papers/WADS99a/
in the article has moved)
The code listing is at http://www.ddj.com/ftp/2001/2001_07/aa0701.txt
--
$jhi++; # http://www.iki.fi/jhi/
# There is this special biologist word we use for 'stable'.
# It is 'dead'. -- Jack Cohen
