Optimising optimise()

[Paul Harris]

The problem is that at each level, the set of items has to be resorted and
divided according to a different key, so rebalancing is (IIRC) non-trivial.

However, there are sure to be ways to improve its performance.  I was
thinking of sorting the items once for each key, and then using tags to
eliminate or mark off uninteresting items at each level.  Trading scanning
O(n) for lots of extra sorting O(nlogn).

there are sure to be other ways too

i have a problem where i have to search a tree and then remove items from
the tree.  instead of using erase etc, i use find_nearest_if() and pass it a
functor that checks that the node hasn't been tagged as 'removed'.  so it'll
effectively ignore items that I want erased.

2008/5/3 Eric Fowler <eric.fowler at gmail.com>:

> Well I have noticed that running optimise() on a tree of half a million
> points seems to take twice as long (or more) than building the tree from
> zero.
>
> So why run it? I was under the impression that removal of elements from a
> tree with erase() or erase_exact() left the tree in a undefined condition so
> further searches might miss points. Is that right? Or is optimise() just
> about performance, not correctness?
>
> If that is the case, perhaps the tree could be extended so when an item is
> removed, the tree flags the highest node that is above everything in need of
> optimisation, so optimise() can search the tree only for subtrees that
> really need the treatment, thus saving time.
>
> Just my $0.02.
>
> Eric
>
> _______________________________________________
> libkdtree-devel mailing list
> libkdtree-devel at lists.alioth.debian.org
> http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.alioth.debian.org/pipermail/libkdtree-devel/attachments/20080505/246c7dd8/attachment.htm