Geometry Boost List: Re: [geometry] partial_sort vs nth_element in the rtree implementation

Subject: Re: [geometry] partial_sort vs nth_element in the rtree implementation
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2014-02-28 08:08:26

Hi,

IMPORTANT!
Boost was moved to GitHub some time ago. SVN trunk has become GIT 
develop branch. You can browse it here: 
https://github.com/boostorg/geometry/tree/develop.

If you'd like to switch to GIT, here's some tutorial: 
https://svn.boost.org/trac/boost/wiki/TryModBoost
So to use Boost.Geometry develop branch with Boost you need to replace 
the last commends mentioned on the page above to something like this:

cdmodular-boost/libs/geometry
git checkout develop
git pull

and probably again run

./b2 headers

but, back to the subject.

Lu Wang wrote:
> Hi all,
>
>    I'm now reading the source code of the rtree implementation in 
> boost::geometry, especially in pack_create.hpp 
> <http://svn.boost.org/svn/boost/trunk/boost/geometry/index/detail/rtree/pack_create.hpp>, 
> I found that std::partial_sort is used to find the median along the 
> longest dimension, which is then used to split the array and perform 
> the splitting recursively:
>
>   // pack_create.hpp, around line 281
>   partial_sort(first, median, last, ...);
>
>   per_level_packets(first, median, ...);
>   per_level_packets(median, last, ...);
>
>
>
>   It seems to me that the sortedness of the first half is never used, 
> in this case, I guess that std::partial_sort may be replaced by 
> std::nth_element, which should be faster.
>

Thanks for catching this! Tests passed, code pushed.

>   Is there any particular reason that partial_sort is used?

No, I must have been under the mental influence of the R* ;).

The speedup is nice, ~4x faster for 1M random boxes.

I remember that someone on the list raised the issue of the small 
preformance difference between linear split and packing algorithm some 
time ago. Please recheck.

Regards,
Adam