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