to compute the permutation vector. I managed to make the code allocation-free in this way,
but I wonder if there is a faster code out there. I did find SortingLab.jl , and SortingAlgorithms. Neither of these would work without major changes, unfortunately. Either the code hasn’t been touched in years and doesn’t run anymore, or the permutation vector is not provided.
sortperm!(ix, v; alg::Algorithm=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward, initialized::Bool=false)
Like sortperm, but accepts a preallocated index vector ix.
If initialized is false (the default), ix is initialized to
contain the values 1:length(v).
julia> v = [3, 1, 2]; p = zeros(Int, 3);
julia> sortperm!(p, v); p
sortperm! allocates for me too (annoying constant 16 bytes), but it has been changed in more recent versions, so maybe we are both not up to date. Latest version allows passing a scratch space, which would specifically allow non-allocating even with algos needing a little memory.
So, if you manage to test newer version, I’ll be glad to hear sortperm! is the way to go, since semantically it should be.
const v = rand(100_000);
const p = zeros(Int, 100_000);
@btime sortperm!($p, $v);
# @show p
@btime begin $p .= 1:length($v); sort!($p, Base.Sort.DEFAULT_UNSTABLE, Base.Order.Perm(Base.Order.Forward, $v)); end
# @show p
4.945 ms (2 allocations: 781.30 KiB)
4.924 ms (2 allocations: 781.30 KiB)
and with 1.8.5
6.796 ms (1 allocation: 16 bytes)
6.796 ms (0 allocations: 0 bytes)