Efficient way to apply monotonous rank transformation to an array

General Usage Performance
1

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?

2

Check out sortperm for obtaining just the sorting permutation.

3 Likes
3

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

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 Ints. 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
5

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

1 Like