朱莉娅：从不断缩小的范围中抽样的最佳方式？

Question

我想对 k 个数字进行采样，其中第一个数字是从 1:n 中采样的，第二个是从 1:n-1 中采样的，第三个是从 1:n-2 中采样的，依此类推。

我有以下实现

function shrinksample(n,k)
    [rand(1:m) for m in n:-1:n-k+1]
end

Julia 中有更快的解决方案吗？

Answer 1

以下内容取自 randperm 的实现思路，并且由于 n 和 k 的顺序相同，因此这是合适的，因为需要相同类型的随机性（两者输出 space 大小 n 阶乘）：

function fastshrinksample(r::AbstractRNG,n,k)
    a = Vector{typeof(n)}(k)
    @assert n <= Int64(2)^52
    k == 0 && return a
    mask = (1<<(64-leading_zeros(n)))-1
    nextmask = mask>>1
    nn = n
    for i=1:k
        a[i] = 1+Base.Random.rand_lt(r, nn, mask)
        nn -= 1
        if nn == nextmask
            mask, nextmask = nextmask, nextmask>>1
        end
    end
    return a
end

fastshrinksample(n,k) = fastshrinksample(Base.Random.GLOBAL_RNG, n, k)

基准测试使一个测试实例提高了 3 倍：

julia> using BenchmarkTools

julia> @btime shrinksample(10000,10000);
  310.277 μs (2 allocations: 78.20 KiB)

julia> @btime fastshrinksample(10000,10000);
  91.815 μs (2 allocations: 78.20 KiB)

技巧主要是使用内部的Base.Random.rand_lt而不是常规的rand(1:n)

Answer 2

如果这对随机性不是很敏感（你不是在做密码学），下面的代码应该非常快而且非常简单：

blazingshrinksample(n,k) = (Int)[trunc(Int,(n-m)rand()+1) for m in 0:k-1]

通过你的实现和 Dan 的实现测试这个，我得到了这个：

using BenchmarkTools

@btime shrinksample(10000,10000);
  259.414 μs (2 allocations: 78.20 KiB)

@btime fastshrinksample(10000,10000);
  66.713 μs (2 allocations: 78.20 KiB)

@btime blazingshrinksample(10000,10000);
  33.614 μs (2 allocations: 78.20 KiB)

朱莉娅：从不断缩小的范围中抽样的最佳方式？

Julia: best way to sample from successively shrinking range?

random

julia

sample

sampling