Python はmy_sample = random.sample(range(100), 10)、 から置換せずにランダムにサンプリングする必要があり[0, 100)ます。
そのような数値をサンプリングした後n、置換せずに (以前にサンプリングした を含めずにn) もう 1 つサンプリングしたいとします。
更新：「合理的に効率的」から「超効率的」に変更されました（ただし、一定の要因は無視されます）
質問する
24710 次
13 に答える
23
オーバーラップのない複数のサンプルが必要であることが事前にわかっている場合、最も簡単な方法はrandom.shuffle()( list(range(100))Python 3 - Python 2 ではスキップできますlist()) で、必要に応じてスライスを剥がします。
s = list(range(100))
random.shuffle(s)
first_sample = s[-10:]
del s[-10:]
second_sample = s[-10:]
del s[-10:]
# etc
そうでなければ、@ Chronialの答えはかなり効率的です。
于 2013-09-20T16:30:27.660 に答える
10
OPからの読者への注意：ロジックを理解するために最初に受け入れられた回答を見てから、この回答を理解してください。
Aaaaaand 完全を期すために: これはnecromancer's answerの概念ですが、禁止番号のリストを入力として受け取るように調整されています。これは前の回答とまったく同じコードですが、forbid数値を生成する前にから状態を構築します。
- これは時間
O(f+k)と記憶O(f+k)です。forbid明らかに、これは(sorted/set)の形式に対する要件なしで可能な最速の方法です。これで何とか勝てると思います(^^) - がセットの場合、に非常に近く、 にあまり近くないを使用
forbidすると、繰り返し推測法が高速になります。O(k⋅n/(n-(f+k)))O(k)f+kn forbidがソートされている場合、私のばかげたアルゴリズムは次のように高速化されます。
import random
def sample_gen(n, forbid):
state = dict()
track = dict()
for (i, o) in enumerate(forbid):
x = track.get(o, o)
t = state.get(n-i-1, n-i-1)
state[x] = t
track[t] = x
state.pop(n-i-1, None)
track.pop(o, None)
del track
for remaining in xrange(n-len(forbid), 0, -1):
i = random.randrange(remaining)
yield state.get(i, i)
state[i] = state.get(remaining - 1, remaining - 1)
state.pop(remaining - 1, None)
利用方法：
gen = sample_gen(10, [1, 2, 4, 8])
print gen.next()
print gen.next()
print gen.next()
print gen.next()
于 2013-09-25T01:49:01.483 に答える
9
近道
サンプリングされた数が母集団よりもはるかに少ない場合は、サンプリングして、選択されているかどうかを確認し、選択されているかどうかを繰り返します。O(n)これはばかげているように聞こえるかもしれませんが、同じ数を選択する可能性が指数関数的に減衰するため、選択されていない割合がわずかでもある場合よりもはるかに高速です。
長い道のり
Python はその PRNG として Mersenne Twister を使用しますが、これで十分です。予測可能な方法で重複しない数値を生成できるようにするために、まったく別のものを使用できます。
二次剰余 は、とが素数の
x² mod p場合に一意です。2x < pp残基 を「反転」すると、
p - (x² % p)今回も が与えられp = 3 mod 4、結果は残りのスペースになります。これはあまり説得力のある数値スプレッドではないため、検出力を増やし、いくつかのファッジ定数を追加すると、分布はかなり良好になります。
まず、素数を生成する必要があります。
from itertools import count
from math import ceil
from random import randrange
def modprime_at_least(number):
if number <= 2:
return 2
number = (number // 4 * 4) + 3
for number in count(number, 4):
if all(number % factor for factor in range(3, ceil(number ** 0.5)+1, 2)):
return number
素数を生成するコストについて心配するかもしれません。10⁶ 要素の場合、これには 10 分の 1 ミリ秒かかります。実行[None] * 10**6にはそれよりも時間がかかりますが、計算は 1 回だけなので、これは実際の問題ではありません。
さらに、アルゴリズムは素数の正確な値を必要としません。必要なのは、入力数値よりも最大でも一定の係数だけである必要があります。これは、値のリストを保存して検索することで可能になります。線形スキャンを行う場合、つまりO(log number)、二分探索を行う場合は ですO(log number of cached primes)。実際、ギャロッピングを使用すると、これを に下げることができます。O(log log number)これは基本的に一定です ( log log googol = 2)。
次に、ジェネレーターを実装します
def sample_generator(up_to):
prime = modprime_at_least(up_to+1)
# Fudge to make it less predictable
fudge_power = 2**randrange(7, 11)
fudge_constant = randrange(prime//2, prime)
fudge_factor = randrange(prime//2, prime)
def permute(x):
permuted = pow(x, fudge_power, prime)
return permuted if 2*x <= prime else prime - permuted
for x in range(prime):
res = (permute(x) + fudge_constant) % prime
res = permute((res * fudge_factor) % prime)
if res < up_to:
yield res
そして、それが機能することを確認してください：
set(sample_generator(10000)) ^ set(range(10000))
#>>> set()
さて、これのすばらしいところは、 が要素数である優先度テストを無視するとO(√n)、nこのアルゴリズムには時間の複雑さO(k)がありk、 はサンプルサイズであり、O(1)メモリ使用量です! 技術的には ですO(√n + k)が、実際にはO(k)です。
要件：
実績のある PRNG は必要ありません。この PRNG は、線形合同法ジェネレーター (人気があり、 Java で使用されています)よりもはるかに優れていますが、Mersenne Twister ほど証明されていません。
最初に異なる機能を持つアイテムを生成しません。これにより、チェックではなく数学を通じて重複が回避されます。次のセクションでは、この制限を削除する方法を示します。
短い方法は不十分でなければなりません（
kアプローチする必要がありますn）。kが半分だけの場合はn、私の最初の提案に従ってください。
利点:
極端なメモリ節約。これには一定のメモリが必要です...そうではありません
O(k)！次のアイテムを生成する一定の時間。これは実際には一定の条件でもかなり高速です。組み込みの Mersenne Twisterほど高速ではありませんが、2 倍以内です。
涼しさ。
この要件を削除するには:
最初に異なる機能を持つアイテムを生成しません。これにより、チェックではなく数学を通じて重複が回避されます。
以前のジェネレーターの単純な拡張である、時間と空間の複雑さにおいて可能な限り最高のアルゴリズムを作成しました。
概要は次のとおりです（nは数字のプールの長さ、kは「外部」キーの数です）：
初期化時間O(√n); O(log log n)すべての妥当な入力に対して
O(√n)これは、コストのおかげで、アルゴリズムの複雑さに関して技術的に完全ではない私のアルゴリズムの唯一の要因です。実際には、これは問題にはなりません。なぜなら、事前計算O(log log n)によって定数時間に計り知れないほど近い値になるからです。
イテラブルを一定の割合で使い果たすと、コストは無料で償却されます。
これは実際的な問題ではありません。
償却されO(1)たキー生成時間
明らかに、これを改善することはできません。
最悪の場合のO(k)キー生成時間
このジェネレーターが既に生成したキーであってはならないという要件のみで、外部から生成されたキーがある場合、これらは「外部キー」と呼ばれます。外部キーは完全にランダムであると想定されます。そのため、プールからアイテムを選択できる関数はすべて選択できます。
任意の数の外部キーが存在する可能性があり、それらは完全にランダムである可能性があるため、完全なアルゴリズムの最悪のケースはO(k).
最悪の場合のスペースの複雑さO(k)
外部キーが完全に独立していると仮定すると、それぞれが別個の情報項目を表します。したがって、すべてのキーを保存する必要があります。アルゴリズムは、キーを見つけるたびにたまたまキーを破棄するため、メモリ コストはジェネレーターの存続期間中にクリアされます。
アルゴリズム
まあ、それは私のアルゴリズムの両方です。それは実際には非常に簡単です：
def sample_generator(up_to, previously_chosen=set(), *, prune=True):
prime = modprime_at_least(up_to+1)
# Fudge to make it less predictable
fudge_power = 2**randrange(7, 11)
fudge_constant = randrange(prime//2, prime)
fudge_factor = randrange(prime//2, prime)
def permute(x):
permuted = pow(x, fudge_power, prime)
return permuted if 2*x <= prime else prime - permuted
for x in range(prime):
res = (permute(x) + fudge_constant) % prime
res = permute((res * fudge_factor) % prime)
if res in previously_chosen:
if prune:
previously_chosen.remove(res)
elif res < up_to:
yield res
変更は以下を追加するだけです。
if res in previously_chosen:
previously_chosen.remove(res)
previously_chosen渡した に追加することで、いつでも に追加できsetます。実際には、潜在的なプールに追加し直すためにセットから削除することもできますが、これは がsample_generatorまだそれを生成していないかスキップした場合にのみ機能しますとprune=False。
あります。すべての要件を満たしていることは簡単にわかり、要件が絶対的であることも簡単にわかります。セットがない場合でも、入力をセットに変換することで最悪のケースに対応できますが、オーバーヘッドは増加します。
RNG の品質のテスト
統計的に言えば、この PRNG が実際にどの程度優れているのか知りたいと思いました。
ちょっとした検索でこれら 3 つのテストを作成しましたが、どれも良い結果を示しているようです!
まず、いくつかの乱数:
N = 1000000
my_gen = list(sample_generator(N))
target = list(range(N))
random.shuffle(target)
control = list(range(N))
random.shuffle(control)
0これらは からまで10⁶-1の 10⁶ の数字の「シャッフル」リストです。3つ目はコントロールです。
これは、線に沿った 2 つの乱数間の平均距離を調べるテストです。違いをコントロールと比較します。
from collections import Counter
def birthdat_calc(randoms):
return Counter(abs(r1-r2)//10000 for r1, r2 in zip(randoms, randoms[1:]))
def birthday_compare(randoms_1, randoms_2):
birthday_1 = sorted(birthdat_calc(randoms_1).items())
birthday_2 = sorted(birthdat_calc(randoms_2).items())
return sum(abs(n1 - n2) for (i1, n1), (i2, n2) in zip(birthday_1, birthday_2))
print(birthday_compare(my_gen, target), birthday_compare(control, target))
#>>> 9514 10136
これは、それぞれの分散よりも小さいです。
これは、順番に 5 つの数字を取り、要素がどのような順序であるかを確認するテストです。それらは、120 の可能な順序すべてに均等に分散する必要があります。
def permutations_calc(randoms):
permutations = Counter()
for items in zip(*[iter(randoms)]*5):
sorteditems = sorted(items)
permutations[tuple(sorteditems.index(item) for item in items)] += 1
return permutations
def permutations_compare(randoms_1, randoms_2):
permutations_1 = permutations_calc(randoms_1)
permutations_2 = permutations_calc(randoms_2)
keys = sorted(permutations_1.keys() | permutations_2.keys())
return sum(abs(permutations_1[key] - permutations_2[key]) for key in keys)
print(permutations_compare(my_gen, target), permutations_compare(control, target))
#>>> 5324 5368
これもそれぞれの分散よりも小さいです。
これは、別名「実行」の長さを確認するテストです。連続した増加または減少のセクション。
def runs_calc(randoms):
runs = Counter()
run = 0
for item in randoms:
if run == 0:
run = 1
elif run == 1:
run = 2
increasing = item > last
else:
if (item > last) == increasing:
run += 1
else:
runs[run] += 1
run = 0
last = item
return runs
def runs_compare(randoms_1, randoms_2):
runs_1 = runs_calc(randoms_1)
runs_2 = runs_calc(randoms_2)
keys = sorted(runs_1.keys() | runs_2.keys())
return sum(abs(runs_1[key] - runs_2[key]) for key in keys)
print(runs_compare(my_gen, target), runs_compare(control, target))
#>>> 1270 975
ここでの分散は非常に大きく、私が行ったいくつかの実行では、両方が均等に広がっているようです。そのため、このテストは合格です。
おそらく「より実り多い」ものとして、線形合同ジェネレーターが言及されました。これが正確な記述であるかどうかを確認するために、私自身の不完全に実装された LCG を作成しました。
AFAICT によると、LCG は通常の発電機と同じように、周期的に作成されていません。したがって、私が見たほとんどの参照、別名。ウィキペディアでは、特定の期間の強力な LCG を作成する方法ではなく、期間を定義するもののみを取り上げました。これが結果に影響した可能性があります。
ここに行きます：
from operator import mul
from functools import reduce
# Credit http://stackoverflow.com/a/16996439/1763356
# Meta: Also Tobias Kienzler seems to have credit for my
# edit to the post, what's up with that?
def factors(n):
d = 2
while d**2 <= n:
while not n % d:
yield d
n //= d
d += 1
if n > 1:
yield n
def sample_generator3(up_to):
for modulier in count(up_to):
modulier_factors = set(factors(modulier))
multiplier = reduce(mul, modulier_factors)
if not modulier % 4:
multiplier *= 2
if multiplier < modulier - 1:
multiplier += 1
break
x = randrange(0, up_to)
fudge_constant = random.randrange(0, modulier)
for modfact in modulier_factors:
while not fudge_constant % modfact:
fudge_constant //= modfact
for _ in range(modulier):
if x < up_to:
yield x
x = (x * multiplier + fudge_constant) % modulier
素数をチェックすることはもうありませんが、因数について奇妙なことをする必要があります。
modulier ≥ up_to > multiplier, fudge_constant > 0a - 1modulier...のすべての約数で割り切れる必要があります。- ...一方、互いに素で
fudge_constantなければなりませんmodulier
これらは LCG のルールではなく、明らかにmodulier に等しい全期間の LCG のルールであることに注意してください。
私はそのようにしました：
modulier少なくともごとに試行up_toし、条件が満たされたときに停止します- その要因のセットを作成し、
- 重複を削除し
multiplierての製品にする multiplierが 未満でない場合はmodulier、次に進みますmodulier- ランダムに選択され
fudge_constantた 未満の数にしますmodulier - にある要因を削除
fudge_constantします。
- その要因のセットを作成し、
fudge_constantこれはそれを生成するためのあまり良い方法ではありませんが、これらの完全な生成器よりも低いsmultiplierがより一般的であるという事実を除けば、数値の品質に影響を与える理由がわかりません。
とにかく、結果は恐ろしいものです:
print(birthday_compare(lcg, target), birthday_compare(control, target))
#>>> 22532 10650
print(permutations_compare(lcg, target), permutations_compare(control, target))
#>>> 17968 5820
print(runs_compare(lcg, target), runs_compare(control, target))
#>>> 8320 662
要約すると、私の RNG は優れていますが、線形合同ジェネレーターはそうではありません。Java が線形合同ジェネレーターを使用できることを考えると (下位ビットしか使用しませんが)、私のバージョンで十分すぎると思います。
于 2013-09-20T16:27:05.000 に答える
6
ウィキペディアの「Fisher--Yates shuffle#Modern method」に基づいて、シャッフル ジェネレーターを実装できます。
def shuffle_gen(src):
""" yields random items from base without repetition. Clobbers `src`. """
for remaining in xrange(len(src), 0, -1):
i = random.randrange(remaining)
yield src[i]
src[i] = src[remaining - 1]
次に、次を使用してスライスできますitertools.islice。
>>> import itertools
>>> sampler = shuffle_gen(range(100))
>>> sample1 = list(itertools.islice(sampler, 10))
>>> sample1
[37, 1, 51, 82, 83, 12, 31, 56, 15, 92]
>>> sample2 = list(itertools.islice(sampler, 80))
>>> sample2
[79, 66, 65, 23, 63, 14, 30, 38, 41, 3, 47, 42, 22, 11, 91, 16, 58, 20, 96, 32, 76, 55, 59, 53, 94, 88, 21, 9, 90, 75, 74, 29, 48, 28, 0, 89, 46, 70, 60, 73, 71, 72, 93, 24, 34, 26, 99, 97, 39, 17, 86, 52, 44, 40, 49, 77, 8, 61, 18, 87, 13, 78, 62, 25, 36, 7, 84, 2, 6, 81, 10, 80, 45, 57, 5, 64, 33, 95, 43, 68]
>>> sample3 = list(itertools.islice(sampler, 20))
>>> sample3
[85, 19, 54, 27, 35, 4, 98, 50, 67, 69]
于 2013-09-23T16:50:08.513 に答える
5
編集:以下の @TimPeters および @Chronial によるよりクリーンなバージョンを参照してください。マイナーな編集により、これがトップに押し上げられました。
これが、増分サンプリングの最も効率的なソリューションであると私が信じているものです。以前にサンプリングされた数値のリストの代わりに、呼び出し元によって維持される状態は、インクリメンタル サンプラーによって使用できる状態になっている辞書と、範囲内に残っている数値のカウントで構成されます。
以下はデモ用の実装です。他のソリューションとの比較:
- ループなし (標準の Python/Veedrac ハックなし。Python impl と Veedrac の間でクレジットを共有)
- 時間の複雑さは
O(log(number_previously_sampled)) - 空間の複雑さは
O(number_previously_sampled)
コード：
import random
def remove (i, n, state):
if i == n - 1:
if i in state:
t = state[i]
del state[i]
return t
else:
return i
else:
if i in state:
t = state[i]
if n - 1 in state:
state[i] = state[n - 1]
del state[n - 1]
else:
state[i] = n - 1
return t
else:
if n - 1 in state:
state[i] = state[n - 1]
del state[n - 1]
else:
state[i] = n - 1
return i
s = dict()
for n in range(100, 0, -1):
print remove(random.randrange(n), n, s)
于 2013-09-24T15:27:52.463 に答える
5
かなり高速なワンライナー ( O(n + m), n=range,m=old samplesize):
next_sample = random.sample(set(range(100)).difference(my_sample), 10)
于 2013-09-20T16:22:04.497 に答える
5
これは @necromancer のクールなソリューションの書き直されたバージョンです。それをクラスにラップして正しく使いやすくし、より多くの dict メソッドを使用してコード行を削減します。
from random import randrange
class Sampler:
def __init__(self, n):
self.n = n # number remaining from original range(n)
# i is a key iff i < n and i already returned;
# in that case, state[i] is a value to return
# instead of i.
self.state = dict()
def get(self):
n = self.n
if n <= 0:
raise ValueError("range exhausted")
result = i = randrange(n)
state = self.state
# Most of the fiddling here is just to get
# rid of state[n-1] (if it exists). It's a
# space optimization.
if i == n - 1:
if i in state:
result = state.pop(i)
elif i in state:
result = state[i]
if n - 1 in state:
state[i] = state.pop(n - 1)
else:
state[i] = n - 1
elif n - 1 in state:
state[i] = state.pop(n - 1)
else:
state[i] = n - 1
self.n = n-1
return result
基本的なドライバーは次のとおりです。
s = Sampler(100)
allx = [s.get() for _ in range(100)]
assert sorted(allx) == list(range(100))
from collections import Counter
c = Counter()
for i in range(6000):
s = Sampler(3)
one = tuple(s.get() for _ in range(3))
c[one] += 1
for k, v in sorted(c.items()):
print(k, v)
および出力例:
(0, 1, 2) 1001
(0, 2, 1) 991
(1, 0, 2) 995
(1, 2, 0) 1044
(2, 0, 1) 950
(2, 1, 0) 1019
肉眼では、その分布は問題ありません (懐疑的な場合は、カイ 2 乗検定を実行してください)。ここでの解決策のいくつかは、(n の各 k-サブセットを等しい確率で返すにもかかわらず) 等しい確率で各順列を与えないためrandom.sample()、その点で異なります。
于 2013-09-24T18:50:43.900 に答える