Najbardziej wydajna metoda generowania liczby losowej ze stałą liczbą bitów ustawiona

Question

Potrzebuję wygenerować liczbę losową, ale musi być wybrana ze zbioru liczb binarnych z równą liczbą bitów zestawu. Na przykład. wybierz losową wartość bajtową z dokładnie 2-bitowym zestawem ...

00000000 - no 
00000001 - no 
00000010 - no 
00000011 - YES 
00000100 - no 
00000101 - YES 
00000110 - YES 
... 

=> Set of possible numbers 3, 5, 6... 

Zauważ, że jest to uproszczony zestaw liczb. Pomyśl bardziej wzdłuż linii "Wybierz losowy 64-bitowy numer z dokładnie 40 bitami". Każda liczba z zestawu musi być równie prawdopodobna.

Answer 1

Dokonaj losowego wyboru ze zbioru wszystkich pozycji bitów, a następnie ustaw te bity.

przykład w Pythonie

def random_bits(word_size, bit_count): 
    number = 0 
    for bit in random.sample(range(word_size), bit_count): 
     number |= 1 << bit 
    return number 

Wyniki prowadzenia powyższych 10 razy:

0xb1f69da5cb867efbL 
0xfceff3c3e16ea92dL 
0xecaea89655befe77L 
0xbf7d57a9b62f338bL 
0x8cd1fee76f2c69f7L 
0x8563bfc6d9df32dfL 
0xdf0cdaebf0177e5fL 
0xf7ab75fe3e2d11c7L 
0x97f9f1cbb1f9e2f8L 
0x7f7f075de5b73362L 

Answer 2

powiedzieć, że liczba bitów określone jest B, zaś wielkość słowo wag. Stworzyłem wektor v o długości w z pierwszymi wartościami b ustawionymi na 1 i resztą ustawionymi na 0. Następnie przetasuj v.

Answer 3

Oto kolejna opcja, która w praktyce jest bardzo prosta i stosunkowo szybka.

choose a bit at random 
if it is already set 
    do nothing 
else 
    set it 
    increment count 
end if 

Powtarzaj, aż liczba będzie równa liczbie bitów, które chcesz ustawić.

Powoduje to spowolnienie tylko wtedy, gdy liczba bitów, które chcesz ustawić (nazywając to k), przekracza połowę długości słowa (nazwij ją: N). W takim przypadku użyj algorytmu do ustawienia bitów N - k, a następnie odwróć wszystkie bity w wyniku.

Założę się, że spodziewany czas biegu jest całkiem niezły, chociaż jestem zbyt leniwy/głupi, aby obliczyć go dokładnie teraz. Ale mogę go ograniczyć jako mniej niż 2 * k ... Spodziewana liczba rzutów monetą, aby uzyskać "główki", wynosi dwa, a każda iteracja ma tutaj lepszą niż 1/2 szansę na sukces.

Answer 4

Jeśli nie masz wygodę Pythona random.sample, można to zrobić w C z użyciem klasycznej sekwencyjny algorytm próbkowania:

unsigned long k_bit_helper(int n, int k, unsigned long bit, unsigned long accum) { 
    if !(n && k) 
    return accum; 
    if (k > rand() % n) 
    return k_bit_helper(n - 1, k - 1, bit + bit, accum + bit); 
    else 
    return k_bit_helper(n - 1, k, bit + bit, accum); 
} 

unsigned long random_k_bits(int k) { 
    return k_bit_helper(64, k, 1, 0); 
} 

Koszt powyższego będzie zdominowany przez koszt generowania liczby losowe (również w innych rozwiązaniach). Możesz zoptymalizować to nieco, jeśli masz dobry prng przez grupowanie: na przykład, ponieważ wiesz, że liczby losowe będą w coraz mniejszych zakresach, możesz uzyskać liczby losowe dla n przez n-3, otrzymując losową liczbę z zakresu 0..(n * (n - 1) * (n - 2) * (n - 3)) a następnie wyodrębnianie poszczególnych liczb losowych:

r = randint(0, n * (n - 1) * (n - 2) * (n - 3) - 1); 
rn = r % n; r /= n 
rn1 = r % (n - 1); r /= (n - 1); 
rn2 = r % (n - 2); r /= (n - 2); 
rn3 = r % (n - 3); r /= (n - 3); 

maksymalna wartość n przypuszczalnie 64 lub 2 , a więc maksymalna wartość powyższego produktu jest z pewnością mniej niż 2 . Rzeczywiście, jeśli użyjesz 64-bitowego prng, możesz wyodrębnić z niego aż 10 losowych liczb. Jednak nie rób tego, chyba że wiesz, że prng, którego używasz, produkuje niezależnie losowe bity.

Answer 5

Znalazłem eleganckie rozwiązanie: losową dychotomię.

Idea jest taka, że ​​średnio:

• i z liczby losowej jest podzielenie przez 2 liczby bitów ustawionych,
• lub dodaje 50% ustawionych bitów.

