資訊專欄INFORMATION COLUMN
摘要：我們平時比較多會遇到的一種情景是從一堆的數(shù)據(jù)中隨機選擇一個大多數(shù)我們使用就夠了但是假如我們要選取的這堆數(shù)據(jù)分別有自己的權(quán)重也就是他們被選擇的概率是不一樣的在這種情況下就需要使用加權(quán)隨機來處理這些數(shù)據(jù)簡單線性方法下面是一種簡單的方案傳入權(quán)重的
我們平時比較多會遇到的一種情景是從一堆的數(shù)據(jù)中隨機選擇一個, 大多數(shù)我們使用random就夠了, 但是假如我們要選取的這堆數(shù)據(jù)分別有自己的權(quán)重, 也就是他們被選擇的概率是不一樣的, 在這種情況下, 就需要使用加權(quán)隨機來處理這些數(shù)據(jù)
1. 簡單線性方法下面是一種簡單的方案, 傳入權(quán)重的列表(weights), 然后會返回隨機結(jié)果的索引值(index), 比如我們傳入[2, 3, 5], 那么就會隨機的返回0(概率0.2), 1(概率0.3), 2(概率0.5)
簡單的思路就是把所有的權(quán)重加和, 然后隨機一個數(shù), 看看落在哪個區(qū)間
import random
def weighted_choice(weights):
totals = []
running_total = 0
for w in weights:
running_total += w
totals.append(running_total)
rnd = random.random() * running_total
for i, total in enumerate(totals):
if rnd < total:
return i
2. 加速搜索
上面這個方法看起來非常簡單, 已經(jīng)可以完成我們所要的加權(quán)隨機, 然是最后的這個for循環(huán)貌似有些啰嗦, Python有個內(nèi)置方法bisect可以幫我們加速這一步
import random
import bisect
def weighted_choice(weights):
totals = []
running_total = 0
for w in weights:
running_total += w
totals.append(running_total)
rnd = random.random() * running_total
return bisect.bisect_right(totals, rnd)
bisect方法可以幫我們查找rnd在totals里面應(yīng)該插入的位置, 兩個方法看起來差不多, 但是第二個會更快一些, 取決于weights這個數(shù)組的長度, 如果長度大于1000, 大約會快30%左右
3. 去掉臨時變量其實在這個方法里面totals這個數(shù)組并不是必要的, 我們調(diào)整下策略, 就可以判斷出weights中的位置
def weighted_choice(weights):
rnd = random.random() * sum(weights)
for i, w in enumerate(weights):
rnd -= w
if rnd < 0:
return i
這個方法比第二種方法竟然快了一倍, 當(dāng)然, 從算法角度角度, 復(fù)雜度是一樣的, 只不過我們把賦值臨時變量的功夫省下來了, 其實如果傳進來的weights是已經(jīng)按照從大到小排序好的話, 速度會更快, 因為rnd遞減的速度最快(先減去最大的數(shù))
4. 更多的隨機數(shù)如果我們使用同一個權(quán)重數(shù)組weights, 但是要多次得到隨機結(jié)果, 多次的調(diào)用weighted_choice方法, totals變量還是有必要的, 提前計算好它, 每次獲取隨機數(shù)的消耗會變得小很多
class WeightedRandomGenerator(object):
def __init__(self, weights):
self.totals = []
running_total = 0
for w in weights:
running_total += w
self.totals.append(running_total)
def next(self):
rnd = random.random() * self.totals[-1]
return bisect.bisect_right(self.totals, rnd)
def __call__(self):
return self.next()
在調(diào)用次數(shù)超過1000次的時候, WeightedRandomGenerator的速度是weighted_choice的100倍
所以我們在對同一組權(quán)重列表進行多次計算的時候選擇方法4, 如果少于100次, 則使用方法3
5. 使用accumulate在python3.2之后, 提供了一個itertools.accumulate方法, 可以快速的給weights求累積和
>>>> from itertools import accumulate >>>> data = [2, 3, 5, 10] >>>> list(accumulate(data)) [2, 5, 10, 20]
如果你有更好的方法, 歡迎在留言區(qū)討論
參考文章: Weighted random generation in Python
本文發(fā)表在致趣技術(shù)團隊博客, 加入致趣
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/37442.html
摘要：或許是有的這是一篇關(guān)于隨機加權(quán)平均的新論文所獲得的成果。隨機加權(quán)平均，隨機加權(quán)平均和快速幾何集成非常近似，除了計算損失的部分。 在這篇文章中，我將討論最近兩篇有趣的論文。它們提供了一種簡單的方式，通過使用一種巧妙的集成方法提升神經(jīng)網(wǎng)絡(luò)的性能。Garipov 等人提出的 Loss Surfaces, Mode Connectivity, and Fast Ensembling of DNNs ...
摘要：負(fù)載均衡算法的選擇常用的負(fù)載均衡算法有哪些呢隨機算法，輪詢，算法，加權(quán)隨機算法，加權(quán)輪詢算法，一致性算法。首選，我們會有集群對應(yīng)的的地址列表，然后我們通過某種算法這里指的就是負(fù)載均衡算法，獲取其中一個的地址進行任務(wù)提交這就是任務(wù)調(diào)度。 showImg(https://segmentfault.com/img/bVbsxlb?w=1104&h=794); 0.背景 有這么一個場景，我們有...
摘要：模式，單實例多進程，常用于多語言混編，比如等，不支持端口復(fù)用，需要自己做應(yīng)用的端口分配和負(fù)載均衡的子進程業(yè)務(wù)代碼。就是我們需要一個調(diào)度者，保證所有后端服務(wù)器都將性能充分發(fā)揮，從而保持服務(wù)器集群的整體性能最優(yōu)，這就是負(fù)載均衡。 showImg(https://segmentfault.com/img/remote/1460000019425391?w=1440&h=1080); Nod...
閱讀 1051·2021-09-13 10:29
閱讀 3398·2019-08-29 18:31
閱讀 2648·2019-08-29 11:15
閱讀 3022·2019-08-26 13:25
閱讀 1381·2019-08-26 12:00
閱讀 2324·2019-08-26 11:41
閱讀 3423·2019-08-26 10:31
閱讀 1498·2019-08-26 10:25
