[help]优先级队列的问题

BlackSnail

我需要实现这样一个系统：
系统中有多个队列，每个队列有不同的优先级。
多个接收线程，将从各个A类客户端收到的消息按不同的优先级放到不同的接收队列中。
发送线程（一个或多个），用于将接收队列中的消息按优先级从高到低发送到B类客户端。

但是我不知道应该采用什么样的算法来寻找优先级高的消息。开始想的是用一个线程轮询所有的接收队列来检出优先级高的消息，但是又担心这样效率低。如果为每个队列分配一个线程，是否效率要好点儿呢？还有其它优先级算法吗？

另外，假如有10个优先级队列，但是进入各个优先级队列的消息数量并不均衡，比如90％的消息都进入优先级0的队列，其它10％消息进入其它9个队列。那么应该如何分配队列大小呢？是将优先级0的队列大小分配为其它队列大小的9倍？还是多产生9个优先级均为0的队列，队列大小均一致？或者还有别的更好的方式？

谢谢各位指教。

zxh5187406

为什么要用多个队列?

mq110

你可以自己定 谁有限级高啊.
我昏.

wxp19831104

新手上路，随便谈谈看法，老大们别笑。

搞一个队列就行了，队列是list型的，搞一个指针数组指向每一级别消息的最后一个指针，是那个级别的消息就直接加到那个级别的指针后。

只是个想法，还有很多读写操作的细节，改指针，要完善。

BlackSnail

谢谢各位的回复。

[quote]原帖由 "zxh5187406"]为什么要用多个队列?[/quote 发表：

我开始想的是将不同优先级的报文放到不同优先级的队列里。您的意思是指象wxp19831104一样，用一个链表来存放所有的报文，有几个不同的指针指向链表中不同的优先级开始的地方，是吗？

[quote]原帖由 "mq110"]你可以自己定 谁优先级高啊.[/quote 发表：

是可以自己定义哪个队列优先级高，但是我不知道如何效率高地从优先级高到优先级低读取报文，假如已经把高优先级的报文取光了，正在取中优先级报文时又有高优先级报文到来，怎么监控到？我担心轮询的效率比较低。听说java中可以通过线程阻塞来自动监控各个队列里是否有新报文到来（每个队列都有一个线程用于读取队列里的数据），C/C++中的线程可以吗？

[quote]原帖由 "wxp19831104"]搞一个队列就行了，队列是list型的，搞一个指针数组指向每一级别消息的最后一个指针，是那个级别的消息就直接加到那个级别的指针后。 只是个想法，还有很多读写操作的细节，改指针，要完善。[/quote 发表：

您说的这个办法的确很巧妙，队列大小可以动态变化。我会认真考虑一下这个作法。

由于我现在在做的这个项目涉及到大流量的报文（每个报文可能只有1K左右字节，但是可能一下子接收到几百万、上千万条报文）接收和发送，所以希望有类似经验的朋友提供一些注意事项，非常感谢。

assiss

一下子收到几百万条？一条1K？你的网卡是1000,000Mbps的？

BlackSnail

[quote]原帖由 "assiss"]一下子收到几百万条？一条1K？你的网卡是1000,000Mbps的？[/quote 发表：


可能我表述得有问题，不是说1秒钟收几百万条。我的意思是A类客户端可能会一下子发几百万条过来，至于A类客户端实际发完这些数据要多久不考虑，反正意思就是有大流量过来。

zxh5187406

= =杀...用优先树....二分搜索...LIST什么效率...

zxh5187406

用可并优先树...拓展性强...刚好符合你这种情况...

BlackSnail

基本google不到“可并优先树”、“可并优先队列”，搜索出来的都是数据结构书的目录。哪位给我一些可并优先树的电子文档啊，哪怕告诉我其可并优先树的英文名也好啊。

谢谢