[fpc-devel] Generic Programming Units

[Marco van de Voort]

> > I would make that the contnrs unit. I think it belongs more together with 
> > objects such as a stack and queue...
> > 
> > What is the performance difference between a hash() and a binary search on 
> > an ordered list ? I've also been working with an 'associative' stringlist, but
> > I was using an ordered stringlist to keep the data, so a binary search is done.
> 
> Depends how the hash is parametrized. If you've a big hash array and a
> good hash function accessing has a complexity of O(1)
> while for a binary
> search it's O(log(n))

This is no fair comparison, since you compare an unsafe way (hash) with a 
safe one (bintree). 

So this only if you have a number of buckets close to the number of elements
and a perfect hash. Otherwise you need log(n1/nbuckets) extra comparisons.
(assuming you do conflict resolving using bintree)

Note also that bintree is a bit outdated since most datastructures texts
measure datastructures in comparisons. However _if_ some of your comparisons
are not equal in speed the spectrum changes.

Compare e.g. a bintree to a quadtree.

type
 pbintree = ^tbintree;
 tbintree = record
		value: array [0..0] of integer; // one int
		ptrs: array[0..1] of pbintree;  
			// left right is more traditional but this is clearer
		end;

 pquadtree= ^tquadtree;
 tquadtree = record
		value: array [0..2] of integer; // one int
		ptrs: array[0..3] of pquadtree;  
			// left right is more traditional but this is clearer
		end;

The bintree does about log(n) comparisons. So does the quadtree. (it must do
more comparisons per record, but the tree depth is about proportionally
less). However the per record quadtree comparisons are cached, making it 
faster AND more memory intensive.