`<[T]>::sort_by_index` and `<[T]>::sort_by_key_and_index`

libs
1

What do you think about chances of getting something like sort_by_index into std?

pub fn sort_by_index<K, F>(&mut self, mut f: F)
where
    F: FnMut(usize) -> K,
    K: Ord;

pub fn sort_by_key_and_index<K, F>(&mut self, mut f: F)
where
    F: FnMut(usize, &T) -> K,
    K: Ord;

pub fn sort_unstable_by_index<K, F>(&mut self, mut f: F)
where
    F: FnMut(usize) -> K,
    K: Ord;

pub fn sort_unstable_by_key_and_index<K, F>(&mut self, mut f: F)
where
    F: FnMut(usize, &T) -> K,
    K: Ord;

// and `cached` too?

One possible use case is to sort one array by keys from some other array. It comes up very frequently for me, and for data oriented programming in general. permutation - Rust can do this, but it requires computing intermediate permutation and additional heap space.

I don't see a good way for it to be an external crate, as it would basically have to reimplement the sorting form std.

1 Like
2

Any implementation of this needs to allocate a temporary vector of indices and sort that. There is no reasonable way of doing this in place.

3

Why? You can just subtract pointers and pass the index to caller, isn't it?

4

The indices will be changing during sorting as you're swapping elements.

2 Likes
5

Oh :sweat_smile:

Well, then unstable case is impossible Indeed.

6

To avoid internal allocation you could oblige caller to supply a scratch array of [usize; N].

EDIT: Concretely, suppose we added this function to slices

/// for 0 <= i < self.len() move item i to position permutation[i]
/// panics if self.len() != permutation.len()
/// (if possible make that a type constraint)
/// or if permutation is not actually a permutation of 0..self.len()
pub fn permute(&mut self, permutation: &[usize])

then I think the existing <[usize]>::sort_(unstable_)by_key could do the rest of the job?

7

Note that https://doc.rust-lang.org/std/primitive.slice.html#method.sort_by_cached_key does that internally, so maybe you could find a way to encode it in that?

Though that doesn't guarantee the order of the calls to the key generator (just that it's at most once per item), so you can't just calculate the index inside the closure.

8

Maybe some API may be composed in order to sort multiple slices with one leader? Structure of arrays basically.

First thing coming to mind is something like

let slice_a;
let slice_b;

slice_a.manual_sort_unstable(|slice, i, j| {
    mem::swap(&mut slice[i], &mut slice[j]);
    mem::swap(&mut slice_b[i], &mut slice_b[j]);
});
1 Like
9

I would love something like that too. I end up with some variations of parallel arrays / structure-of-arrays quite often.

That's technically quite close to sort_by_cached_key, but I almost never end up using actual sort_by_cached_key, because typically I have to build all the keys first using some elaborate process that can't make keys on demand, so I have to make my own "cached_key" storage, but still need the "sort" part.

I'm not sure if |slice, i, j| could optimize out bounds checks. I've tried to make LLVM remove bounds checks in select_nth_unstable and found that length checks fail to propagate across non-trivial conditions. But something that takes a slice of keys and a slice of values to sort, performs a one-time length check, and then swaps with unsafe indexing under the hood if necessary, would be fine for me.

[values].sort_by_keys(&mut [keys])
// or
[keys].sort_values(&mut [values])

The latter could work with multiple homogeneous parallel arrays via [keys].sort_values(&mut [[values]; N]). With some hypothetical variadic generics, or enough macro hacks, maybe it could support multiple different parallel arrays [keys].sort_values((&mut [T], &mut [U])).

10

It seems to be the issue with short-circuiting OR, as it creates too many bloat for optimizer. But there, I believe, llvm should be able to remove bounds checks for slice. But yeah, I don't know if assert of equal length for each array before the sort would still hold inside the closure.

Could you elaborate a little bit more on this api? I can't quite grasp what is it. And do I understand correctly, that it will require allocation at the end?

11

I imagine that keys.sort_values(&mut values) would be:

keys.manual_sort_unstable(|keys, i, j| {
    mem::swap(&mut keys[i], &mut keys[j]);
    mem::swap(&mut values[i], &mut values[j]);
});

and then because the swap would be part of the std function instead of a custom closure, std can know that the slices won't change during sorting, so bounds checks can be skipped, like so:

keys.manual_sort_unstable(|keys, i, j| unsafe {
    keys.swap_unchecked(i, j);
    values.swap_unchecked(i, j);
});
12

Would be great to somehow have it safe though :sweat_smile:

13

Hmm, since we have the "apply a permutation" code, maybe it would be reasonable to start with an unsafe method exposing that? They you could always make your own permutation however you need to without also needing to apply it yourself.

I don't know a great (non-allocating) way to check that something is a permutation, though, for a safe API...

14

An array of integers of length N defines a permutation if and only if each of the integers 0..N appears in the array exactly once. It's obviously easy to check for integers outside the valid range. The pigeonhole principle says that if all the array entries are in the range, and there are no missing values, then there cannot be any duplicates either. I feel like there ought to be a way to detect missing values (or, equivalently, duplicates) in O(1) space but I can't think of one off the top of my head ... can we use the sum and/or product of the values somehow?

15

The O(N2) way is what get_disjoint_mut does, comparing every index against duplicates (and in range), which as you say is also a permutation if N == len(). But of course the assumption in that case is that N is usually small.

16

This MathOverflow answer seems to indicate that we do not yet have any deterministic algorithm which checks for duplicates in O(n) time and O(1) space (though we don't seem to have proven it impossible yet).

2 Likes
17

One option could be to guarantee a panic on too large of an index or the wrong size permutation slice and state that duplicates (or, equivalently, missing values) can either cause a panic or any arbitrary permutation (or an even looser value guarantee if that is helpful for the algorithm) (but not undefined behavior), similar to what [T]::sort and similar methods guarantee.

1 Like
18

If you can stomach requiring mutable access to the permutation, you could use the slice itself for the necessary memory. For &mut [usize] to be a valid permutation, each element must have a zero MSB. Using those as an N-element bitset, you could check the permutation in O(N) time and no additional space.

2 Likes
19

I did think of that, but I suspect the T-libs folks won't want the stdlib doing that.

But: this is an expensive check no matter what -- intrinsically has to scan the whole array -- and you might want to use the same permutation multiple times, so maybe a wrapper class something like

struct Permutation<N: usize>([usize; N]);

impl Permutation {
    /// Checks that `indices` define a permutation
    fn from_indices(indices: [usize; N])
        -> Result<Self, NotAPermutationError>;

    /// Uses self to permute the first N elements of `s`
    /// it is an error if s.len() < N
    fn permute<T: Sized>(&self, s: &mut [T]) -> Result<(), TooSmallError>;
}

(API sketch only, type annotations for illustration only and may be bogus)

20

Maybe if we can somehow type erase other slices and pass their reborrows as an array into sort, it may run assume_unchecked before calling the closure and pass the reborrow to the closure too?

Type erasure is to be able to place them into one array, while still allowing swaps.