第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

為了賬號安全,請及時綁定郵箱和手機(jī)立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

從元素具有權(quán)重的列表中選擇k個隨機(jī)元素

從元素具有權(quán)重的列表中選擇k個隨機(jī)元素

從元素具有權(quán)重的列表中選擇k個隨機(jī)元素這里精美地描述了沒有任何權(quán)重(相等概率)的選擇。我想知道是否有辦法將這種方法轉(zhuǎn)換為加權(quán)方法。我也對其他方法感興趣。更新:無需更換的采樣
查看完整描述

3 回答

?
慕尼黑的夜晚無繁華

TA貢獻(xiàn)1864條經(jīng)驗(yàn) 獲得超6個贊

我知道這是一個非常古老的問題,但是如果你應(yīng)用一點(diǎn)數(shù)學(xué),我認(rèn)為在O(n)時間有一個巧妙的技巧!

指數(shù)分布有兩個非常有用的特性。

  1. 給定來自具有不同速率參數(shù)的不同指數(shù)分布的n個樣本,給定樣本的最小概率等于其速率參數(shù)除以所有速率參數(shù)的總和。

  2. 它是“無記憶的”。因此,如果您已經(jīng)知道最小值,那么任何剩余元素是第二個到最小值的概率與如果真正的最小值被移除(并且從未生成)的概率相同,那個元素將是新的分鐘。這看起來很明顯,但我認(rèn)為由于某些條件概率問題,其他分布可能不是這樣。

使用事實(shí)1,我們知道選擇單個元素可以通過生成速率參數(shù)等于權(quán)重的指數(shù)分布樣本,然后選擇具有最小值的指數(shù)分布樣本來完成。

使用事實(shí)2,我們知道我們不必重新生成指數(shù)樣本。相反,只需為每個元素生成一個元素,并使用最低樣本的k元素。

找到最低k可以在O(n)中完成。使用Quickselect算法查找第k個元素,然后簡單地再次通過所有元素并輸出低于第k個的所有元素。

一個有用的說明:如果您無法立即訪問庫以生成指數(shù)分布樣本,則可以通過以下方式輕松完成: -ln(rand())/weight


查看完整回答
反對 回復(fù) 2019-08-06
  • 3 回答
  • 0 關(guān)注
  • 962 瀏覽

添加回答

舉報(bào)

0/150
提交
取消
微信客服

購課補(bǔ)貼
聯(lián)系客服咨詢優(yōu)惠詳情

幫助反饋 APP下載

慕課網(wǎng)APP
您的移動學(xué)習(xí)伙伴

公眾號

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號