[Feature request] Methods for sorting/reordering with indices

mbhall88 · November 8, 2021, 2:40am

Hi,

I'm enquiring as to whether two new methods would be of interest to the standard library.

The first is a method (argsort?) for getting the indices that would sort a slice/vector - akin to argsort in numpy (this SO question sums up this method).

The second is a method (sort_by_indices?) for sorting a slice/vector by given indices (such as the output of another slice's argsort; see this SO question).

I would be happy to have a go at implementing both (or one) if they seem in scope.

jhpratt · November 8, 2021, 4:37am

I've never even heard of these methods let alone use them. What's the use case?

fbstj · November 8, 2021, 8:25am

I would guess it might help sorting column-oriented data; where you grab the argsort of one column and then apply it to each of the others?

SadiinsoSnowfall · November 8, 2021, 9:11am

It could be interesting when you want to sort two slices using the same order, for exemple, let's say you have

let mut keys = [0, 2, 1, 3];
let mut values = ["d_val0", "c_val2", "b_val1", "a_val3"];
keys.sort_unstable();
values.???;

And you want to sort both slice "the same way", you can't just sort the values slice, or else you will get &["a_val3", "b_val1", "c_val2", "d_val0"] instead of &["d_val0", "b_val1", "c_val2", "a_val3"].

(ex: rust - How can I co-sort two Vecs based on the values in one of the Vecs? - Stack Overflow)

Luro02 · November 8, 2021, 9:18am

The problem with proposing new additions to the standard library is that you have to justify why this method must be in the standard library and can not exist as a utility function/crate.

In general only functions/methods are added that are definitely useful for a large number of people, otherwise one would have dead-code in the standard library.

Another problem is "what if the method was not the right decision?" and one later on regrets adding it to the standard library?

One can not remove (as far as I know) methods from the standard library through an edition, so the best thing one could do would be to deprecate it.

A lot of deprecated methods add noise to the documentation which makes reading the docs a bit more annoying with every new deprecated method.

So what I want to say with this, is that one has to think really carefully about which methods should be added to the standard library and you need to give very convincing arguments how this could be used.

I would recommend adding a few examples to your post that show how one could use it.

A working implementation with an extension trait on play.rust-lang.org would be very appreciated as well.

quinedot · November 8, 2021, 9:39am

More generally, sort_by_indices is the act of applying a[n inverse] permutation.

IndianBoy42 · November 8, 2021, 10:06am

I don't think it should be called sort_by_indices. Because you are not necessarily sorting it, you are just reordering (or permuting) the array.

djc · November 8, 2021, 10:20am

See also crates like GitHub - jeremysalwen/rust-permutations: Permutations library for Rust.

FWIW, I've wanted this functionality before. Right now, reordering requires cloning or copying, but it would be great if there was some general interface that would allow sorting based on an external order.

The code where I wanted it is here: instant-distance/lib.rs at main · InstantDomain/instant-distance · GitHub. In this case, I wanted to randomly order values of a generic type, and in this case I had to impose a Clone bound because there is no (straightforward) way to sort based on the generated random numbers (at least I wasn't able to figure one out).

nacaclanga · November 8, 2021, 1:34pm

Argsort is a function to get an array of indices that describe the order of the elements in an array. This index array can then be used to rearrange multiple arrays in the same manner.

A sample implementation can be found here: Rust Playground

steffahn · November 8, 2021, 3:11pm

It seems to me like the best way to apply a permutation to a slice in-place is to first have the permutation in represented according to cycle notation. Then you don't need that scratchpad anymore that the SO answer was talking about.

If the usage pattern is: create a permutation for one unsorted slice and apply it to multiple slices, then creating an optimal¹ representation of the permutation first seems like the correcte approach.

¹optimal for the application of in-place reordering slices

This approach would mean that an abstract "Permutation" datatype would be used instead of just a list/array of indices. This also seems suficciently specific to be better fitted for a custom crate than the standard library.

H2CO3 · November 8, 2021, 6:15pm

These are very common in array-oriented numeric code.

scottmcm · November 8, 2021, 7:05pm

I think the library already has code that does this for sort_by_cached_key, so it might be reasonable to expose it so long as it works for that use.

github.com

rust-lang/rust/blob/495322d776fd6f679cd8cd4ca02b8fa834da654b/library/alloc/src/slice.rs#L411-L434

    
      
          pub fn sort_by_cached_key<K, F>(&mut self, f: F)
          where
              F: FnMut(&T) -> K,
              K: Ord,
          {
              // Helper macro for indexing our vector by the smallest possible type, to reduce allocation.
              macro_rules! sort_by_key {
                  ($t:ty, $slice:ident, $f:ident) => {{
                      let mut indices: Vec<_> =
                          $slice.iter().map($f).enumerate().map(|(i, k)| (k, i as $t)).collect();
                      // The elements of `indices` are unique, as they are indexed, so any sort will be
                      // stable with respect to the original slice. We use `sort_unstable` here because
                      // it requires less memory allocation.
                      indices.sort_unstable();
                      for i in 0..$slice.len() {
                          let mut index = indices[i].1;
                          while (index as usize) < i {
                              index = indices[index as usize].1;
                          }
                          indices[i].1 = index;

This file has been truncated. show original

leonardo · November 8, 2021, 8:58pm

Something similar is worth adding to Rust stdlib.

mbhall88 · November 8, 2021, 10:08pm

Thank you all for the feedback.

@Luro02

I would recommend adding a few examples to your post that show how one could use it.

A working implementation with an extension trait on play.rust-lang.org would be very appreciated as well.

Here is an example of something I used in a recent tool. I can transfer this to a playground if you want though. (I realise this may not be an ideal implementation.)

github.com

mbhall88/psdm/blob/0c8c4be5e4a6d566193b688824197fac2d233108/src/lib.rs#L13-L41


      
          trait SortExt<T> {
              fn argsort(&self) -> Vec<usize>;
              fn sort_by_indices(&mut self, indices: &mut Vec<usize>);
          }
          
          impl<T: Ord + Clone> SortExt<T> for Vec<T> {
              fn argsort(&self) -> Vec<usize> {
                  let mut indices = (0..self.len()).collect::<Vec<_>>();
                  indices.sort_by_key(|&i| &self[i]);
                  indices
              }
          
              fn sort_by_indices(&mut self, indices: &mut Vec<usize>) {
                  for idx in 0..self.len() {
                      if indices[idx] != usize::MAX {
                          let mut current_idx = idx;
                          loop {
                              let target_idx = indices[current_idx];
                              indices[current_idx] = usize::MAX;
                              if indices[target_idx] == usize::MAX {

This file has been truncated. show original

And some associated tests

github.com

mbhall88/psdm/blob/0c8c4be5e4a6d566193b688824197fac2d233108/src/lib.rs#L255-L283


      
          #[test]
          fn argsort() {
              let v = vec![1, 7, 4, 2];
              let i = v.argsort();
              assert_eq!(i, &[0, 3, 2, 1]);
          }
          
          #[test]
          fn argsort_with_str() {
              let v = vec!["a", "c", "B", "-"];
              let i = v.argsort();
              assert_eq!(i, &[3, 2, 0, 1]);
          }
          
          #[test]
          fn argsort_on_empty() {
              let v: Vec<u8> = vec![];
              let i = v.argsort();
              assert!(i.is_empty());
          }

This file has been truncated. show original

@IndianBoy42

I don't think it should be called sort_by_indices. Because you are not necessarily sorting it, you are just reordering (or permuting) the array.

Well the definition of "sort" depends on the comparison function you are using. But I agree with you, there is probably a more descriptive way to name it. reorder, permute etc.

system · February 6, 2022, 10:09pm

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.

Topic		Replies	Views
`positions()` method for slices, or iterators in general libs	3	915	March 25, 2019
Add a "Vec.sorted()" function	27	10645	June 12, 2020
Fallible sorting language design	11	1728	May 8, 2022
Pre-RFC-ish: add Vec::sorted and friends libs	7	1465	March 25, 2019
Should slice.swap() require unpin	4	683	January 19, 2020

[Feature request] Methods for sorting/reordering with indices

Related topics