random.sampleの時間複雑度

Question

別のスレッドでは、バイナリヒープ重み付きランダムサンプルの時間複雑さがO（n * log（m））に等しく、ここでnは選択肢の数であり、mは数選択するノードの数。

Pythonでrandom.sampleとして使用されている重み付けされていないランダムなサンプルの時間的な複雑さが不思議でした。時間の複雑さは単にO（n）かそれとも完全に他の何かですか？

Answer 1

Pythonソース：random.py（行267）。

315    selected = set() 
    316    selected_add = selected.add 
    317    for i in range(k): 
    318     j = randbelow(n) 
    319     while j in selected: 
    320      j = randbelow(n) 
    321     selected_add(j) 
    322     result[i] = population[j] 

それは基本的に​​へのランダムインデックスの「サイコロを振り」：

はここに関連するビットです。すでにselectedというセットに含まれているインデックスを取得した場合は、それがリロールされます。すすぎ、泡立て、そしてくり返しk回（kはあなたが求めたサンプルの数です）

要求されたサンプル数のサイズでは、O(n)と思われます。小さなセットにはいくつかの最適化がありますが、物の肉は上のメインループです。

---

編集：サンプル数が要求されたとき、kは、総人口nの大部分であるため

私は信じてはライン305-313は特殊なケースです。人口全体からランダムな要素をローリングする代わりに（すでに選択した要素と衝突した場合に再ロールバックする）、選択する要素のリストを明示的に維持します。私たちは毎回新しい要素を得ることが保証されていますが、リストを維持しなければならないというトレードオフがあります。

私がこれを間違って解釈している場合は、以下にコメントしてください。

303   result = [None] * k 
    304   setsize = 21  # size of a small set minus size of an empty list 
    305   if k > 5: 
    306    setsize += 4 ** _ceil(_log(k * 3, 4)) # table size for big sets 
    307   if n <= setsize: 
    308    # An n-length list is smaller than a k-length set 
    309    pool = list(population) 
    310    for i in range(k):   # invariant: non-selected at [0,n-i) 
    311     j = randbelow(n-i) 
    312     result[i] = pool[j] 
    313     pool[j] = pool[n-i-1] # move non-selected item into vacancy 
    314   else: 
    315    selected = set() 
    316    selected_add = selected.add 
    317    for i in range(k): 
    318     j = randbelow(n) 
    319     while j in selected: 
    320      j = randbelow(n) 
    321     selected_add(j) 
    322     result[i] = population[j] 
    323   return result