优先级队列的实现

anthony1983

想用STL来实现个优先级队列，STL中已经有了一个基于堆的priority_queue优先级队列， 但是如果priority_queue中已经有10W的消息， 我想根据某个条件，将其中满足需求的消息优先级提前（这种操作可能会比较频繁），priority_queue又显得不那么适用了， 所以我想用map来做这个优先级队列，这样对队列中消息的查找和删除都比较方便，请问哪个高手对这种优先级队列有什么研究没~小弟先谢过了·

peimichael

没研究过优先级队列，随便说说
不知道你所说的满足需求是什么样的需求，
个人认为如果这个需求是某个可计算的值的话，可以按这个值做一个哈希函数，
当需要把消息提前的时候只要把相应的那个链表提前就行了。

就好像内核中优先级调度使用140个优先级队列一样的那种。

alexhappy

我觉的这样还不如用几个优先级不同的队列

anthony1983

原帖由 alexhappy 于 2009-6-26 09:57 发表
我觉的这样还不如用几个优先级不同的队列

那遇到这种情况你怎么办，  比如
1.A1先进入了优先级低的队列Q1，未被执行
2.A2后进入了优先级高的队列Q2
3.由于Q2优先级高，最后处理的时候，A2就有可能先于A1被执行，但是逻辑上是需要保证A1执行后，A2才能执行的

alexhappy

什么意思？难道你不是相应优先级的消息进入相应优先级的队列的么？
为什么逻辑上要保证A2先于A1执行？既然这样，那岂不是A2高于A1？

xinglp

优先级别队列，难道不是多个普通队列构成的么？

while(1)
{
   处理队列(A);
   处理队列(B);
   处理队列(C);
   .....
}

anthony1983

原帖由 alexhappy 于 2009-6-26 11:43 发表
什么意思？难道你不是相应优先级的消息进入相应优先级的队列的么？
为什么逻辑上要保证A2先于A1执行？既然这样，那岂不是A2高于A1？

是的，比如客户做了一笔优先级低的业务A1， 然后又做了一笔优先级高的业务A2， 如果让A2先于A1执行话 ，会有逻辑错误的
原则上必须保证每个客户的业务是按时间流水被处理的。
所以目前只能 当有A2过来时，必须保证A1已经被做掉，如果A1还没有被处理，必须把A1的优先级提高，以便让A1被做掉，A2再被做掉

用多个优先级队列的话，只能这样做：从Q1中把A1删除，然后再把A1插到Q2中A2的前面。

从一个10W级的队列中 查找，然后在插入另外一个10W级的队列，这样的效率怎么保证呢

anthony1983

原帖由 xinglp 于 2009-6-26 11:52 发表
优先级别队列，难道不是多个普通队列构成的么？

while(1)
{
   处理队列(A);
   处理队列(B);
   处理队列(C);
   .....
}

是这样就简单了，你这种事静态的优先级， 关键是还要实现优先级的动态调整 ，说白了，就是随时从A中提一个消息出来，插到C的某一个位置

alexhappy

原则上必须保证每个客户的业务是按时间流水被处理的。

那么你让先做的一律成为高优先级不就完了？这样还用什么优先级队列啊。。。

[ 本帖最后由 alexhappy 于 2009-6-26 12:40 编辑 ]