python，从(1，n)中选择随机#k个数字，不包括列表中的数字 [英] python, select random #k numbers from (1, n) excluding numbers in list

问题描述

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

For a given exclude_list = [3, 5, 8], n = 30, k = 5

我想从 1 到 30 之间选择 5(k) 个随机数.但我不应该在 exclude_list 中选择数字

I'd like to pick 5(k) random numbers between 1 and 30. But I should not pick numbers in the exclude_list

假设 exclude_list，n 可能很大.

Suppose exclude_list, n could be potentially large.

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

When there's no need for exclusion, it is easy to get k random samples

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

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

So to get the answer, I could do

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

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

I read that range keeps one number in memory at a time. I'm not quite sure how it affects the two lines above.

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

The first question is, does the following code puts all n numbers in memory or does it put each number at a time?

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

第二个问题是，如果上面的代码确实一次在内存中放入一个数字，我可以用排除列表的附加约束来做类似的事情吗?

2nd question is, if the above code indeed puts one number at a time in memory, can I do the similar with the additional constraint of the exclusion list?

推荐答案

sample 的文档字符串:

Sample notes in sample's docstring:

要在整数范围内选择样本，请使用 range 作为参数.这对于从一个大人口:样本(范围(10000000)，60)

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)

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

I can test this on my machine:

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 模块:

---

One way to sample with an exclude list efficiently is to use the same range trick but "hop over" the exclusions (we can do this in O(k * log(len(exclude_list))) with the 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]

我们可以看到它在工作:

and we can see it working:

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) 内存的情况下做到了这一点:

Specifically we've done this without using O(n) memory:

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

这篇关于python，从(1，n)中选择随机#k个数字，不包括列表中的数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！