[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
The tree's working
The tree now correctly implements adding, removing and searching for
With optimizations on, it takes a few seconds to add 5000 entries to the
tree one at a time. I couldn't get profiling to work (for some weird reason,
the profiler will profile ok, but then it won't write me an output file).
The array that the tree is stored in is kept partially unconstructed, so
that only positions in the array that is used is constructed, and the rest
is just "raw", contentless and unconstructed memory. Construction and
destruction is done on a per-need basis (ie, when adding and removing
The tree does not take ownership of the entries it contains. It just stores
and fetches them. The way its implemented, though, makes it possible to
revise this behavior through templates extremely easily, writing no more
than a few lines to, say, make it store pointers and take over ownersip of
those pointers (deleting them when nessecary). The same thing goes for
Adding/removing is, as I've said before, quite expensive operations, taking,
by my estimate, O(n) time. Removing ALL entries at one time is a very cheap
operation (depending on the cost of destructor calls).
Again, searching is very effecient, which is what matters.
Its a bit late here, so I'll wait to tomorrow to implement hashing and
comparing hashed/non-hashed performance. Perhaps I'll also compare this new
tree to the one currently used.