模拟从袋子里拉出大理石而不需要更换(高效)

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

此实现非常易读,并且可以清楚地跟踪问题的设置.但是,它必须创建一个大小人口列表,这似乎是瓶颈.

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)