4

我有一个接受传入查询并执行它们的服务器应用程序。如果查询太多，则应将它们排队，并且如果执行了其他一些查询，则也应执行排队的查询。由于我想传递具有不同优先级的查询，我认为使用 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;
};
4

6 回答 6

3

您要实现多少个离散优先级值？如果它们的数量很小（例如，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)。

于 2010-05-27T14:40:08.850 回答
1

如果您的排序标准发生变化， A 将std::priority_queue无法重新组织自己。你需要自己管理它。

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

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

否则可能更好的是使用 Kristo 的方法并维护自己的堆。当您重新确定呼叫的优先级时make_heap，添加使用push_heap并获得最重要的项目使用pop_heap。

于 2010-05-27T13:36:55.003 回答
0

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

于 2010-05-27T13:28:04.357 回答
0

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

  • 您有一个由两个线程共享的消息队列
  • 在生产者线程中，您填充消息队列
  • 消息队列会根据策略在正确的位置插入新消息。
  • 在接收器线程中，您只需从队列中读取最顶层的项目。
于 2010-05-27T13:54:24.840 回答
0

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

于 2010-05-27T13:55:56.820 回答
0

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

  1. 您不能保证每次删除时每个对象只会调用一次 operator <（它可以在 top 和 pop 时调用，或者在 push 时调用，或者...）。
  2. 您在操作员函数中增加本地副本的优先级，而不是队列中的副本
  3. 这里不需要使用友元函数来声明运算符<。

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

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

此外，它是基于堆管理的pop 和push。据我所知，这将正常工作，因为每个元素的线性变化，推送之间的顺序不会改变；）。

#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;
}
于 2010-05-27T14:00:23.410 回答