关键词：
【中文标题】如何避免优先级队列中的饥饿【英文标题】：How to avoid starvation in a priority queue 【发布时间】：2018-08-24 23:40:47 【问题描述】：我正在尝试创建一个队列，以避免队列中的元素时间过长。我正在使用链接列表。我想要实现它的方式是，如果添加更高的优先级，则被推送的优先级会添加 0.4。我还需要为链表实现排序，但这已经很有意义了。我真的不明白我应该如何将这个 0.4 添加到已被取代的优先级中。
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class LinkedList:
def __init__(self,):
self.head = Node()
def append(self, data):
new_node = Node(data)
current = self.head
while current.next is not None:
current = current.next
current.next = new_node
def __str__(self):
data = []
current = self.head
while current is not None:
data.append(current.data)
current = current.next
return "[%s]" %(', '.join(str(i) for i in data))
def __repr__(self):
return self.__str__()
def length(self):
current = self.head
total = 0
while current.next is not None:
total += 1
current = current.next
return total
def display(self):
elements = []
current_node = self.head
while current_node.next is not None:
current_node = current_node.next
elements.append(current_node.data)
print("Elements ", elements)
def get(self, index):
if index >= self.length():
print("Error: Index is out of range!")
return None
current_index = 0
current_node = self.head
while True:
current_node = current_node.next
if current_index == index:
return current_node.data
current_index += 1
def remove(self):
current = self.head
if current is not None:
self.head = current.next
else:
print("Queue is empty!")
def main():
queue = LinkedList()
queue.append(5)
queue.append(2)
queue.display()
main()
【问题讨论】：
编写一个函数，将其命名为get_true_priority(base_priority, age)，这样它就会产生“避免饥饿”的有用输出（可能还有一些其他规则应该遵守，例如单调的年龄？）。这个函数可以绘制在图表上，我可能会首先绘制我“预期”它如何工作的图表，然后将其返回到代码中。
你不需要链表，Python list 就可以了。您的班级需要 2 个结构：一个按当前优先级对项目进行排序或堆积，另一个 - 按剩余时间“直到添加另一个 0.4”。更新优先级得到更新的项目的列表位置。
【参考方案1】：
我建议使用 python 的heapq 而不是链表。因为您正在进行自定义比较，所以您可能希望实现类似于heapq with custom compare predicate 中描述的内容。
除了优先级之外，添加一个包含项目添加到堆中的时间的字段。然后，您的实际优先级是分配的优先级和项目在堆中的时间长度的函数。例如，优先级可能是这样的：
elapsed_time = current_time - added_time;
real_priority = assigned_priority * elapsed_time;
您可能希望将乘数设为已用时间的一小部分。
另一种可能性是，如果您想确保某些东西在队列中的停留时间不会超过某个设定的时间。例如，如果您想确保事情不会停留超过 5 分钟，您可以添加 dequeue_time 字段。然后你的比较变成这样：
// assume items a and b are being compared
if (a.dequeue_time < current_time)
if (b.dequeue_time < a.dequeue_time)
// b sorts before a
else if (b.dequeue_time > a.dequeue_time)
// return a sorts before b
else // dequeue times are equal
return result of comparing a.priority to b.priority
else
// here, return result of comparing a.priority and b.priority
heapq 将比您的链表更有效，尤其是当您的队列中的项目数量增加时。另外，它已经被编写并且已知工作。只需提供比较功能即可。
【讨论】：
五种进程调度算法的总结;
...度，优点是公平，实现简单；缺点是不利于短作业。3、优先级调度算法（HPF）：在进程等待队列中选择优先级最高的来执行。4、多级反馈队列调度算法：将时间片轮转与优先级调度相结合，把进程按优先级分成不同的队列，先... 查看详情
使用最小优先级队列时，如何跟踪 Dijkstra 算法中的最短路径？
】使用最小优先级队列时，如何跟踪Dijkstra算法中的最短路径？【英文标题】：HowdoIkeeptrackoftheshortestpathsintheDijkstraalgorithmwhenusingamin-priorityqueue?【发布时间】：2019-10-2917:49:18【问题描述】：我正在尝试使用优先级队列实现Dijkstra算... 查看详情
如何将排序应用于 Scala 优先级队列？
】如何将排序应用于Scala优先级队列？【英文标题】：HowtoapplyorderingtoaScalaPriorityQueue?【发布时间】：2015-06-1713:27:32【问题描述】：我已经像这样定义了一个优先级队列importscala.collection.mutable.PriorityQueue...valqueue=newPriorityQueue[(Int,Int... 查看详情
如何生成随机数并将它们插入优先级队列？
】如何生成随机数并将它们插入优先级队列？【英文标题】：HowdoIgeneraterandomnumbersandinsertthemtoapriorityqueue?【发布时间】：2019-04-0708:26:17【问题描述】：我已经使用具有所需功能的SLList实现了PriorityQueue。我想生成100个随机整数并... 查看详情
如何对不同队列上的消息进行优先级排序？
】如何对不同队列上的消息进行优先级排序？【英文标题】：HowcanIprioritizemessagesondifferentqueues?【发布时间】：2012-02-0618:52:28【问题描述】：资源分配/优先级问题。我正在开发一个JavaEE应用程序，该应用程序有许多消息驱动Bean(MD... 查看详情
008优先级和饥饿问题
一.概述在上面我们说到由于线程的优先级的设置不当,造成了线程运行的程度会不同, 最终会有一些线程很难得到运行的机会. 一般操作系统是使用时间片轮转的方式进行线程的优先级的改变. 二.动态优先级现代操作系... 查看详情
将自定义比较器传递到 Cython 中的优先级队列
】将自定义比较器传递到Cython中的优先级队列【英文标题】：PassacustomcomparertoapriorityqueueinCython【发布时间】：2018-01-2711:57:10【问题描述】：Cythonlibcpp模块包含priority_queue的模板，这很棒，除了一件事：我无法将自定义比较器传递... 查看详情
如何在 C++ 中正确使用优先级队列
】如何在C++中正确使用优先级队列【英文标题】：HowtoproperlyusepriorityqueuesinC++【发布时间】：2014-11-1504:16:35【问题描述】：对于我的数据结构类中的分配，我想为所谓的背包问题实现分支定界方法。问题本身不是问题，但如果您... 查看详情
从线程的优先级看饥饿问题
饥饿与公平：1.高优先级吞噬所有低优先级的CPU时间片2.线程被永久堵塞在一个等待进入同步块的状态3.等待的线程永远不被唤醒 关于优先级，编程的时候注意：不要假定高优先级的线程一定先于低优先级的线程，不要有逻辑... 查看详情
SQL 中的优先级队列
】SQL中的优先级队列【英文标题】：PriorityqueueinSQL【发布时间】：2013-05-2100:53:11【问题描述】：我正在实施一个具有多个优先级的排队系统。我想要一个查询，它可以返回X行，每个优先级至少Y行。例如：假设队列有3个优先级（... 查看详情
优先级队列中的不同元素
】优先级队列中的不同元素【英文标题】：Distinctelementsinpriorityqueue【发布时间】：2019-03-1007:46:44【问题描述】：我正在使用这个有界优先级队列的实现，https://gist.github.com/ryanlecompte/5746241，它运行良好。但是，我希望这个队列不... 查看详情
与java中的优先级队列混淆
】与java中的优先级队列混淆【英文标题】：confusionwithpriorityqueueinjava【发布时间】：2016-08-2109:11:52【问题描述】：我有一些要放入优先级队列的数组索引。现在我想使用一个比较器，它应该将这个索引与同一类中的另一个数组进... 查看详情
网络编程——同一进程中的队列（多线程）
...queue.Queue()先进先出queue.LifoQueue()后进先出queue.PriorityQueue()优先级队列 优先级队列q=queue.PriorityQueue() q.put()接受的是一个元祖 元祖中第一个参数是：表示当前数据的优先级 元祖中第二个参数是：需要存... 查看详情
java示例代码_删除优先级队列中的特定元素
java示例代码_删除优先级队列中的特定元素 查看详情
SQL Server 中的优先级队列
】SQLServer中的优先级队列【英文标题】：PriorityqueueinSQLServer【发布时间】：2016-11-2911:13:45【问题描述】：我目前正在使用C#构建网络爬虫。要将尚未抓取的URL排队，我使用SQLServer。它运行得非常快，但随着时间的推移它开始变得... 查看详情
swift中的优先队列
...到尾的最短路线。不幸的是，我似乎找不到swift提供一种优先级队列的库或其他方式，所以看来我必须自己编写代码。话虽如此，任何人都可以为我指出正确的方向吗？目前我的想法如下：编写一个保存优先级数组的类。在这个... 查看详情
JavaScript 中的优先级队列，我无法添加多个节点
】JavaScript中的优先级队列，我无法添加多个节点【英文标题】：PriorityQueueinJavaScript,Iamnotabletoaddmorethanonenode【发布时间】：2021-09-2217:54:35【问题描述】：classPriorityQueueconstructor()this.values=[]enqueue(value,priority)if(this.values.length===0)thi 查看详情
通用优先级队列中的协变和逆变类型
】通用优先级队列中的协变和逆变类型【英文标题】：Co-andcontravarianttypesingenericpriorityqueue【发布时间】：2010-07-3017:10:01【问题描述】：我正在尝试在Scala中实现一个在类型T上参数化的通用数据类型，它应该是Ordered[T]。具体来说... 查看详情