Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!ucsd!pacbell.com!pacbell!osc!jgk
From: jgk@osc.COM (Joe Keane)
Newsgroups: comp.lang.functional
Subject: Re: Id array comprehensions revisited
Message-ID: <3076@osc.COM>
Date: 19 Jul 90 08:19:07 GMT
References: <51369@iuvax.cs.indiana.edu>
Reply-To: jgk@osc.COM (Joe Keane)
Organization: Object Sciences Corp., Menlo Park, CA
Lines: 22

I don't think array initialization such as the one described is necessarily
linear.  If we think of an array as a monolithic object, then yes the updates
must happen sequentially.  However if the array is somehow divided into
pieces, it is clear that we know which updates could affect a given piece, so
the pieces can be constructed independently, although it takes time to put
them together.

There are simple algorithms to do insertion and deletion in arrays, but they
become slow with large arrays.  To avoid linear time in such operations you
have to use more sophisticated data structures, using a divide-and-conquer
approach.  The array is hierarchically broken down into smaller pieces which
are better handled with simple algorithms.  This sort of indexing is done by
B-trees, 2-3 trees, splay trees, etc.

It is interesting that this same change also solves the parallelism problem.
The initialization of the array will follow the structure of the data
structure, because the different parts at each node in the hierarchy can be
done independently.

This does it in logarithmic time, which is the best we can do assuming that in
a given amount of time a computation can only fork off a limited number of
parallel sub-computations.