Re: Adding 'indirect_sort' to boost::algorithm

From: Francisco José Tapia (fjtapia_at_[hidden])
Date: 2023-06-20 16:49:45

 Hi, I'm Francisco Tapia, from the Sort Library.

I would like to point out a couple of things about indirect sort

1- The name is not very correct, since indirect sort is usually used for a
process in which an ordered index is created and later, we physically order
the elements that we have ordered logically in an index.  Indirect sorting
is useful with large objects, where it is much more expensive to move the
object than to compare it.

In the library, it was studied but its use was discarded, because when the
data is almost ordered (data added at the beginning or end, or some
elements whose value has been modified) the final step of passing from
logical ordering with an index to a physical ordering, greatly increases
the times with respect to direct ordination. If you are interested in it,
you can find the code of the discarded implementation at
*https://github.com/boostorg/sort/blob/develop/include/boost/sort/common/indirect.hpp
<https://github.com/boostorg/sort/blob/develop/include/boost/sort/common/indirect.hpp>*

2.- It would be more correct and expressive for users to create index.  And
the most suitable and simple place for users to find is the Sort Library. I
have created a repository with a very simple implementation of such a
function. The index is a simple vector of iterators.  You can find it
at *https://github.com/fjtapia/create_index
<https://github.com/fjtapia/create_index>*

It is a basic version (ideas and suggestions are welcome), but can you give
us an idea about how to do it?

Francisco

El jue, 15 jun 2023 a las 20:15, David Bien via Boost (<
boost_at_[hidden]>) escribió:

> Wrt (1) I guess you’d have to use something other than iota() since it
> takes a cue from the initialized size of the array – necessitating initial
> throwaway initialization of the elements.
>
> bien
>
> Sent from Mail<https://go.microsoft.com/fwlink/?LinkId=550986> for Windows
>
> From: David Bien via Boost<mailto:boost_at_[hidden]>
> Sent: Thursday, June 15, 2023 12:00 PM
> To: boost_at_[hidden]<mailto:boost_at_[hidden]>
> Cc: David Bien<mailto:davidbien_at_[hidden]>
> Subject: Re: [boost] Adding 'indirect_sort' to boost::algorithm
>
> A couple of things.
>
>
>   1.  It seems you are initializing the indices of the Permutation <ret>
> return twice – first to 0 and then to the position in iota(). An
> optimization would be to first declare an empty Permutation and then
> reserve() the count of elements you want and then call iota().
>   2.  In my former codebase I had a similar indirect_sort() that accepted
> an input array of indices instead of generating them inside the method.
> This allows a “select and then indirect_sort this set of indices” which is
> what I generally used.
>   3.  (this less important but just an aside) I also implemented two other
> types of indirect sort in my old code base due to necessity. A “pointer to
> element” sort – this allows sorting on post-iterator-access elements –
> allowing sorting of elements stored in non-indexable iterators. Also an
> “offset sort” which is more or less like the pointer-to-element sort but
> allowed sorting of sub-fields of elements (though thinking about it now I
> don’t remember how I did this and I no longer have access to the code). I
> used the “pointer to element” sort the most of the time – the size of an
> 64bit index and a pointer are usually the same so no loss in terms of
> storage – the return is a set of sorted pointer-to-elements.
> bien
>
> Sent from Mail<
> https://na01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgo.microsoft.com%2Ffwlink%2F%3FLinkId%3D550986&data=05%7C01%7C%7Cb05ca86255704e0564e508db6dca57fe%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C638224488055949615%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=O4stdx5U6GfpW0jfVok2GFmQI7FLQXM2NS6%2B%2B%2FLJ9tc%3D&reserved=0
> <https://go.microsoft.com/fwlink/?LinkId=550986>> for Windows
>
> From: Alexander Grund via Boost<mailto:boost_at_[hidden]>
> Sent: Thursday, June 15, 2023 3:04 AM
> To: boost_at_[hidden]<mailto:boost_at_[hidden]>
> Cc: Alexander Grund<mailto:alexander.grund_at_[hidden]>
> Subject: Re: [boost] Adding 'indirect_sort' to boost::algorithm
>
> > So you are adding a building block to have such a "cosort".
> > You're just missing a way to apply that reordering to several
> > (random-access) collections.
>
> There already is: Basically you first do an indirect sort and then use
> `boost::algorithm::apply_permutation` on each collection with the result
> permutation.
> See the test case and documentation of indirect_sort.
>
> Alex
>
>
> _______________________________________________
> Unsubscribe & other changes:
> https://na01.safelinks.protection.outlook.com/?url=http%3A%2F%2Flists.boost.org%2Fmailman%2Flistinfo.cgi%2Fboost&data=05%7C01%7C%7Cb05ca86255704e0564e508db6dca57fe%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C638224488055949615%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=8xi35vQdmkaAeZZswWGxKX0Uyxa19s8IPf3%2Bg7nnNhc%3D&reserved=0
> <http://lists.boost.org/mailman/listinfo.cgi/boost>
>
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>