In-place inverse permutation

General Usage Performance
,
1

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

2

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