Shuffle values and sample indices of a sparse matrix

General Usage Performance
, ,
10

I’m thinking of something much simpler. When you are sampling from a range (or any array with unique elements), and the fraction of samples is small, you can just sample uniformly and check that the samples are unique; the probability of a collision is quite low so you will only need to re-sample a few times.

function seqsample_trivial!(rng::AbstractRNG, a::AbstractRange, x::AbstractArray)
    n, k = length(a), length(x)
    k <= n || error("length(x) should not exceed length(a)")
    while true
        for i in 1:k; x[i] = rand(a); end
        sort!(x)
        allunique = true
        for i = 2:k
            if x[i] == x[i-1]
                allunique = false
                continue
            end
        end
        allunique && return x
    end
end

(You can save the final shuffle! call in your code if you are willing to pass in a buffer array, or if you don’t care about the order. In your case, since you are calling this repeatedly, and only for lengths ≤ some threshold, I would just pass a preallocated buffer array and use it to cache the non-sorted values.)

1 Like