Adam Wulkiewicz via Boost-users <boost-users@lists.boost.org> writes:
> W dniu 13.07.2021 o 17:04, Jens Thiele via Boost-users pisze: >> Another problem I face now is that each run produces different results >> which is still correct (multiple linestrings might have the same >> distance to some point) but I would prefer a reproducible result. >> >> I guess the cause for this is that >> rtree_t::const_query_iterator it=t->qbegin(idx::nearest(pt, tree_size)); >> returns an iterator where the order isn't stable. >> Would it be difficult to fix the iteration order? > The rtree can have different internal structure depending on balancing > algorithm and the order of inserts. So unless you know that values are > always inserted in the same order it's impossible to guarantee that > the structure is going to be the same. Then the order is also > determined by the internals of the iterator, how exactly the rtree is > traversed, how nodes and values are prioritized based on distance. And > yes, currently heap and sort is used and I plan to replace sort with > minmax heap for performance. Neither of these is stable. > > But I don't understand what do you mean by "each run" and "stable > order"? What the stability refers to? Could you give an example? Problem solved. The details: The test basically does the following: 1) create r-tree 2) knn search of some points to linestrings 3) repeat 2 and compare results Now a few points have the same distance to multiple linestrings and in those cases I saw some random ordering of the linestrings in the knn search results. But: it wasn't the query iterator that introduced that randomness it was the priority queue in the case where linestrings had the same distance => priority. To break the tie I now additionally use the ID of the linestring => no more random ordering. Jens _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org https://lists.boost.org/mailman/listinfo.cgi/boost-users
