パイソン、からランダム#K番号を選択し（1、n）が与えられたexclude_list =ためのリスト

Question

の数字を除い[3,5]、[8]、N = 30、K = 5

5（k）1から30までの乱数。 しかし除外リストで数字を選んではいけません。

nが潜在的に大きい可能性があるとします。

除外のための必要はありません、私が、その範囲は1つの番号でを保つ読ん

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

行うことができ、答えを得るために無作為標本ので

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

をk個取得することは簡単です一度にメモリ。 私はそれが上記の2行にどのように影響するかについてはあまりよく分かりません。

最初の質問は、次のコードはすべてのn個の数値をメモリに入れますか、またはそれぞれの数値を一度に入れるのですか？

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

第二の問題は、上記のコードは、実際にメモリに一度に一つの番号を置く場合、私は、除外リストの追加の制約と同様の操作を行うことができますか？ sample's docstringで

Answer 1

サンプル・ノート：

引数として範囲を使用し、整数の範囲内のサンプルを選択します。 これは特に高速でスペース効率のよい 大きな母集団からのサンプリングのためである：サンプル（レンジ（10000000）、60）

私は私のマシン上でこれをテストすることができます。

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

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

---

ワン排除リストを使って効率的にサンプリングする方法は、同じ範囲のトリックを使用して除外を「ホップオーバー」することです（bisect module：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] 

具体的に我々は（n）はOを使用せずにメモリにこれをやった：

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