c++ - 具有动态优先级的 priority_queue

Question

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

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

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

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

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;
};

Answer 1

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

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