博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
带权轮询算法
阅读量:6954 次
发布时间:2019-06-27

本文共 1900 字,大约阅读时间需要 6 分钟。

问题

有Q1、Q2、……、Qn n个队列,每个队列有一个权值W1、W2、……、Wn,需要每次从其中一个队列取出一个元素,使得从不同队列取出的元素数量比例服从权值的比例。

解释

这正是网络流量调度场景中的“带权轮询调度”(Weighted Round-Robin Scheduling,WRR),有现成的算法可用。

为了简单起见,先考虑最简单的情况,令 W1 = W2 = ... = Wn,那么“带权轮询调度”退化成“轮询调度”(Round-Robin Scheduling,RR),RR实现很简单,然后考虑权值不同的情况。

实现(python代码)

RR

# countN = 3# Round-Robin Schedulingdef rr_select():    last = N - 1    while True:        current = (last + 1) % N        last = current        yield currentrr_test = rr_select()for i in range(1000):    print(rr_test.__next__())

N是队列的个数,0到N-1数字代表这N个队列。

RR会依次从每个队列取出元素,很简单无需过多叙述。

WRR

# countN = 3weight = (60, 30, 10)# 最大公约数def gcd(nums):    m = nums[0]    for n in nums[1:]:        while n != 0:            m, n = n, m % n    return m# Weighted Round-Robin Schedulingdef wrr_select():    current = N - 1    current_weight = 0    while True:        current = (current + 1) % N        if current == 0:            current_weight -= gcd(weight)            if current_weight <= 0:                current_weight = max(weight)        if weight[current] >= current_weight:            yield currentwrr_test = wrr_select()for i in range(1000):    print(wrr_test.__next__())

这个算法需要解释一下。

先看一下取前10个元素的结果:

current_weight     从哪些队列取出了元素60                 050                 040                 030                 0 120                 0 110                 0 1 2

也就是每次for i in (0, 1, 2)的小周期内,当current_weight > weight[i]时,就把i选出来。当current_weight等于0了,就再从头开始,这算一个大周期。一个大周期包含max(weight)/gcd(weight)个小周期。

那如何证明这样取是符合权值比例的?

可以看到每个小周期中,都是要从权值最大的队列里拿走一个元素的,可以看作拿权值最大的那个作为基准,然后权值较小的直接拿它对比。那仅看权值为10的便可,10是60的1/6,把60分6分,只有1份是应该给10的,所以60知道降到10才满足10的条件。权值30的同理。

其实max(weight)和gcd(weight)都可以选择别的,但选它们两个可以满足最细粒度的平均,即每取出任意10个连续的中间结果,就必然服从权值比例,可以认为是最优的。

随机性考虑

WRR的运行结果是固定的,如果需要考虑随机性的话,需要再做一些额外工作。简单的话可以先对队列的顺序做随机,但这样实际的顺序还是固定的。可以按实际需要频繁暂存一定(随机)数量的结果,再随机处理后依次输出。

参考

付费解决 Windows、Linux、Shell、C、C++、AHK、Python、JavaScript、Lua 等领域相关问题,灵活定价,欢迎咨询,微信 ly50247。

转载地址:http://pctil.baihongyu.com/

你可能感兴趣的文章
Android实战技巧:消息循环与Looper
查看>>
android-audioRecord
查看>>
apache 访问权限基本设置
查看>>
jQuery的deferred对象详解
查看>>
python基础知识~ 序列化
查看>>
函数作业
查看>>
开发经理的职责
查看>>
FinalData 数据恢复工具[绿色版]
查看>>
linux vim
查看>>
莫比乌斯反演
查看>>
新SQL temp
查看>>
两个有序数组的合并
查看>>
JZ-C-29
查看>>
声明式事务xml Spring
查看>>
Activity的启动模式(android:launchMode)
查看>>
CQOI2007 涂色 paint (区间dp)
查看>>
Bootstrap定制(二)less基础语法
查看>>
js 数组排序
查看>>
android笔记--处理started service的多次启动请求(转)
查看>>
UE4 学习笔记1 变量的初始化
查看>>