Another way to go about it, is to look at R's implementation of a random
permutation and recreate it in Julia, hoping for similar performance.
Having done so, the resulting Julia code is:
function nrandperm(r::AbstractRNG, n::Integer)
res = Array(typeof(n),n)
if n == 0
return res
end
a = typeof(n)[i for i=1:n]
nn = n
@inbounds for i = 1:n
j = floor(Int,nn*rand(r))+1
res[i] = a[j]
a[j] = a[nn]
nn -= 1
end
return res
end
nrandperm(n::Integer) = nrandperm(Base.Random.GLOBAL_RNG, n)
A size 1,000,000 permutation was generated x2 faster with this method.
But, this method uses uniform floating random numbers, which might not be
uniform on integers for large enough numbers. In general, it should be
possible to optimize a more correct implementation. But if R envy is a
driver, R performance is recovered with a pure Julia implementation (the R
implementation is in C).
On Saturday, January 23, 2016 at 7:26:49 AM UTC+2, Rafael Fourquet wrote:
>
> > Let's capture this as a Julia performance issue on github,
> > if we can't figure out an easy way to speed this up right away.
>
> I think I remember having identified a potentially sub-optimal
> implementation of this function few weeks back (perhaps no more than
> what Tim suggested) and had planned to investigate further (when time
> permits...)
>
