Draw two distinct random integers from `1:n`

General Usage Performance
, ,
21

Note that this solution is broken for n>2^32

2 Likes
22

No, not if you call rand properly, explicitly providing the rng. As mentioned.

23

For me it is not even faster with default global rng, running 1.7 though so maybe that is the difference from Xoshiro?

julia> function iter(n,draw)
           for i in 1:1000
               draw(n)
           end
           nothing
       end
iter (generic function with 1 method)

julia> function draw1(n)
       a = rand(1:n)
       b = rand(1:n-1)
       b += (a <= b)
       return a,b
       end
draw1 (generic function with 1 method)

julia> @btime iter(3,$draw1)
  8.139 Ξs (0 allocations: 0 bytes)

julia> function draw5(n)
           ind = rand(0:(n * (n - 1) - 1))
           a, b = divrem(ind, n)
           a += (a >= b)
           return a + 1, b + 1
       end
draw5 (generic function with 1 method)

julia> @btime iter(3,$draw5)
  10.833 Ξs (0 allocations: 0 bytes)
24

Yes, here (1.6) with MersenneTwister the difference is of about 5% in favor of the two-rand calls. Passing the rng is sometimes cumbersome, so good there is a reasonable alternative :slight_smile: .

25

Probably not faster than the other solutions, but here is my take:

function draw(n)
    a = rand(0:n-1)
    b = mod(rand(0:n-2) + a + 1, n)
    a+1, b+1
end

julia> histogram(reinterpret(Int,[draw(3) for i = 1:100000]), nbins=3)
              ┌                                        ┐
   [1.0, 2.0) â”Ī████████████████████████████████▊ 66585
   [2.0, 3.0) â”Ī████████████████████████████████▊ 66562
   [3.0, 4.0) â”Ī█████████████████████████████████  66853
              └                                        ┘
                               Frequency
1 Like