Złożoność czasowa random.sample

Question

W innym wątku widziałem, że złożoność czasowa losowej próbki ważonej binarnymi stertami jest równa O (n * log (m)), gdzie n jest liczbą wyborów, a m jest liczbą węzłów do wyboru.

Zastanawiam się nad złożonością czasową nieważonej próbki losowej, która jest używana przez Python jako random.sample. Czy złożoność czasu po prostu O (n) czy jest czymś zupełnie innym?

Answer 1

Źródło w języku Python: random.py (wiersz 267).

Oto odnośny bit:

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] 

To w zasadzie "rzuca kośćmi" random indeksem population. Jeśli otrzyma indeks, który jest już w zestawie selected, zostanie ponownie załadowany. Opłukać, spienić i powtórzyć k razy (gdzie k jest liczba próbek prosiłeś.)

Wydaje się O(n) w wielkości wymaganej liczby próbek. Istnieją pewne optymalizacje dla małych zestawów, ale mięso z rzeczy jest główną pętlą powyżej.

---

Edit:

wierzę linia 305-313 są szczególnym przypadku, gdy liczba próbek wymagane, k, to duża część całej populacji n. Zamiast toczyć losowe elementy z całej populacji (i przewracać, jeśli zderzamy się z elementem, który już wybraliśmy), jawnie utrzymujemy listę elementów, które musimy jeszcze wybrać. Gwarantujemy, że otrzymamy nowy element za każdym razem, ale kompromisem jest to, że musimy utrzymywać tę listę.

Jeśli źle zinterpretuję tę wypowiedź, prosimy o komentarz poniżej.

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