4

着信クエリを受け入れて実行するサーバーアプリケーションがあります。クエリが多すぎる場合はキューに入れ、他のクエリの一部が実行された場合は、キューに入れられたクエリも実行する必要があります。異なる優先度のクエリを渡したいので、priority_queueを使用するのが最善の選択だと思います。

たとえば、受け入れているクエリの量（a）が限界に達し、新しいクエリがキューに保存されます。（a）からのクエリの一部が実行される場合、すべてのクエリの優先度は1（最低）になります。プログラムは、キューから最も優先度の高いクエリを選択して実行します。それでも問題ありません。現在、誰かがキューに追加される優先度5のクエリを送信しています。これは最も優先度の高いクエリであるため、実行中のクエリが制限に達しなくなるとすぐに、アプリケーションはこのクエリを実行します。優先度1の500個のクエリがキューに入れられても、誰かが常に優先度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の単純なキューを使用する方が理にかなっています（これは、一部のOSで優先プロセススケジューラが実装される方法です）。最初に、優先度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

ソート基準が変更された場合、 Astd::priority_queueはそれ自体を再編成する方法がありません。自分で管理する必要があります。

std::vectorそれを維持するために、2つのアプローチのうちの1つを使用することをお勧めします。

2つのケースがあります。要素を削除するよりも頻繁に優先順位を変更する場合（そうではないように聞こえます）、ソートせずに、min_elementを使用して、必要に応じて削除するアイテムを見つけます。

それ以外の場合は、Kristoのアプローチを使用して、独自のヒープを維持することをお勧めします。呼び出しの優先順位を変更するときはmake_heap、useを追加しpush_heap、最上位のアイテムのuseを取得しますpop_heap。

于 2010-05-27T13:36:55.003 に答える
0

優先度を変更する必要がある場合は、すべての要素にアクセスするためのインターフェイスがないため、priority_queueを使用できません。std::vectorとの方がいいですstd::make_heap。

于 2010-05-27T13:28:04.357 に答える
0

ACEフレームワークは、おそらくあなたを助けることができる何かを提供します。クラスACE_Dynamic_Message_QueueおよびACE_Laxity_Message_Strategyを参照してください。私はまだこの特定のクラスを扱ったことがないので、例をあげることはできませんでした。しかし、アイデアは次のとおりです。

  • 2つのスレッドで共有されるメッセージキューがあります
  • プロデューサースレッドでは、メッセージキューを埋めます
  • メッセージキューは、戦略に従って正しい場所に新しいメッセージを挿入します。
  • レシーバースレッドでは、キューから一番上のアイテムを読み取るだけです。
于 2010-05-27T13:54:24.840 に答える
0

std :: dequeを使用して、残りを自分でビルドします（C ++を使用していて、外部ライブラリが役に立たない場合）。make_heapの他の提案（std :: priority_queueが使用するもの）の問題は、それが安定していないことです。この場合の安定性の欠如は、優先順位の範囲内で注文が保証されておらず、飢餓が発生する可能性があることを意味します。

于 2010-05-27T13:55:56.820 に答える
0

まず、コードに関するいくつかのコメント：

  1. 演算子<が、削除するたびにオブジェクトごとに1回だけ呼び出されることを保証することはできません（topとpopの両方で、またはpushで、または...で呼び出すことができます）。
  2. キュー内のコピーではなく、演算子関数でローカルコピーの優先度を上げます
  3. ここで演算子を宣言するためにフレンド関数を使用する必要はありません<。

priority_queueを必要な特定のキューにオーバーライドする例を作成しました。ここから続行できることを願っています。動作は、Queryクラスではなく、キューに実装する必要があります。これは、この動作を可能にするために必要なアクセサーのみを提供する必要があります。Queryクラスは、キューに関する知識を持っていない必要があります。

基本的に、通常のキューのサイズと空をコピーし、クエリを挿入および取得するための2つの新しいメソッドを作成します（プッシュ、ポップ、およびトップは無効になっています）。ローカルコンテナでfor_each呼び出しを使用して、push呼び出しだけを挿入し、top呼び出し、pop呼び出しの両方を取得し、すべての優先度を更新します。最後に、機能を示す小さなプログラムが提供されます。

また、ポップアンドプッシュでのヒープ管理に基づいています。これは、すべての要素が線形に変化するため、私が知る限り正しく機能します。順序はプッシュ間で変化しません;）。

#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 に答える