python - 模拟从袋子中取出弹珠而不更换(有效)

Question

我需要在 python 中模拟超几何分布(用于不替换采样元素的花哨词)。

设置:有一个装满人口许多弹珠的袋子。弹珠有两种类型，红色和绿色(在以下实现中，弹珠表示为 True 和 False)。从袋子中拉出的弹珠数量是样本。

以下是我针对该问题提出的两种实现方式，但是它们都在人口 > 10^8 时速度开始下降

def pull_marbles(sample, population=100):
    assert population % 2 == 0
    marbles = [x < population / 2 for x in range(0,population)]
    chosen = []
    for i in range(0,sample):
        choice = random.randint(0, population - i - 1)
        chosen.append(marbles[choice])
        del marbles[choice]
    return marbles

这个实现非常可读，并且清楚地遵循了问题的设置。但是，它必须创建一个大小为 population 的列表，这似乎是瓶颈。

def pull_marbles2(sample, population=100):
    assert population % 2 == 0
    return random.sample([x < population / 2 for x in range(0, population)], sample)

此实现使用 random.sample 函数希望加快速度。不幸的是，它没有解决生成长度人口列表的潜在瓶颈。

编辑:错误地，第一个代码示例返回弹珠，这使得这个问题变得模棱两可。所以毫不含糊地，我希望代码返回“拉出”的红色弹珠和绿色弹珠的数量。很抱歉造成混淆 - 我会保留 pull_marbles 的原始错误版本，但不会使现有答案看起来无效。

Answer 1

不用列表来表示您的包，只需使用两个整数来计算红色和绿色弹珠。每次拉动都是通过检查 (0..red+green) 范围内的随机数是否小于 red 来完成的。如果是，则拉红色，因此减少 red，否则拉绿色，因此减少 green。

这样您将不得不迭代地完成所有拉动，但我想这应该不是问题。 但是可能有一些我现在想不到的优化方法来提取大量数字而不必反复执行此操作。

def pull_marbles(sample, population=100):
  red = population / 2
  green = (population+1) / 2  # round up just to ensure red+green == population
  for i in range(sample):
    choice = random.randint(1, red + green)
    if choice <= red:  # red pulled
      red -= 1
    else:
      green -= 1
  return (red, green)