> > 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. _______________________________________________ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel