具有动态优先级的priority_queue

Question

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

例如，接受查询的数量 (a) 达到限制，新的查询将存储在队列中。所有查询的优先级均为 1（最低），如果 (a) 中的某些查询得到执行，程序将从队列中选择具有最高优先级的查询并执行它。还是没问题。现在有人正在发送优先级为 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 向上移动到队列 #25如果队列是 std::list 的并且使用 list::splice() ，则为 O(1)。

Answer 2

如果排序条件发生变化，std::priority_queue 无法重新组织自身。您需要自己管理。

我建议只使用 std::vector 和两种方法之一来维护它。

有两种情况：如果您重新确定优先级的频率比删除元素的频率高（听起来并非如此），则只需保持其未排序并使用 min_element 来查找需要时要删除的项目。

否则，更好的方法可能是使用 Kristo 的方法并维护自己的堆。当您重新调整调用make_heap的优先级时，要添加使用push_heap，并使用pop_heap获取顶部项目。

Answer 3

如果您需要修改优先级，则不能使用priority_queue，因为没有接口可以访问所有元素。您最好使用 std::vector 和 std::make_heap。

Answer 4

ACE 框架可能会提供一些可以帮助您的东西。请参阅类 ACE_Dynamic_Message_Queue 和 ACE_Laxity_Message_Strategy。
我还没有使用过这个特定的类，所以我无法给你一个例子。
但思路是这样的：

• 你有一个由两个线程共享的消息队列，
• 在生产者线程中，你填充消息队列，
• 消息队列会根据策略在正确的位置插入新消息。
• 在接收器线程中，您只需从队列中读取最上面的项目。

Answer 5

首先对您的代码进行一些评论：

1. 您不能保证运算符 <每次删除时每个对象只会被调用一次（它可以在顶部和弹出时调用，或者在推送时调用，或者......）。
2. 您增加了运算符函数中本地副本的优先级，而不是队列中的副本
3. 。此处无需使用友元函数来声明运算符<。

我写了一个示例，将priority_queue覆盖为您想要的特定队列，我希望您可以从这里继续。该行为应该在队列中实现，而不是在 Query 类中实现，这只应该提供必要的访问器来允许该行为。查询类不应该了解队列。

基本上它复制了普通队列的大小和空，并创建了 2 个新方法来插入和获取查询（push、pop 和 top 被禁用）。 Insert 仅调用push，get 调用top、pop 并使用本地容器上的for_each 调用更新所有优先级。最后提供了一个显示功能的小程序。

此外，它基于弹出和推送中的堆管理。据我所知，由于每个元素的线性变化，这将正确工作，推送之间的顺序不会改变；）。

#include <algorithm>
#include <queue>
#include <iostream>

class Query
{
public:
    Query( std::string p_stQuery, double priority = 1.0) : stQuery( p_stQuery ) , fPriority(priority), fStartPriority(priority) {};
    std::string getQuery() const
    {
        return stQuery;
    };
    void conditionalIncrease( const Query& otherQuery )
    {
        if (fStartPriority < otherQuery.fStartPriority) fPriority += INCREASE_RATE;
    }

    bool operator < ( const Query& rhs )  const
    {
        return fPriority < rhs.fPriority;
    }

    double getPriority() const
    {
        return fPriority;
    }
private:
    static const double INCREASE_RATE = 0.2;
    double fPriority; // current priority
    double fStartPriority; // initialised priority
    std::string stQuery;
};

class QueryIncreaser
{
private:
    Query base;
public:
    QueryIncreaser(const Query& q) : base(q) {}
    void operator() (Query& q)
    {
        q.conditionalIncrease(base);
    }
};

class QueryQueue : private std::priority_queue<Query>
{
public:
    void insertQuery(const Query& q)
    {
        push(q);
    }
    Query getQuery()
    {
        Query q = top();
        pop();
        QueryIncreaser comp(q);
        for_each(c.begin(), c.end(), comp);
        return q;
    }
    bool empty() const
    {
        return std::priority_queue<Query>::empty();
    }
    size_t size() const
    {
        return std::priority_queue<Query>::size();
    }
};

int main ()
{
    Query a("hello"), b("world",2.);
    QueryQueue myQueue;
    myQueue.insertQuery(a);
    myQueue.insertQuery(b);
    while (!myQueue.empty())
    {
        std::cout << myQueue.getQuery().getPriority() << std::endl;
    }
    return 0;
}

Answer 6

我会使用 std::deque 并自己构建其余部分（如果您只是使用 C++，没有可能有帮助的外部库）。 make_heap（std::priority_queue 使用的）的其他建议的问题是它不稳定。在这种情况下缺乏稳定性意味着优先级内的排序得不到保证，并且可能出现饥饿。