algorithm - 优先处理不同类型的消息
问题描述
我有t
不同的消息类型,可以在不同的时间到达队列q
。在特定时间到达的消息数量可能会有所不同。每种类型都有一些优先级。
我需要编写一个算法,该算法将使用以下规则在优先级队列中对该消息进行排序:
- 组织消息,使 t 的更高优先级是队列中的第一条消息。
- 除了优先级,我们还需要考虑较低优先级的消息仍然需要以一定百分比出现在队列中(例如,每 10 条消息将是优先级 2 的消息,每 100 条消息将具有优先级 3 等) .
- 如果队列头部已经有较低优先级的消息,则应在到达的消息之前具有较高的优先级
- 如果队列头部已经有优先级较低的消息,并且我们没有收到更高优先级的消息。消息 - 从队列中获取时,我们首先获取优先级较低的消息
示例 1:
- t1 - 优先级 1(在 8 中显示 5)
- t2 - 优先级 2(在 8 中显示 2)
- t3 - 优先级 3(在 8 中显示 1)
此队列的可能状态(前 8 条消息)
q = t1,t1,t2,t1,t1,t2,t1,t3
示例 2:
在 5t2
条消息到达一个空队列后,我有:
q = t2,t2,t2,t2,t2
现在如果有 10t1
条消息到达,我需要以下分布:
q = t1,t1,t2,t1,t1,t2,t1,t1,t2,t1,t1,t2,t1,t1,t2
是否已经有一些算法可以实现此功能?
解决方案
我的想法是为每个优先级保留三个不同的队列。维护每个队列中的消息数。
让 ratio1 = c1 / (c1 + c2 + c3)。在您的示例中,c1、c2、c3 分别为 5、2、1。
从第一个队列中挑选 (n1 * ratio1) 条消息,然后从第二个队列中挑选 (n2 * ratio2) 条消息,依此类推。n1、n2、n3 分别是当前队列 1、2、3 中的消息数。
我解释了我的总体想法。您可以将其扩展到任意数量的队列。
我想将上述方案命名为基于优先级的循环算法。我搜索了这个名字,我也找到了一篇相关的文章。希望能帮助到你。