对不同类型的消息进行排序
对不同类型的消息进行排序
提问于 2021-01-27 15:22:31
我有不同的t消息类型，它们可以在不同的时间到达队列q。到达特定时间的消息数量可能会有所不同。每种类型都有一定的优先权。
我需要编写一个算法，按照以下规则将这些消息排序在优先级队列中：
- 组织消息，所以t的高优先级是队列中的第一条消息。
- 除了优先级之外，我们还需要考虑到优先级较低的消息仍然需要以一定的百分比出现在队列中(例如，每10条消息中就有一条消息具有优先级2，而每100条消息中有一条优先级为3)。
- 如果队列头上已经有优先级较低的消息，则应在到达时出现更高的优先级。
- 如果队列头上已经有优先级较低的消息，并且我们没有收到更高优先级的消息。消息-当从队列中获取消息时，我们首先接收优先级较低的消息。
Example1：
- t1 -优先级1(在8中显示5)
- t2 -优先级2(在8中显示2)
- t3 -优先级3(显示1/ 8)
此队列的可能状态(前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
是否已经有实现此功能的算法？
回答 1
Stack Overflow用户
回答已采纳
发布于 2021-01-27 16:16:14
我的想法是为每个优先级保留三个不同的队列。维护每个队列中数量消息的计数。
设ratio1 = c1 / (c1 + c2 + c3)。在您的示例中，c1、c2、c3分别为5、2、1。
从第一个队列中选择(n1 * ratio1)消息，然后从第二个队列中选择(n2 * ratio2)消息，等等。n1、n2、n3分别是队列1、2、3中的消息数。
我解释了我的总体想法。您可以将其扩展到任意数量的队列。
我认为将上述方案命名为基于优先级的Robin算法。我搜索了这个名字，也找到了找到一篇相关文章。希望能帮上忙。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/65922143
复制相关文章
相似问题
腾讯云开发者
