具有动态优先级的priority_queue [英] priority_queue with dynamic priorities

问题描述

我有一个服务器应用程序，它接受传入的查询并执行它们.如果有太多的查询，他们应该排队，如果其他一些查询被执行，排队的查询也应该被执行.由于我想传递具有不同优先级的查询，因此我认为使用 priority_queue 将是最佳选择.

I have a server application which accepts incomming queries and executes them. If there are too many queries they should be queued and if some of the other queries got executed the queued queries should be executed as well. Since I want to pass queries with different priorities I think using a priority_queue would be the best choice.

例如接受查询的数量 (a) 达到限制，新查询将存储在队列中.如果来自 (a) 的某些查询被执行，所有查询的优先级为 1(最低)，则程序将从队列中挑选具有最高优先级的查询并执行它.还是没有问题.现在有人正在发送一个优先级为 5 的查询，该查询被添加到队列中.由于这是具有最高优先级的查询，一旦正在运行的查询不再达到限制，应用程序就会执行此查询.最坏的情况可能是 500 个优先级为 1 的查询排队但不会被执行，因为有人总是发送优先级为 5 的查询，因此这 500 个查询将排队等待很长时间.为了防止我想增加所有优先级低于优先级查询的优先级，在这个例子中优先级低于 5.所以如果优先级为 5 的查询被拉出队列中所有其他优先级<5 应增加 0.2.这样，即使可能有 100 个具有更高优先级的查询，具有低优先级的查询也不会永远排队.

e.g. The amout of the axcepting queries (a) hit the limt and new queries will be stored in the queue. All queries have a priority of 1 (lowest) if some of the queries from (a) get executed the programm will pick the query with the highest priority out of the queue and execute it. Still no problem. Now someone is sending a query with a priority of 5 which gets added to the queue. Since this is the query with the highest priority the application will execute this query as soon as the running queries no longer hit the limit. There might be the worst case that 500 queries with a priority of 1 are queued but wont be executed since someone is always sending queries with a priority of 5 hence these 500 queries will be queued for a looooong time. In order to prevent that I want to increase the prioritiy of all queries which have a lower priority than the query with the higher priority, in this example which have a priority lower than 5. So if the query with a priority of 5 gets pulled out of the queue all other queries with a priority < 5 should be increased by 0.2. This way queries with a low priority wont be queued for ever even if there might be 100 queries with a higher priority.

我真的希望有人能帮我解决优先级的问题:

I really hope someone can help me to solve the problem with the priorities:

由于我的查询由一个对象组成，我认为这样的事情可能会起作用:

Since my queries consist of an object I thought something like this might work:

class Query {
public:
    Query( std::string p_stQuery ) : stQuery( p_stQuery ) {};
    std::string getQuery() const {return stQuery;};
    void increasePriority( const float fIncrease ) {fPriority += fIncrease;};

    friend bool operator < ( const Query& PriorityFirst, const Query& PriorityNext ) {
        if( PriorityFirst.fPriority < PriorityNext.fPriority ) {
            if( PriorityFirst.fStartPriority < PriorityNext.fStartPriority ) {
                Query qTemp = PriorityFirst;
                qTemp.increasePriority( INCREASE_RATE );
            }

            return true;
        } else {
            return false;
        }
    };

private:
    static const float INCREASE_RATE = 0.2;
    float fPriority; // current priority
    float fStartPriority; // initialised priority
    std::string stQuery;
};

推荐答案

您想要实现多少个离散的优先级值?如果它们的数量很小(比如 256 个级别)，那么拥有 256 个简单队列而不是单个优先级队列更有意义(这是在某些操作系统中实现优先级进程调度程序的方式).最初，您以优先级 1 发送的事件放置在队列 #1 中.然后有人发送一个 prio=25 事件，并将它放在队列 #25 中.读取器从最高的非空队列(在本例中为 #25)读取事件，并将所有 25 岁以下的非空队列上的事件向上移动一个槽(整个队列 #1 移动到队列 #2，等等).我很确定这一切都可以在 O(k) 中完成(其中 k 是优先级的数量)，无论是使用 std::move 还是使用 std::swap 或使用 list::splice.

How many discrete priority values do you want to implement? If their number is small (say, 256 levels), then instead of a single priority queue it makes more sense to have 256 simple queues (this is how priority process schedulers are implemented in some OSes). Initially your events sent with priority 1 are placed on queue #1. Then someone sends a prio=25 event, and it is placed on queue #25. The reader reads the event from the highest non-empty queue (in this case #25) and the events on all non-empty queues under 25 are moved up a slot (the entire queue #1 is moved to queue #2, etc). I am pretty sure this could all be done in O(k) (where k is the number of priority levels), either with std::move or with std::swap or with list::splice.

将队列 #1 移动到队列 #2 先前占据的位置应该是 O(1) 使用移动或交换，如果队列的剩余部分 prio=25 不为空，则将所有元素从队列 #24 向上移动到如果队列是 std::list 并且使用了 list::splice()，则队列 #25 是 O(1).

Moving queue #1 to the position earlier taken by queue #2 should be O(1) with move or swap, and if the remainder of prio=25 queue is not empty, then moving all elements up from queue #24 into queue #25 is O(1) if the queues are std::list's and list::splice() is used.

这篇关于具有动态优先级的priority_queue的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！