Python中的加权随机

ThinkSNS 发布于2019-07-24 17:47 / 2005人阅读

摘要：我们平时比较多会遇到的一种情景是从一堆的数据中随机选择一个大多数我们使用就够了但是假如我们要选取的这堆数据分别有自己的权重也就是他们被选择的概率是不一样的在这种情况下就需要使用加权随机来处理这些数据简单线性方法下面是一种简单的方案传入权重的

我们平时比较多会遇到的一种情景是从一堆的数据中随机选择一个, 大多数我们使用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随机数字

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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