kod C podczas kompilacji gcc (mieć __builtin_popcountll)

#include <assert.h> 
#include <stdint.h> 
#include <stdio.h> 
#include <stdlib.h> 
/// Return a random number, with nb_bits bits set out of the width LSB 
uint64_t random_bits(uint8_t width, uint8_t nb_bits) 
{ 
    assert(nb_bits <= width); 
    assert(width <= 64); 
    uint64_t x_min = 0; 
    uint64_t x_max = width == 64 ? (uint64_t)-1 : (1UL<<width)-1; 
    int n = 0; 

    while (n != nb_bits) 
    { 
     // generate a random value of at least width bits 
     uint64_t x = random(); 
     if (width > 31) 
      x ^= random() << 31; 
     if (width > 62) 
      x ^= random() << 33; 

     x = x_min | (x & x_max); // x_min is a subset of x, which is a subset of x_max 
     n = __builtin_popcountll(x); 
     printf("x_min = 0x%016lX, %d bits\n", x_min, __builtin_popcountll(x_min)); 
     printf("x_max = 0x%016lX, %d bits\n", x_max, __builtin_popcountll(x_max)); 
     printf("x  = 0x%016lX, %d bits\n\n", x, n); 
     if (n > nb_bits) 
      x_max = x; 
     else 
      x_min = x; 
    } 

    return x_min; 
} 

Na ogół są potrzebne mniejsze niż 10 zwojów, aby osiągnąć żądaną liczbę bitów (i szczęście to może mieć 2 lub 3 pętle). Przypadki narożne (nb_bity = 0,1, szerokość-1, szerokość) działają, nawet jeśli specjalny przypadek byłby szybszy.

Przykład wyniku:

x_min = 0x0000000000000000, 0 bits 
x_max = 0x1FFFFFFFFFFFFFFF, 61 bits 
x  = 0x1492717D79B2F570, 33 bits 

x_min = 0x0000000000000000, 0 bits 
x_max = 0x1492717D79B2F570, 33 bits 
x  = 0x1000202C70305120, 14 bits 

x_min = 0x0000000000000000, 0 bits 
x_max = 0x1000202C70305120, 14 bits 
x  = 0x0000200C10200120, 7 bits 

x_min = 0x0000200C10200120, 7 bits 
x_max = 0x1000202C70305120, 14 bits 
x  = 0x1000200C70200120, 10 bits 

x_min = 0x1000200C70200120, 10 bits 
x_max = 0x1000202C70305120, 14 bits 
x  = 0x1000200C70201120, 11 bits 

x_min = 0x1000200C70201120, 11 bits 
x_max = 0x1000202C70305120, 14 bits 
x  = 0x1000200C70301120, 12 bits 

width = 61, nb_bits = 12, x = 0x1000200C70301120 

Oczywiście, trzeba mieć dobry PRNG. W przeciwnym razie możesz zmierzyć się z nieskończoną pętlą.

Answer 6

Mam inną sugestię na podstawie wyliczenia: wybierz liczbę losową i pomiędzy 1 i n wybierz k, i wygeneruj i-tą kombinację. Na przykład dla n = 6, k = 3 to 20 kombinacje są:

000111 
001011 
010011 
100011 
001101 
010101 
100101 
011001 
101001 
110001 
001110 
010110 
100110 
011010 
101010 
110010 
011100 
101100 
110100 
111000 

Powiedzmy, że losowo wybrać liczbę kombinacji 7. Najpierw należy sprawdzić, czy ma ona 1 na ostatniej pozycji: ma, bo pierwsze 10 (5 wybiera 2) kombinacji ma. Następnie rekursywnie sprawdzamy pozostałe pozycje. Oto kod C++:

word ithCombination(int n, int k, word i) { 
    // i is zero-based 
    word x = 0; 
    word b = 1; 
    while (k) { 
     word c = binCoeff[n - 1][k - 1]; 
     if (i < c) { 
      x |= b; 
      --k; 
     } else { 
      i -= c; 
     } 
     --n; 
     b <<= 1; 
    } 
    return x; 
} 
word randomKBits(int k) { 
    word i = randomRange(0, binCoeff[BITS_PER_WORD][k] - 1); 
    return ithCombination(BITS_PER_WORD, k, i); 
} 

być szybki, używamy wcześniej obliczone Symbol Newtona w binCoeff. Funkcja randomRange zwraca losową liczbę całkowitą między dwoma granicami (włącznie).

Zrobiłem kilka ustawień czasowych (source). Przy domyślnym generatorze liczb losowych C++ 11 większość czasu zajmuje generowanie liczb losowych. To rozwiązanie jest najszybsze, ponieważ wykorzystuje bezwzględną minimalną liczbę losowych bitów. Jeśli używam szybkiego generatora liczb losowych, to najszybsze jest rozwiązanie według mic006. Jeśli wiadomo, że k jest bardzo mały, najlepiej jest po prostu losowo ustawić bity, aby ustawić k.