# Efficient way to apply monotonous rank transformation to an array

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