# Efficient way to apply monotonous rank transformation to an array

**URL:** <https://discourse.julialang.org/t/efficient-way-to-apply-monotonous-rank-transformation-to-an-array/37689>\
**Category:** Performance\
**Created:** [April 16, 2020, 10:05am UTC](https://discourse.julialang.org/t/efficient-way-to-apply-monotonous-rank-transformation-to-an-array/37689 "2020-04-16T10:05:39Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![francesco.alemanno](https://avatars.discourse-cdn.com/v4/letter/f/e8c25b/32.png) [@francesco.alemanno](https://discourse.julialang.org/u/francesco.alemanno)\
**Post date:** [April 16, 2020, 10:05am UTC](https://discourse.julialang.org/t/efficient-way-to-apply-monotonous-rank-transformation-to-an-array/37689/1 "2020-04-16T10:05:39Z")

</div>

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

```julia
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

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

```

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

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [April 16, 2020, 10:13am UTC](https://discourse.julialang.org/t/efficient-way-to-apply-monotonous-rank-transformation-to-an-array/37689/2 "2020-04-16T10:13:52Z")

</div>

Check out `sortperm` for obtaining just the sorting permutation.

---

<div class="post-metadata">

**Author:** ![francesco.alemanno](https://avatars.discourse-cdn.com/v4/letter/f/e8c25b/32.png) [@francesco.alemanno](https://discourse.julialang.org/u/francesco.alemanno)\
**Post date:** [April 16, 2020, 10:42am UTC](https://discourse.julialang.org/t/efficient-way-to-apply-monotonous-rank-transformation-to-an-array/37689/3 "2020-04-16T10:42:17Z")

</div>

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

```julia
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)

```

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [April 16, 2020, 10:58am UTC](https://discourse.julialang.org/t/efficient-way-to-apply-monotonous-rank-transformation-to-an-array/37689/4 "2020-04-16T10:58:46Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![francesco.alemanno](https://avatars.discourse-cdn.com/v4/letter/f/e8c25b/32.png) [@francesco.alemanno](https://discourse.julialang.org/u/francesco.alemanno)\
**Post date:** [April 16, 2020, 1:51pm UTC](https://discourse.julialang.org/t/efficient-way-to-apply-monotonous-rank-transformation-to-an-array/37689/5 "2020-04-16T13:51:02Z")

</div>

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