# In-place inverse permutation

Is there a reason that there is not an in-place equivalent of `sortperm!`, i.e., “`invperm!`”?

One current (v1.8.3) approach would be to call `invpermute!(v, sig)` for permutation `sig`, but the docs say that for `v` with many elements, `v[sig]` is faster than `permute!(v,sig)` so I would think that the same is true for `v[siginv]` versus `invpermute!(v, sig)`.

Is there a reasonably efficient in-place algorithm for this? I doubt it…

The fastest is to do `u[p] = v` with a pre-allocated output array `u`. Then you don’t need the inverse permutation `pinv = invperm(p)` at all. For example:

``````julia> using BenchmarkTools, Random

julia> p = randperm(100); v = rand(100); u = similar(v); pinv = invperm(p);

julia> @btime \$v[\$pinv];
90.787 ns (1 allocation: 896 bytes)

julia> @btime permute!(\$v, \$pinv);
283.500 ns (1 allocation: 896 bytes)

julia> @btime \$u .= @view \$v[\$pinv];
70.441 ns (0 allocations: 0 bytes)

julia> @btime \$u[:] = @view \$v[\$pinv];
103.679 ns (0 allocations: 0 bytes)

julia> @btime invpermute!(\$v, \$p);
311.929 ns (1 allocation: 896 bytes)

julia> @btime \$u[\$p] = \$v;
48.583 ns (0 allocations: 0 bytes)
``````

So, `u[p] = v` is by far the fastest way to perform an inverse permutation, not even counting the time it would take to compute `pinv = invperm(p)` (about 94ns on my machine).

Note that even the “in-place” functions `permute!` and `invpermute!` need to do some allocation internally (the former to keep track of which elements have already been permuted, the latter to simply run `v[p] = v` with a copy). Efficient in-place permutation is hard! It’s hard even when the permutation has a simple mathematical formula!

I submitted a documentation patch to clarify this: permute! and invpermute! - explain fully in-place alternatives by stevengj · Pull Request #48609 · JuliaLang/julia · GitHub

2 Likes