python，从(1，n)中随机选择#k个数字，不包括列表中的数字

Question

对于给定的 except_list = [3, 5, 8], n = 30, k = 5

我想选择 1 到 30 之间的 5(k) 个随机数。 但我不应该在排除列表中选择数字

假设 except_list，n 可能很大。

当不需要排除时，很容易得到k个随机样本

rand_numbers = sample(range(1, n), k)

为了得到答案，我可以这样做

sample(set(range(1, n)) - set(exclude_numbers), k)

我读到范围一次在内存中保存一个数字。 我不太确定它如何影响上面的两行。

第一个问题是，下面的代码是将所有n个数字放入内存中还是一次将每个数字放入内存中？

rand_numbers = sample(range(1, n), k)

第二个问题是，如果上面的代码确实一次在内存中放入一个数字，我可以通过排除列表的附加约束来执行类似的操作吗？

Answer 1

sample's docstring中的示例注释:

To choose a sample in a range of integers, use range as an argument. This is especially fast and space efficient for sampling from a large population: sample(range(10000000), 60)

我可以在我的机器上测试这个:

In [11]: sample(range(100000000), 3)
Out[11]: [70147105, 27647494, 41615897]

In [12]: list(range(100000000))  # crash/takes a long time

---

有效地使用排除列表进行采样的一种方法是使用相同的范围技巧，但“跳过”排除项(我们可以在 O(k * log(len(exclude_list)) 中完成此操作) )与 bisect module :

import bisect
import random

def sample_excluding(n, k, excluding):
    # if we assume excluding is unique and sorted we can avoid the set usage...
    skips = [j - i for i, j in enumerate(sorted(set(excluding)))]
    s = random.sample(range(n - len(skips)), k)
    return [i + bisect.bisect_right(skips, i) for i in s]

我们可以看到它正在工作:

In [21]: sample_excluding(10, 3, [2, 4, 7])
Out[21]: [6, 3, 9]

In [22]: sample_excluding(10, 3, [1, 2, 8])
Out[22]: [0, 4, 3]

In [23]: sample_excluding(10, 6, [1, 2, 8])
Out[23]: [0, 7, 9, 6, 3, 5]

具体来说，我们在不使用 O(n) 内存的情况下完成了此操作:

In [24]: sample_excluding(10000000, 6, [1, 2, 8])
Out[24]: [1495143, 270716, 9490477, 2570599, 8450517, 8283229]