<div dir="ltr"><br><div class="gmail_quote"><div dir="ltr"><div class="gmail_quote"><div class="Ih2E3d">2008/10/17 Sylvain Bougerel <span dir="ltr"><<a href="mailto:sylvain.bougerel.devel@gmail.com" target="_blank">sylvain.bougerel.devel@gmail.com</a>></span><br>
</div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div>On Fri, Oct 17, 2008 at 10:42 AM, Paul Harris <<a href="mailto:paulharris@computer.org" target="_blank">paulharris@computer.org</a>> wrote:<div><div></div><div class="Wj3C7c"><br>
> do the math, for each iteration you will need to still walk the tree. first<br>
> time would be the same speed, after the the iteration might be faster, but<br>
> at the end of the day - visitor would only need to walk it once.<br>
><br>
> plus, the iterator may be difficult to configure for different tasks.<br>
><br>
> having said that, the cost of extra computation may be outweighed by the<br>
> benefit of the convenience of the iterator<br>
><br>
<br>
</div></div></div><div><div></div><div class="Wj3C7c">Well, I not convinced about that. May be I'm like St Thomas: I need to<br>
see it first :-). IMHO neither a well written iterator nor a well<br>
written visitor should be slower: the complexity for both should be<br>
the same and for both it should be: n.log(n) ... I think :-P.<br>
<br>
At least, it's the conclusion I can come up with with my limited<br>
knowledge on algorithms. I'll try it and see.<br>
<font color="#888888"><br>
Sylvain<br>
</font></div></div></blockquote></div><br><br>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.<br>
<br>the visitor pattern helps to extend algorithms. lets say you want to find the 5 nearest points,<br><br>you could write a<br>find_nearest_5_points()<br><br>or you can do<br>visit_nearest( visitor_collect_5_nearest_points() );<br>
<br>and the visitor specification doesn't have to be built into kdtree ... extensions via templates - very efficient<br><br><br>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.<br>
<br>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<br>
<br>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.<br>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.<br>
<br>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.<br><br>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<br>
son: "i'm looking in the bakery section"<br>you: "no, its not there. cull that section"<br>son: "ok they have some nice chocolates"<br>you: "no, just go to the cold section"<br>
<br>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.<br></div></div><br></div>