Python：模拟掷骰子，直到所有值都出现至少一次

Question

我想从列表中抽样，直到所有元素至少出现一次。我们可以以掷骰子为例。一个骰子有六个面：1 到 6。我不断地掷它，直到我至少看到所有六个值一次，然后我停下来。这是我的功能。

import numpy as np

def sample_until_all(all_values):
    sampled_vals = np.empty(0)
    while True:
        cur_val = np.random.choice(all_values, 1)
        sampled_vals = np.append(sampled_vals, cur_val[0])        
        if set(all_values) == set(sampled_vals):
            return(len(sampled_vals))
        
sample_until_all(range(6))

cur_val 是当前投掷的值。我使用 np.append 将所有采样值保存在 sampled_vals 中，并使用 set(all_values) == set(sampled_vals) 检查每次投掷后它是否包含所有可能的值。它有效但效率不高（我相信）。任何想法如何让它更快？谢谢。

我只是用这个作为玩具示例。我需要的实际列表远不止 6 个值。

Answer 1

我不认为 numpy 在这里真的有用，因为你一个一个地生成你的值。

使用计数器怎么样？

from collections import Counter
import random

def sample_until_all(all_values):
    all_values = list(all_values)
    c = Counter()
    while len(c)<len(all_values):
        c[random.choice(all_values)] +=1
    return sum(c.values())


sample_until_all(range(6))

这段代码比range(6)快了50倍左右，范围越大差异就越大

Answer 2

下面创建一个集合a，它将是all_values中唯一对象的集合。这个集合将代表我们还没有看到的元素。由于我们从 all_values 中随机选择元素，如果它是我们以前没有见过的，那么我们从集合中删除相应的对象。我们继续这样做，直到集合 a 为空。

from random import choice

def sample_until_all(all_values):
    a = set(all_values)
    count = 0

    while a:
        r = choice(all_values) 
        print(r)
        count += 1
        if r in a:
            a.remove(r)

    print(f"\nIt took {count} draws.")
    return count

示例会话（调用sample_until_all(range(6))）

1
5
1
3
5
2
4
0

It took 8 draws.

计时

通过 perfplot.show()、setup = lambda n: range(n) 和 n_range = [2**k for k in range(11)] 获得。在进行计时之前，我从我的函数中删除了 print 语句。

Answer 3

这是另一种不依赖于构建和修改列表的方法（除了最初从指定范围获取列表）：

import random

def sample_until_all(all_values):
    vlist = list(all_values) # list of values to choose from
    target = sum(vlist) # target sum
    seen = set() # values seen so far
    total = 0 # running total
    while total != target:
        choice = random.choice(vlist)
        if not choice in seen:
            seen.add(choice)
            total += choice

sample_until_all(range(6))

Answer 4

Numpy 数组在具有确定大小时工作得很好，但如果不是这种情况则效果不佳。

您程序的核心部分是检查 sampled_vals 中元素的存在，这是 dicts excel 的任务。然而，在每个循环中将数组转换为字典的代价是不必要的。因此，我们可以这样简化您的代码：

from random import choice

def new_sample_until_all(all_values):
    sampled_vals = set()
    universe_set = set(all_values)
    n = 0
    while sampled_vals != universe_set:
        cur_val = choice(all_values)
        sampled_vals.add(cur_val)
        n += 1
    return n

其主要改进是

将 sampled_vals 保持为一个集合，而不是每次都必须转换的 variable-length numpy 数组。
使用一个简单的 n 计数器来跟踪您必须从 all_values 采样的次数。

在我的机器上进行的简单测试中，我得到 values = list(range(10**3)):

%timeit sample_until_all(values)
>>> 2.6 s ± 1.22 s

%timeit new_sample_until_all(values)
>>> 2.37 ms ± 11.8 µs

这意味着新代码大约快 1000 倍。不错！

Python：模拟掷骰子，直到所有值都出现至少一次

Python: simulate tossing a die until all values have appeared at least once

python

random