Re: Grace 0.51 released

[Nick Roberts <nick.roberts@acm.org>]

Simon Wright wrote:

>> [Tenet implementation will use clustering]

> I would be fairly amazed if anyone produced such an implementation in
> a general library without needing it themselves (certainly I won't for
> the BCs, partly at least because I feel I don't understand the concept
> totally!)
> 
> I guess what you have in mind is some performance requirement; state
> that, maybe Charles or the BCs or whatever will do what you want,
> maybe not ..

Clustering is applicable to unbounded lists and unbounded maps (which I 
call 'lookups'). As with other implementations, I intend to implement these 
(in Tenet) by a (doubly) linked list and a linked tree respectively. 
However, rather than having just one data element per node, as with usually 
implementations, I will have a small array -- of fixed length -- for each 
node, so that several data elements can be stored in each node (in the 
array). This array is called a 'cluster array', and the nodes are called 
'clusters'.

The basic idea is that by varying the length of the cluster array, it is 
possible to adjust the trade off between higher memory efficiency (longer 
arrays) and speed of operations (shorter arrays). At one extreme, the array 
might have length 1; obviously this is the same as the usual 
implementation. At the other extreme, one might have a very big array length.

For linked lists, each cluster (node) will be able to store the number of 
data elements actually stored in its cluster array (from 1 to N, where N is 
the cluster array length). In this way, arbitrary insertion and deletion of 
elements can be achieved by the appropriate combination of inserting or 
deleting clusters (nodes), and inserting or deleting data elements within 
cluster arrays (by moving items and/or adjusting the dynamic length).

For lookups (maps), data elements are stored within cluster arrays sorted 
by key. Insertion requires finding the correct position in the array (by 
binary-chop search), and copying up the remainder. If the array is full, a 
new cluster (node) has to be created. Deletion works the reverse way. The 
tree is kept balanced using a standard AVL or RB algorithm.

I do indeed wish to use clustering for a particular application (which will 
be called TDL, but that's another story). However, I feel that it is a very 
general-purpose technique, suitable for most applications, and that it 
should enable applications to achieve the right balance between memory and 
speed efficiency.

Are there any existing container implementations which provide clustering?

-- 
Nick Roberts