Re: Adding 'indirect_sort' to boost::algorithm

From: Marshall Clow (mclow.lists_at_[hidden])
Date: 2023-06-26 03:04:28

On Jun 20, 2023, at 9:49 AM, Francisco José Tapia via Boost <boost_at_[hidden]> wrote:
> 
> 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?

I thought about putting this into Boost.sort.
It may be that that is the best place for it - I don’t know.

One use case that has come up in the discussion is the ability to apply the index
to multiple sequences (a ’struct of arrays’ - see the docs in the PR), and creating an
index that contains iterators (rather than positions) doesn’t help with that.

Also, I worry about discoverability - someone who is looking to sort something
probably won’t look at a function named `create_index`. :-(

— Marshall

P.S.  The deadline for “new features/major code changes” for the next Boost release is coming up this week….

> 
> 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().

Ok.

>>  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
>> 
> 
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost