從元素具有權重的列表中選擇k個隨機元素這里精美地描述了沒有任何權重（相等概率）的選擇。我想知道是否有辦法將這種方法轉換為加權方法。我也對其他方法感興趣。更新：無需更換的采樣
3 回答
慕尼黑的夜晚無繁華
TA貢獻1864條經驗 獲得超6個贊
我知道這是一個非常古老的問題，但是如果你應用一點數學，我認為在O（n）時間有一個巧妙的技巧！
該指數分布有兩個非常有用的特性。
給定來自具有不同速率參數的不同指數分布的n個樣本，給定樣本的最小概率等于其速率參數除以所有速率參數的總和。
它是“無記憶的”。因此，如果您已經知道最小值，那么任何剩余元素是第二個到最小值的概率與如果真正的最小值被移除（并且從未生成）的概率相同，那個元素將是新的分鐘。這看起來很明顯，但我認為由于某些條件概率問題，其他分布可能不是這樣。
使用事實1，我們知道選擇單個元素可以通過生成速率參數等于權重的指數分布樣本，然后選擇具有最小值的指數分布樣本來完成。
使用事實2，我們知道我們不必重新生成指數樣本。相反，只需為每個元素生成一個元素，并使用最低樣本的k元素。
找到最低k可以在O（n）中完成。使用Quickselect算法查找第k個元素，然后簡單地再次通過所有元素并輸出低于第k個的所有元素。
一個有用的說明：如果您無法立即訪問庫以生成指數分布樣本，則可以通過以下方式輕松完成： -ln(rand())/weight
添加回答
舉報
0/150
提交
取消