Python中的加權隨機

ThinkSNS 發布于2019-07-24 17:47 / 2161人閱讀

摘要：我們平時比較多會遇到的一種情景是從一堆的數據中隨機選擇一個大多數我們使用就夠了但是假如我們要選取的這堆數據分別有自己的權重也就是他們被選擇的概率是不一樣的在這種情況下就需要使用加權隨機來處理這些數據簡單線性方法下面是一種簡單的方案傳入權重的

我們平時比較多會遇到的一種情景是從一堆的數據中隨機選擇一個, 大多數我們使用random就夠了, 但是假如我們要選取的這堆數據分別有自己的權重, 也就是他們被選擇的概率是不一樣的, 在這種情況下, 就需要使用加權隨機來處理這些數據

1. 簡單線性方法

下面是一種簡單的方案, 傳入權重的列表(weights), 然后會返回隨機結果的索引值(index), 比如我們傳入[2, 3, 5], 那么就會隨機的返回0(概率0.2), 1(概率0.3), 2(概率0.5)

簡單的思路就是把所有的權重加和, 然后隨機一個數, 看看落在哪個區間

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. 加速搜索

上面這個方法看起來非常簡單, 已經可以完成我們所要的加權隨機, 然是最后的這個for循環貌似有些啰嗦, Python有個內置方法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里面應該插入的位置, 兩個方法看起來差不多, 但是第二個會更快一些, 取決于weights這個數組的長度, 如果長度大于1000, 大約會快30%左右

3. 去掉臨時變量

其實在這個方法里面totals這個數組并不是必要的, 我們調整下策略, 就可以判斷出weights中的位置

def weighted_choice(weights):
  rnd = random.random() * sum(weights)
  for i, w in enumerate(weights):
      rnd -= w
      if rnd < 0:
          return i

這個方法比第二種方法竟然快了一倍, 當然, 從算法角度角度, 復雜度是一樣的, 只不過我們把賦值臨時變量的功夫省下來了, 其實如果傳進來的weights是已經按照從大到小排序好的話, 速度會更快, 因為rnd遞減的速度最快(先減去最大的數)

4. 更多的隨機數

如果我們使用同一個權重數組weights, 但是要多次得到隨機結果, 多次的調用weighted_choice方法, totals變量還是有必要的, 提前計算好它, 每次獲取隨機數的消耗會變得小很多

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()

在調用次數超過1000次的時候, WeightedRandomGenerator的速度是weighted_choice的100倍

所以我們在對同一組權重列表進行多次計算的時候選擇方法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]

如果你有更好的方法, 歡迎在留言區討論

參考文章: Weighted random generation in Python

本文發表在致趣技術團隊博客, 加入致趣

GPU云服務器云服務器 python加權聚類 python 隨機 python隨機森林 python隨機數字

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/37442.html

隨機加權平均 -- 在深度學習中獲得最優結果的新方法

摘要：或許是有的這是一篇關于隨機加權平均的新論文所獲得的成果。隨機加權平均，隨機加權平均和快速幾何集成非常近似，除了計算損失的部分。在這篇文章中，我將討論最近兩篇有趣的論文。它們提供了一種簡單的方式，通過使用一種巧妙的集成方法提升神經網絡的性能。Garipov 等人提出的 Loss Surfaces, Mode Connectivity, and Fast Ensembling of DNNs ...

kaka 2019-04-25 18:27 評論0 收藏0
Hive集群合并之應用端的負載均衡算法

摘要：負載均衡算法的選擇常用的負載均衡算法有哪些呢隨機算法，輪詢，算法，加權隨機算法，加權輪詢算法，一致性算法。首選，我們會有集群對應的的地址列表，然后我們通過某種算法這里指的就是負載均衡算法，獲取其中一個的地址進行任務提交這就是任務調度。 showImg(https://segmentfault.com/img/bVbsxlb?w=1104&h=794); 0.背景有這么一個場景，我們有...

wangbinke 2019-08-19 11:40 評論0 收藏0
Node.js運行原理、高并發性能測試對比及生態圈匯總

摘要：模式，單實例多進程，常用于多語言混編，比如等，不支持端口復用，需要自己做應用的端口分配和負載均衡的子進程業務代碼。就是我們需要一個調度者，保證所有后端服務器都將性能充分發揮，從而保持服務器集群的整體性能最優，這就是負載均衡。 showImg(https://segmentfault.com/img/remote/1460000019425391?w=1440&h=1080); Nod...

kamushin233 2019-08-30 11:08 評論0 收藏0