On Jun 20, 2023, at 9:49 AM, Francisco José Tapia via Boost
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/indi... https://github.com/boostorg/sort/blob/develop/include/boost/sort/common/indi...*
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@lists.boost.org>) 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 Mailhttps://go.microsoft.com/fwlink/?LinkId=550986 for Windows
From: David Bien via Boostmailto:boost@lists.boost.org Sent: Thursday, June 15, 2023 12:00 PM To: boost@lists.boost.orgmailto:boost@lists.boost.org Cc: David Bienmailto:davidbien@hotmail.com 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 Boostmailto:boost@lists.boost.org Sent: Thursday, June 15, 2023 3:04 AM To: boost@lists.boost.orgmailto:boost@lists.boost.org Cc: Alexander Grundmailto:alexander.grund@tu-dresden.de 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