Biorąc pod uwagę szereg booleans, jaki jest najskuteczniejszy sposób, aby wybrać indeks losowej wartości TRUE?

Question

Dostajesz tablicę o rozmiarze n, zawierającą dowolne wartości logiczne.

Jaki jest najszybszy sposób na zwrócenie indeksu losowej wartości PRAWDA.

Algorytm powinien losowo zwracać dowolny z indeksów zawierających PRAWDA.

Answer 1

coś takiego:

int count = 0; 
int index = -1; 
for (int i = 0; i != n; ++i) 
{ 
    if (values[i]) 
    { 
     ++count; 
     if (unit_random <= 1.0f/count) 
     { 
      index = i; 
     } 
    } 
} 

Więc dla 4 wartości na przykład uzyskać następujące prawdopodobieństwa dla swoich indeksach:

1: (1/1) * (1/2) * (2/3) * (3/4) = 1/4 
2: (1/2) * (2/3) * (3/4) = 1/4 
3: (1/3) * (3/4) = 1/4 
4: 1/4 = 1/4 

EDIT: Jak Steve Jessop wskazał na zmiennoprzecinkowych porównania ostatecznie doprowadzi do bardzo niejednolitej selekcji. Zakładając unit_random jest zdefiniowany jako rand()/RAND_MAX porównania mogą być zmienione na:

typedef unsigned long long u64; 
u64 product = u64(count) * rand(); 
if (product <= u64(RAND_MAX)) 

To nie dadzą doskonały rozkład ze względu na dyskretny charakter rand ale będzie lepiej.

Answer 2

Nie jest do końca jasne, co oznacza "losowo distibuted". Czy to oznacza "z nieznaną dystrybucją"? Jeśli tak, to udawajmy, że wszystkie możliwe rozkłady są równie prawdopodobne, więc "oczekiwana dystrybucja" (jak w "wartości oczekiwanej") jest jednolita ("średnia" wszystkich możliwych rozkładów). Następnie dowolny indeks ma wartość PRAWDA z prawdopodobieństwem 1/2. Zatem twoim zadaniem staje się jak najszybsze iterowanie przez tablicę. Zacznij od początku, tak jakbyś normalnie iterował tablicę, dopóki nie napotkasz wartości PRAWDA.

Answer 3

Aby go zwrócić, musisz najpierw policzyć wartości True (nie ma sposobu, aby je pominąć) i zebrać ich indeksy w innej tablicy. A po zliczeniu trzeba po prostu wygenerować losową liczbę całkowitą od 0 do N-1 (gdzie N jest liczbą wartości True) i wybrać wartość z utworzonej tablicy.

w pseudo-python:

indices=[] 

for i,val in enumerate(arr): 
    if val: 
     indices.append(i) 
randi = randint(0,len(indices)-1) 
return indices[randi] 

Answer 4

Najszybszym rozwiązaniem - zakładając, że nie wielokrotnie wybrać na tej samej tablicy - jest, aby wybrać indeks losową, zwrócić go, czy to prawda, i powtórzyć, jeśli nie. W najlepszym przypadku, gdy wszystkie wpisy są prawdziwe, jest to O (1); w najgorszym przypadku, gdy tylko jeden wpis jest prawdziwy, jest to O (n) (każda próba ma 1/n szansę na trafienie w jedyną prawdziwą wartość, co oznacza spodziewaną liczbę prób n). To nie jest gorsze niż jakiekolwiek inne opublikowane rozwiązania.

Jeśli spodziewasz się, że tablica będzie prawie zawsze fałszywa, możesz wybrać inne rozwiązanie, ponieważ wariancja w czasie wykonywania tej przypadkowej metody będzie wysoka.

Answer 5

Proste rozwiązanie: Generowanie możliwych permutacji indeksów (1: n) i rzędu permutacji tego wskaźnika powrotnej, gdy odpowiednia wartość prawda

def randomTrue(x): 
    perm = randomPermute(0:len(x)) 
    for i in perm: 
     if x[i]: 
      return i