您正在寻找的算法类称为多路复用。多路复用器接受多个输入流,并创建一个输出流,一次从输入中选择一个项目。有许多不同的多路复用策略。我将描述一个易于实现且性能良好的。
总体思路是,每个项目都有一个name、rate和accumulator,然后选择其 accumulator 中值最大的项目。在问题中给出的示例中,Apple 的费率为 2,Banana 的费率为 1,Pineapple 的费率为 3,Orange 的费率为 1。费率之和就是周期,即 7。
该算法的操作如下:
initialize all accumulators to 0
for each slot in one period:
choose the item with the largest accumulator, and add it to the output
update each accumulator by adding the rate to the accumulator
subtract the period from the accumulator of the chosen item
下表显示了算法的进展情况。这些插槽标记为 S1 到 S7。对于每个插槽,有两列数字,每个项目的累加器值,以及对累加器的调整。
在插槽 1 中,选择了橙色,因此对累加器的调整是+1 -7 = -6
(加上利率,减去周期)。对于每个其他项目,调整等于费率。请注意,所有累加器都从 0 开始,并在第七个插槽后返回 0。因此,该算法可以针对任意数量的时隙运行,并且它会简单地重复相同的模式。
Name Rate __S1__ __S2__ __S3__ __S4__ __S5__ __S6__ __S7__
Orange 1/7 0 -6 -6 +1 -5 +1 -4 +1 -3 +1 -2 +1 -1 +1 0
Banana 1/7 0 +1 1 +1 2 +1 3 -6 -3 +1 -2 +1 -1 +1 0
Apple 2/7 0 +2 2 +2 4 -5 -1 +2 1 +2 3 -5 -2 +2 0
Pineapple 3/7 0 +3 3 -4 -1 +3 2 +3 5 -4 1 +3 4 -4 0
Selected item: Orange Pine Apple Banana Pine Apple Pine
这是 Python 中的一个实现:
items = ['Apple', 'Apple', 'Banana', 'Pineapple', 'Pineapple', 'Pineapple', 'Orange']
# Convert the list of items into a list that contains the [name, rate, accumulator]
# for each item. The initial value for the accumulator is 0
counts = {}
for item in items:
counts[item] = counts.get(item, 0) + 1
rates = counts.items()
rates = [[name, rate, 0] for (name, rate) in rates]
rates.sort(key=lambda x:x[1])
# Run the multiplexer, which
# adds the item with the largest accumulator to the output
# updates all the accumulators by adding the rate to the accumulator
# subtracts the period from the chosen accumlator
output = []
period = len(items)
for i in range(period):
best = 0
for j in range(len(rates)):
if rates[j][2] > rates[best][2]: # compare accumulators
best = j
rates[j][2] += rates[j][1] # update accumulator
rates[best][2] -= period
output.append(rates[best][0]) # add an item to the output
print output # ['Orange', 'Pineapple', 'Apple', 'Banana', 'Pineapple', 'Apple', 'Pineapple']