问题
有Q1、Q2、……、Qn n个队列，每个队列有一个权值W1、W2、……、Wn，需要每次从其中一个队列取出一个元素，使得从不同队列取出的元素数量比例服从权值的比例。
解释
这正是网络流量调度场景中的“带权轮询调度”（Weighted Round-Robin Scheduling，WRR），有现成的算法可用。
为了简单起见，先考虑最简单的情况，令 W1 = W2 = ... = Wn，那么“带权轮询调度”退化成“轮询调度”（Round-Robin Scheduling，RR），RR实现很简单，然后考虑权值不同的情况。
实现（python代码）
RR
# count
N = 3
# Round-Robin Scheduling
def rr_select():
last = N - 1
while True:
current = (last + 1) % N
last = current
yield current
rr_test = rr_select()
for i in range(1000):
print(rr_test.__next__())
N是队列的个数，0到N-1数字代表这N个队列。
RR会依次从每个队列取出元素，很简单无需过多叙述。
WRR
# count
N = 3
weight = (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 Scheduling
def 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 current
wrr_test = wrr_select()
for i in range(1000):
print(wrr_test.__next__())
这个算法需要解释一下。
先看一下取前10个元素的结果：
current_weight 从哪些队列取出了元素
60 0
50 0
40 0
30 0 1
20 0 1
10 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。
网友评论