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

General Usage
,
1

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?

Thanks!

1 Like
2

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

3

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

4

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

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

1 Like
5

@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.

EDIT:
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)
3 Likes
6

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:
https://docs.julialang.org/en/v1/manual/performance-tips/#Copying-data-is-not-always-bad

7

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

8

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