我需要对一组记录发出多少个随机请求才能获得 80% 的记录

Question

假设我有一个 100_000 条记录的数组(这是 Ruby 代码，但任何语言都可以(

ary = ['apple','orange','dog','tomato', 12, 17,'cat','tiger' .... ]
results = []

我

只能随机调用数组(我不能以任何方式遍历它(

results << ary.sample 
# in ruby this will pull a random record from the array, and 
# push into results array

我需要进行多少次这样的随机调用，才能从ary获得至少 80% 的记录。或者以另一种方式表达 - results的大小应该是多少，以便results.uniq将包含来自ary的大约 80_000 条记录。

根据我对大学统计课的生疏记忆，我认为它需要 2*结果集大小 = 或大约 160_000 个请求(假设随机函数是随机的，并且没有其他一些潜在问题(。 我的测试似乎证实了这一点。

ary = [*1..100_000];
result = [];  
160_000.times{result << ary.sample}; 
result.uniq.size # ~ 80k

这是统计数据，所以我们谈论的是概率，而不是保证的结果。我只需要一个合理的猜测。

所以问题真的是，确认这一点的公式是什么？

Answer 1

我只想做一个快速的模拟研究。在 R 中，

N = 1e5
# Simulate 300 times
s = replicate(300, sample(x = 1:N, size = 1.7e5, replace = TRUE))

现在计算出何时达到目标

f = function(i) which(i == unique(i)[80000])[1]
stats = apply(s, 2, f)

要得到

summary(stats)
# Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
# 159711  160726  161032  161037  161399  162242 

因此，在 300 次试验中，所需的最大模拟次数是162242平均161032数。

Answer 2

使用费舍尔-耶茨洗牌，您可以从正好 80K 的随机调用中获得 80K 个项目

对 Ruby 一无所知，但查看 https://gist.github.com/mindplace/3f3a08299651ebf4ab91de3d83254fbc 并对其进行修改

def shuffle(array, counter)
  #counter = array.length - 1
  while counter > 0
    # item selected from the unshuffled part of array
    random_index = rand(counter)
    # swap the items at those locations
    array[counter], array[random_index] = array[random_index], array[counter]
    # de-increment counter
    counter -= 1
  end
  array
end
indices = [0, 1, 2, 3, ...] # up to 99999
counter = 80000
shuffle(indices, 80000)
i = 0
while counter > 0
  res[i] = ary[indices[i]]
  counter -= 1
  i += 1

更新

将采样索引打包到自定义 RNG 中(请耐心等待，对 Ruby 一无所知(

class FYRandom
  _indices = indices
  _max     = 80000
  _idx     = 0
  def rand()
    if _idx > _max
      return -1.0
    r = _indices[idx]
    _idx += 1
    return r.to_f / max.to_f
  end
end

示例的代码将是

rng = FYRandom.new
results << ary.sample(random: rng)