add invpermute

[LilithHafner]

An optimized version of v[invperm(p)].

(also stop exporting inv because it is already exported by Base)

julia> @benchmark invpermute(v, p) setup=(v=rand(3000); p=shuffle(1:3000))
BenchmarkTools.Trial: 10000 samples with 7 evaluations.
 Range (min … max):   3.923 μs … 937.430 μs  ┊ GC (min … max):  0.00% … 98.58%
 Time  (median):      5.611 μs               ┊ GC (median):     0.00%
 Time  (mean ± σ):   10.569 μs ±  50.582 μs  ┊ GC (mean ± σ):  31.72% ±  6.60%

        █▂                                                      
  ▂▆▃▁▂███▃▃▃▃▂▂▂▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▂▂▂▂▂▂▂▂▂▂▂▂▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁ ▂
  3.92 μs         Histogram: frequency by time         18.1 μs <

 Memory estimate: 23.48 KiB, allocs estimate: 2.

julia> @benchmark v[invperm(p)] setup=(v=rand(3000); p=shuffle(1:3000))
BenchmarkTools.Trial: 10000 samples with 3 evaluations.
 Range (min … max):   7.271 μs …   2.739 ms  ┊ GC (min … max):  0.00% … 98.90%
 Time  (median):     10.706 μs               ┊ GC (median):     0.00%
 Time  (mean ± σ):   20.674 μs ± 104.696 μs  ┊ GC (mean ± σ):  27.27% ±  5.41%

From https://github.com/JuliaLang/julia/pull/44941#discussion_r847620024

[codecov[bot]]

Codecov Report

Merging #29 (d5d6e0c) into master (fe39ac9) will increase coverage by 0.88%. The diff coverage is 100.00%.

@@            Coverage Diff             @@
##           master      #29      +/-   ##
==========================================
+ Coverage   83.19%   84.08%   +0.88%     
==========================================
  Files           5        5              
  Lines         482      490       +8     
==========================================
+ Hits          401      412      +11     
+ Misses         81       78       -3     

Impacted Files	Coverage Δ
src/Permutations.jl	81.00% <100.00%> (+0.60%)	:arrow_up:
src/CompiledPermutation.jl	91.05% <0.00%> (+0.81%)	:arrow_up:
src/sqrt.jl	93.33% <0.00%> (+3.33%)	:arrow_up:

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update fe39ac9...d5d6e0c. Read the comment docs.

[scheinerman]

@LilithHafner : I think this is ok, but will inv(p) still work? I really don't understand why you would want to have a separate named function for this. Can you enlighten me?

[LilithHafner]

Sorry, I put two different things in this PR that aren't really connected.

1) Yes, inv will still work. When we import the function Base.inv and then define a new method for it, that method will be attached to the function no matter where it is used. In a sense, we are mutating the function by adding a method, but Permutations.inv is still the same function as Base.inv, which everyone already has because Base exports it. We can see that the functions are the same by running Base.inv === Permutations.inv. We can also check that it still works with a test. I'll add a test that inv works.

2) Primarily, for performance. If someone wants to compute the inverse permutation applied to a vector, it is almost twice as fast to combine the two operations than to do them separately because there is no need to invert a permutation to apply its inverse. As a package maintainer, it is up to you to make a judgment call as to whether that is within the scope of this package and worth the cost of an additional exported method. If someone is applying inverse permutations in a performance-sensitive piece of code, this is nice to have, or if someone is using this particular operation a whole lot and wants a name for it. Otherwise, it's just a little more noise in the namespace. I personally think it is appropriate to include efficient implementations of obscure permutation operations in Permutations.jl, but it's up to you to make that decision.

[scheinerman]

@LilithHafner : Thanks for the explanation! I merged and will register this as a new version.