hi guys, i wonder if any of you know of a more efficient way to rank an array

currently i am using

```
A=[45, 4, 7, 10, 25, 36, 36, 22, 31, 16] # input vector
S=invperm(sort(1:length(A),by=i->A[i]))
f(x)=x^2
B=1:length(A)
T=f.(B[S]) #output vector
```

this correctly produces

```
T = [100, 1, 4, 9, 36, 64, 81, 25, 49, 16]
```

this to me looks wildly inefficient, is there a better way?

Check out `sortperm`

for obtaining just the sorting permutation.

3 Likes

hey Tamas, thank you, ~~but apparently it doesnt do much~~ it works!

```
function rank_vector(A::AbstractVector)
invperm(sortperm(A))
end
rank_vector(f,A::AbstractVector) = f.(rank_vector(A))
function rank_vector2(A::AbstractVector)
invperm(sort(1:length(A),by=i->A[i]))
end
rank_vector2(f,A::AbstractVector) = f.(rank_vector2(A))
using BenchmarkTools
f(x)=x*x
A=rand(1:50,1000)
@btime rank_vector2($f,$A)
@btime rank_vector($f,$A)
A=rand(1000)
@btime rank_vector2($f,$A)
@btime rank_vector($f,$A)
julia>
9.799 μs (7 allocations: 23.88 KiB)
3.600 μs (6 allocations: 24.33 KiB)
27.600 μs (7 allocations: 23.88 KiB)
12.900 μs (8 allocations: 23.89 KiB)
```

I imagine that the sorting/inversion will dominate in any case, so I am not sure it is possible to make this more efficient for general `A`

.

Note however that in your integer benchmarks you have a lot of repetition for `Int`

s. Depending on whether this is a feature of your data and your need for a stable sort, you may be able to come up with a faster specialized algorithm (I assume your data is large, which is why you want to make this efficient).

1 Like

Sorry man, i had a typo in my code, your suggestion actually works!

1 Like