給定一組布爾值，選擇隨機TRUE值索引的最有效方法是什麼？

給出一個大小爲n的數組，其中包含任意布爾值。給定一組布爾值，選擇隨機TRUE值索引的最有效方法是什麼？

什麼是返回隨機TRUE值的索引的最快方法。

該算法應隨機返回任何一個包含TRUE的索引。

2012-03-23 PaulV

事情是這樣的：

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; 
     } 
    } 
}

因此，對於例如4個值，你得到他們的指標以下可能性：

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

編輯：正如史蒂夫·傑索普指出浮點比較最終會導致非常不一致的選擇。假設unit_random被定義爲rand()/RAND_MAX的對比可以改爲：

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

這不會給完美的分佈因rand離散性，但它會更好。

來源

2012-03-23 13:42:24

對不起，我忘了詞。我的意思是說：返回一個隨機TRUE值的索引...不僅僅是我們找到的第一個。但函數應隨機返回包含TRUE的任何一個索引。 – PaulV 2012-03-23 13:46:15

@PaulV這正是這個功能所做的。 – 2012-03-23 14:09:39

@尼克是啊，但我已經編輯了我的答案;） – 2012-03-23 14:17:05

「隨機分佈」的含義並不十分清楚。這是否意味着「有一些未知的分佈」？如果是這樣，假設所有可能的分佈是同等可能的，所以「期望分佈」（如「期望值」）是均勻的（所有可能分佈的「平均值」）。然後，任何指數爲真，概率爲1/2。所以你的任務變成了儘可能快地遍歷數組的任務。從一開始就像通常迭代一個數組一樣，直到遇到一個TRUE值。

來源

2012-03-23 13:45:34

我的意思是沒有任何值的模式。他們不遵循任何分配功能。 – PaulV 2012-03-23 13:55:53

猜測這意味着[均勻分佈]（http://en.wikipedia.org/wiki/Uniform_distribution_（discrete）），對不對？ ;） – 2012-03-23 13:58:33

@PaulV：「隨機分佈」可能是一個糟糕的短語，如果你的意思是「他們沒有遵循任何分佈函數」。你可以說「任意布爾值」，或者只是「布爾值」。那麼你必須定義「最快」的含義，因爲如果你沒有這個值的分佈，那麼對於速度取決於這些值的任何算法，「預期的運行時間」是沒有的。 – 2012-03-23 14:47:53

爲了返回它，你必須首先計算True值（沒有辦法跳過那個）並且在另一個數組中累積它們的索引。計數後，您只需生成從0到N-1的隨機整數（其中N是True值的數目），然後從創建的數組中選取值。

僞蟒蛇：

indices=[] 

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

來源

2012-03-23 13:59:10

最快的解決辦法 - 假設你不要在同一陣列上反覆選擇 - 是選擇一個隨機指數，返回它，如果它是真的，並重復如果沒有。在最好的情況下，所有條目都是真的，這是O（1）;在最壞的情況下，只有一個條目是真實的，這是O（n）（每次嘗試有1/n的機會擊中唯一的真實值，這意味着預期的n嘗試次數）。這並不比任何其他發佈的解決方案差。

但是，如果您希望數組通常幾乎都是錯誤的，您可能需要選擇另一個解決方案，因爲此隨機方法的運行時差異很大。

來源

2012-03-23 14:09:14

「這並不比其他任何解決方案都差」 - 複雜性並非如此，但它比安德烈亞斯的答案使用緩存效率低。而FWIW，安德烈亞斯的代碼捕捉失敗案例，而這種方法並沒有。也許「最好」的東西（交易期望與最壞的情況）是執行少量的隨機樣本，如果他們都沒有發現真實值，那麼就可以得出結論，數組很稀疏，並回退到安德烈亞斯的解決方案或類似的。 – 2012-03-23 14:39:32

簡單的解決方案：可以生成索引的置換（1：n）和在置換回報指數的順序如果相應值爲true

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

來源

2012-03-23 17:04:12 ElKamina

給定一組布爾值，選擇隨機TRUE值索引的最有效方法是什麼？

回答

相關問題