동적 우선 순위가있는 priority_queue

Question

나는 incomming 쿼리를 받아들이고 실행하는 서버 응용 프로그램이 있습니다. 쿼리가 너무 많으면 대기열에 있어야하며 다른 쿼리가 실행되면 대기중인 쿼리도 실행해야합니다. 우선 순위가 다른 쿼리를 전달하고자하므로 priority_queue를 사용하는 것이 최선의 선택이라고 생각합니다.

axcepting 질의 (a)는 사기를 치고 새로운 질의는 큐에 저장 될 것이다. (a)의 쿼리가 실행되면 programm가 큐에서 가장 높은 우선 순위를 가진 쿼리를 선택하여 실행하는 경우 모든 쿼리의 우선 순위는 1 (최하위)입니다. 여전히 문제 없습니다. 이제 다른 사용자가 대기열에 추가되는 우선 순위가 5 인 쿼리를 보냅니다. 이것은 가장 높은 우선 순위를 갖는 쿼리이므로 실행중인 쿼리가 더 이상 한계에 도달하지 않으면 응용 프로그램은이 쿼리를 실행합니다. 최악의 경우 우선 순위가 1 인 500 개의 쿼리가 대기열에 있지만 실행되지 않을 수 있습니다. 누군가 우선 순위가 5 인 쿼리를 보내므로이 500 개의 쿼리는 대기 시간 동안 대기합니다. 우선 순위가 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 개의 간단한 큐를 갖는 것이 더 낫습니다 (우선 순위 프로세스 스케줄러가 일부 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 큐가 std :: list이고 list::splice() 인 경우 큐 25에 O (1)이됩니다.

Answer 2

을 수정해야하는 경우

는 정말 누군가가 나를 우선 순위 문제를 해결하는 데 도움이 될 수 있습니다 희망 모든 요소에 액세스 할 인터페이스가 없으므로 priority_queue를 사용할 수 없습니다. std::vector 및 std::make_heap을 사용하는 것이 좋습니다.

Answer 3

std::priority_queue에는 정렬 기준이 변경 될 경우 자체를 재구성 할 수있는 방법이 없습니다. 스스로 관리 할 수 ​​있습니다.

그냥 std::vector을 사용하고 두 가지 방법 중 하나를 사용하여 유지하는 것이 좋습니다.

두 가지 경우가 있습니다 : 요소를 제거하는 것보다 더 자주 우선 순위를 지정하는 경우 (해당하지 않는 것처럼 들리는) 요소는 정렬되지 않은 상태로 유지하고 min_element를 사용하여 제거 할 항목을 찾습니다.

그렇지 않으면 Kristo의 방법을 사용하고 자신의 힙을 유지하는 것이 좋습니다. 전화 번호 make_heap을 다시 프라이버시로 지정하고 push_heap을 추가하고 최상위 항목을 얻으려면 pop_heap을 사용하십시오.

Answer 4

ACE 프레임 워크는 아마도 도움이 될만한 것을 제공 할 것입니다. 클래스 ACE_Dynamic_Message_Queue 및 ACE_Laxity_Message_Strategy을 참조하십시오. 나는 아직이 특정 클래스들과 일 해본 적이 없기 때문에 예제를 줄 수는 없다. 는 그러나 아이디어는 다음과 같다 :

• 당신은 두 개의 스레드 생산자 스레드에서
• 공유하는 메시지 큐를 가지고, 당신은 메시지 큐가 올바른 위치에서 새 메시지를 삽입합니다
• 메시지 큐를 채우기 전략에 따르면.
• 수신자 스레드에서 대기열의 맨 위 항목을 읽었을뿐입니다.

Answer 5

나는 std :: deque와 함께 가고 나머지는 스스로 구축한다. (만약 도움이 될만한 외부 라이브러리없이 C++을 사용한다면). make_heap의 다른 제안 (std :: priority_queue가 사용하는 것)의 문제점은 안정적이지 않다는 것입니다. 이 경우의 안정성 부족은 우선 순위 내에서 주문이 보장되지 않고 기아가 발생할 수 있음을 의미합니다. 코드에 대한 모든 몇 가지 코멘트

Answer 6

첫째 : 당신은 각각 < 한 번만 호출 할 것이다 연산자를 보장 할 수 없습니다

1. 모든 제거를 객체 (이 상단과 팝에서 모두 호출 할 수 있습니다, 또는 푸시에, 또는 ...).
2. 대기열의 복사본이 아닌 연산자 기능에서 로컬 복사본의 우선 순위를 높입니다.
3. 여기서 friend 함수를 사용하여 연산자 <을 선언 할 필요가 없습니다.

내가 원하는 특정 대기열에 우선 순위 대기열을 덮어 쓰는 예제를 작성했습니다. 여기서 계속 할 수 있기를 바랍니다. 비헤이비어는 Query 클래스가 아닌 대기열에 구현되어야하며,이 동작을 수행하는 데 필요한 접근 자만 제공해야합니다. Query 클래스는 Queue에 대한 지식이 없어야합니다.

기본적으로 일반 큐의 크기와 빈을 복사하고 쿼리를 삽입하고 가져 오는 두 가지 새로운 메서드를 만듭니다 (푸시, 팝 및 맨 위를 사용할 수 없습니다). Insert는 push를 호출하고, 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; 
}