If you're inserting a list of malloc'ed memory chunks into a binary tree, you should make sure that the tree is self-balancing: inserting a stream of sorted objects (assuming you're using the address of the malloc'ed object as a key, a list of subsequent malloc()s will be "ordered") will create a *very* unbalanced binary tree (i.e. worst case performance - you're basically doing an insertion sort).
I see where you're getting at. I am using a hash function to generate a hash but I didn't realise that my trees would actually look more like lists if I inserted sorted data until you pointed it out. In reality though we would get random but unique numbers.
This would be where I'd start looking: the long runtime is typical of a malformed tree.
It's probably not the cause as my CPU utilisation is very low (even on the processor that the process is running on). Later on I did intend on looking at some models to balance the tree but that would further increase my runtime to O(log n). Maybe potentially unbalanced trees would still perform better than balancing at every insert? I'm also in the process of implementing an iterative (as opposed to a recursive) binary tree insertion.
(Oh, and 100,001 isn't prime either. Using 100,003 may make your hash a little more efficient. Or not. :)
:P Haven't seriously looked into finding a good prime number yet hehe.
John
_______________________________________________ coders mailing list [email protected] http://lists.slug.org.au/listinfo/coders
