<html><body><div style="color:#000; background-color:#fff; font-family:times new roman, new york, times, serif;font-size:12pt">Hi Sylvain,<br><br>I just saw this email by chance, not sure why it didn't show up bigger in the inbox...<br><br><br>http://www.cplusplus.com/reference/algorithm/nth_element/<br><br>Quote: <br>The
other elements are left without any specific order, except that none of
the elements preceding nth are greater than it, and none of the
elements following it are less.<br><br>So your comment regarding Guarantees cannot be correct.<br>Please check your code again, I assume there is some other problem that is the source of the issue.<br><br>cheers,<br>Paul<br><div><span><br></span></div><div style="display: block;" class="yahoo_quoted"> <br> <br> <div style="font-family: times new roman, new york, times, serif; font-size: 12pt;"> <div style="font-family: times new roman, new york, times, serif; font-size: 12pt;"> <div dir="ltr"> <font face="Arial" size="2"> On Sunday, 24 November 2013 10:19 PM, Sylvain Bougerel <sylvain.bougerel.devel@gmail.com> wrote:<br> </font> </div> <div class="y_msg_container"><div id="yiv4051790362"><div><div dir="ltr">Hi Sebastien and others,<div><br clear="none"></div><div>I will retry with the new addresses.</div><div><br clear="none"></div><div>The real reason why I wanted the latest sources was to do performance comparisons between libkdtree++ and
spatial (<a rel="nofollow" shape="rect" target="_blank" href="https://sourceforge.net/projects/spatial/">https://sourceforge.net/projects/spatial/</a>).</div>
<div><br clear="none"></div><div>During the course of the performance comparisons, I insert 1000000 points in 3 or 9 dimensions and watch how the 2 libraries behave, on insertion and insertion with optimization.</div><div><br clear="none"></div><div>
This has lead me to the discovery of one bug very important bug and its fix. Spatial originally (a year ago) suffered from the same issue, so I was able to identify it quickly.</div><div><br clear="none"></div><div>In the KDTree::_M_optimize, the body in the version I have is:</div>
<div><br clear="none"></div><div><div> template <typename _Iter></div><div> void</div><div> _M_optimise(_Iter const& __A, _Iter const& __B,</div><div> size_type const __L)</div><div>
{</div><div> if (__A == __B) return;</div><div> _Node_compare_ compare(__L % __K, _M_acc, _M_cmp);</div><div> _Iter __m = __A + (__B - __A) / 2;</div><div> std::nth_element(__A, __m, __B, compare);</div>
<div> this->insert(*__m);</div><div> if (__m != __A) _M_optimise(__A, __m, __L+1);</div><div> if (++__m != __B) _M_optimise(__m, __B, __L+1);</div><div> }</div></div><div><br clear="none"></div><div>But it should be:</div>
<div><br clear="none"></div><div><div><div> template <typename _Iter></div><div> void</div><div> _M_optimise(_Iter const& __A, _Iter const& __B,</div><div> size_type const __L)</div>
<div> {</div><div> if (__A == __B) return;</div><div> _Node_compare_ compare(__L % __K, _M_acc, _M_cmp);</div><div> _Iter __m = __A + (__B - __A) / 2;</div><div> std::partial_sort(__A, __m, __B, compare);</div>
<div> this->insert(*__m);</div><div> if (__m != __A) _M_optimise(__A, __m, __L+1);</div><div> if (++__m != __B) _M_optimise(__m, __B, __L+1);</div><div> }</div></div></div><div><br clear="none"></div><div>
(notice the change from std::nth_element to std::partial_sort)</div><div><br clear="none"></div><div>Using nth_element here is a erroneous, because it does not guarantee that everything in the sequence [__A, __m) is lower than _m nor that everything in the sequence (__m, __B] is greater than __m. This is expected from the algorithm because it operates on a subset where the point sorted along the dimension __L % __K are strictly ordered around the pivot __m.</div>
<div><br clear="none"></div><div>In practice nth_element does "some" sorting around the pivot __m and this bug was not noticeable when inserting less than 10,000 elements. I started to get different results between some random nearest neighbor queries at 10,000 elements. At 1,000,000 elements, efficient_insert_and_optimize started to crash with Segmentation Faults on Linux.</div>
<div><br clear="none"></div><div><div>Replacing nth_element by partial_sort fixes the issues described above, because partial_sort enforces the guarantee needed here.</div></div><div><br clear="none"></div><div>If the current maintainers agree with the proposed changes, I'd like to request their good will to apply the changes on my behalf in the source. To top it off, I think, a long time ago (5 years may be?), I may have been the one proposing to replace a previous std::sort by std::nth_element (I remember a conversation with Paul on this)... So I might even have introduced the bug in the first place :(</div>
<div><br clear="none"></div><div>According to my current experiments, at the moment libkdtree++ cannot be assumed to maintain its invariant throughout the tree after a call to _M_optimize(). If you are a user of optimization in libkdtree++ with large data sets, then you have probably experienced this issue, if the code above is the one you are using.</div>
<div><br clear="none"></div><div>Best Regards,</div><div>Sylvain</div></div><div class="yiv4051790362gmail_extra"><br clear="none"><br clear="none"><div class="yiv4051790362yqt4093622849" id="yiv4051790362yqtfd49028"><div class="yiv4051790362gmail_quote">On Sun, Nov 24, 2013 at 9:41 PM, Sebastian Ramacher <span dir="ltr"><<a rel="nofollow" shape="rect" ymailto="mailto:sebastian+lists@ramacher.at" target="_blank" href="mailto:sebastian+lists@ramacher.at">sebastian+lists@ramacher.at</a>></span> wrote:<br clear="none">
<blockquote class="yiv4051790362gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div class="yiv4051790362im">On 2013-11-24 21:20:25, Sylvain Bougerel wrote:<br clear="none">
> Thank you Sebastien, I will wait a bit then.<br clear="none">
<br clear="none">
</div>It should be back up:<br clear="none">
<a rel="nofollow" shape="rect" target="_blank" href="https://lists.debian.org/debian-infrastructure-announce/2013/11/msg00002.html">https://lists.debian.org/debian-infrastructure-announce/2013/11/msg00002.html</a><br clear="none">
<br clear="none">
Regards<br clear="none">
<span class="yiv4051790362HOEnZb"><font color="#888888">--<br clear="none">
Sebastian Ramacher<br clear="none">
</font></span><br clear="none">_______________________________________________<br clear="none">
libkdtree-devel mailing list<br clear="none">
<a rel="nofollow" shape="rect" ymailto="mailto:libkdtree-devel@lists.alioth.debian.org" target="_blank" href="mailto:libkdtree-devel@lists.alioth.debian.org">libkdtree-devel@lists.alioth.debian.org</a><br clear="none">
<a rel="nofollow" shape="rect" target="_blank" href="http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/libkdtree-devel">http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/libkdtree-devel</a><br clear="none"></blockquote></div><br clear="none"></div></div></div></div><br><div class="yqt4093622849" id="yqtfd37319">_______________________________________________<br clear="none">libkdtree-devel mailing list<br clear="none"><a shape="rect" ymailto="mailto:libkdtree-devel@lists.alioth.debian.org" href="mailto:libkdtree-devel@lists.alioth.debian.org">libkdtree-devel@lists.alioth.debian.org</a><br clear="none"><a shape="rect" href="http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/libkdtree-devel" target="_blank">http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/libkdtree-devel</a></div><br><br></div> </div> </div> </div> </div></body></html>