Majority voting in find_nearest()

[Paul Harris]

2008/10/17 Sylvain Bougerel <sylvain.bougerel.devel at gmail.com>

> On Fri, Oct 17, 2008 at 10:42 AM, Paul Harris <paulharris at computer.org>
> wrote:
>
> > do the math, for each iteration you will need to still walk the tree.
>  first
> > time would be the same speed, after the the iteration might be faster,
> but
> > at the end of the day -  visitor would only need to walk it once.
> >
> > plus, the iterator may be difficult to configure for different tasks.
> >
> > having said that, the cost of extra computation may be outweighed by the
> > benefit of the convenience of the iterator
> >
>
> Well, I not convinced about that. May be I'm like St Thomas: I need to
> see it first :-). IMHO neither a well written iterator nor a well
> written visitor should be slower: the complexity for both should be
> the same and for both it should be: n.log(n) ... I think :-P.
>
> At least, it's the conclusion I can come up with with my limited
> knowledge on algorithms. I'll try it and see.
>
> Sylvain
>


the difference is that the visitor is able to collect the data it needs in
one sweep of the tree.  as it goes it can snip the tree search space and
thus be more efficient than scanning the whole tree.

the visitor pattern helps to extend algorithms.   lets say you want to find
the 5 nearest points,

you could write a
find_nearest_5_points()

or you can do
visit_nearest( visitor_collect_5_nearest_points() );

and the visitor specification doesn't have to be built into kdtree ...
extensions via templates - very efficient


the iterator pattern on the other hand ... yes it can do a second and third
sweep faster because it knows what it can cull, but you will still have to
start from the root (or a leaf via your back-forwards technique) and walk
*some* of the nodes.  thats additional work the visitor didn't have to do.

it took me a while to comprehend the power of visitor because you have to
flip your solution inside out... in a metaphor lets say kdtree is a
supermarket, and you have a shopping list which consists of 5 types of milk

the iterator you speak of is like going into the supermarket, finding the
milk, buying 1 bottle. leaving the store, and then going back in again 4
more times.
first time you have to hunt for the milk, the next 4 times, you know where
the milk is and you go straight to the milk... but you STILL have to go in
and out of the shop, walk past all the checkouts, etc.

the visitor pattern is like sending your teenage son there.  you have to
tell him what to get first before he enters the store, and when he does find
the milk, he gets all 5 bottles and leaves with them all.

if we were to enhance the visitor pattern support in kdtree, it would be
like giving the son a walkietalkie, and as he goes you could modify his
behaviour
son: "i'm looking in the bakery section"
you: "no, its not there.  cull that section"
son: "ok they have some nice chocolates"
you: "no, just go to the cold section"

i don't think i know exactly how you will do the iterator, just give it a go
and we shall see how it works out.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.alioth.debian.org/pipermail/libkdtree-devel/attachments/20081017/de29643c/attachment.htm