Use of `Perm` to find sorted subset of indices?

I want to use sortperm on only a subset of indices of an array a, I couldn’t find how to do it with the sortperm function, I can simply use sort on the subset of indices s_subs this way:
sort(s_subs, by = x -> a[x])
It seems however that using a function that refers to an external array (here a) seems to be quite slow.

By looking a bit in the code of the sorting functions in Base, I understood that the non-exported Perm ordering possibly does what I want faster:
sort(s_subs, order = Perm(Forward, a))

Since Perm is not exported, I am cautious about its use. Are there any caveats about using it this way (I already noticed that bounds aren’t checked), or is there a better way to do what I want?


1 Like

I may have misunderstood, but would sortperm(a[s_subs]) work for you?

This gives indices ranging from 1 to length(s_subs), while I want the indices in s_subs to be sorted, s_subs can be any subset of indices ranging from 1 to length(a).

I see. What about s_subs[sortperm(a[s_subs])]?

Hopefully someone else chimes in with a cleaner and faster solution.

1 Like

@Adriel, your solution looks good but it seems slower than the two OP solutions, of which the first one seems faster for integer arrays and the second for float arrays.

For some large number of subindices and/or large vectors, your function actually seems to be faster. For example:

n = 100_000
a = rand(n)
s_subs = rand(1:n, 5_000)

Could that be because @Adriel’s solution does the sorting by operating on a smaller array (the copy a[s_subs]) and not the whole array a directly?

I am referring to this:

Recently stumbled upon partialsortperm. Is this what you are looking for?

I think that partialsortperm takes a range containing the “order” and gives the indices corresponding to that order.

From the example of the documentation: partialsortperm(v, 1:3) would give the indices of the 3 smallest elements of v. I somehow want the opposite, I want to give the indices and have them returned in order.

1 Like