11.1 priority_queue 데이터 추상(data abstraction)
priority queue는 값들의 콜렉션으로부터 가장 큰 값을 신속하게 찾거나 제거할 필요가 빈번하게 발생하는 상황에서 유용하게 사용할 수 있다. 일상에서 찾아볼 수 있는 priority queue의 예로 아직 처리되지 않은 일들의 목록을 들 수 있다. '책상 정리'와 같은 일들은 그리 긴박한 사항이 아니므로, 임의로 연기할 수 있지만, '월요일까지 보고서 마치기'나 '기념일을 위한 꽃사기'와 같은 작업은 시간이 중요하므로 가장 급히 해결해야할 일들이다. 따라서, 중요도에 따라 수행할 작업들을 정리하고, 가장 급박한 것을 골라 수행한다.
A Queue That is Not a Queue
A Queue That is Not a Queue
컴퓨터와 관련된 예로는 대기 프로세스의 리스트를 유지하는 운영체제에서 살펴볼 수 있다. 여기서 각 원소와 연결된 값은 작업의 우선순위이다. priority queue에 프로세스들을 유지함으로써, 높은 순위를 가지는 작업들은 낮은 순위의 작업들보다 우선적으로 실행한다.
시뮬레이션 프로그램들은 앞으로 발생할 사건(event)들의 priority queue를 사용한다. 시뮬레이션은 가상 '시계'를 유지하고, 각각의 사건(event)은 사건이 일어날 시간을 가지고 있다. 이렇게 사건들의 집합에서 가장 작은 시간값을 가지는 원소가 다음에 시뮬레이션될 원소이다. 이들외에도 priority queue가 사용되는 예는 많이 있다.
11.1.1 Include 화일
priority queue를 사용하는 프로그램은 컨테이너 타입(예를 들어 vector)에 대한 헤더화일과 queue 헤더 화일을 포함시켜야 한다.
#include <queue> #include <vector>
11.2 priority_queue 연산
priority queue는 T 타입의 원소를 가지고, 다음 5가지의 연산을 구현하는 데이터 구조이다.
| push(T) | 컨테이너에 새로운 값을 추가 |
| top() | 컬렉션내의 가장 작은 원소의 레퍼런스를 리턴 |
| pop() | 컬렉션에서 가장 작은 원소를 삭제 |
| size() | 컬렉션내에 포함된 원소들의 수를 리턴 |
| empty() | 컬렉션의 empty이면 true를 리턴 |
디폴트 less-than(<) 연산자를 사용하든, 템플릿 인자나 생성자의 인자로 지정한 비교 함수를 사용하든지간에, T 타입의 원소들은 서로 비교가 가능해야 한다. 두번째 형태는 나중에 뒤에서 설명할 예제 프로그램에서 설명하기로 한다. 표준 라이브러리의 다른 컨테이너와 마찬가지로, priority_queue에도 두개의 생성자가 있다. 기본 생성자는 인자없이 또는 생략가능한 비교연산자가 있으면 된다. 또다른 생성자는 한쌍의 반복자를 취하여 다른 컨테이너의 값들로 초기화한다. 여기서도, 생략가능한 세번째 인자로 비교함수를 사용한다.
priority queue 데이터 타입은 컨테니어 클래스를 바탕으로 구성되며, 이 컨테이너가 실제로 priority queue의 값들을 담게 된다. priority_queue를 구성하는데 사용되는 컨테이너는 vector와 deque가 있다.
11.2.1 priority_queue의 선언과 초기화
다음은 여러가지 priority_queue를 선언하는 예이다.
priority_queue< int, vector<int> > queue_one; priority_queue< int, vector<int>, greater<int> > queue_two; priority_queue< double, deque<double> > queue_three(aList.begin(), aList.end()); priority_queue< eventStruct, vector<eventStruct> > queue_four(eventComparison); priority_queue< eventStruct, deque<eventStruct> > queue_five(aVector.begin(), aVector.end(), eventComparison);
vector로 구축된 queue는 좀 더 작은 반면, 만약 수행중에 queue내의 원소의 갯수가 큰폭으로 변하는 경우에는 deque로 구축된 queue가 좀 더 빨라진다. 그러나, 이들간의 차이는 경미하며, 어느 형태든 대부분의 상황에서 잘 작동한다.
priority queue 데이터 구조는 반복자를 만들 줄 모르기 때문에, 13장에서 설명하는 알고리듬의 일부만이 priority queue와 같이 사용될 수 있다. 값들을 반복하는 대신에, priority queue를 사용하는 전형적인 알고리듬은 콜렉션이 빌때까지(empty()를 사용하여 검사) 데이터 구조로부터 값들을 반복적으로 끌어내는 (top()과 pop() 연산을 사용) 루프를 구성한다. 다음 절의 예제 프로그램에서 이의 사용에 관해 설명할 것이다.
priority_queue는 내부적으로 heap이라고 불리는 자료구조를 만들어 구현하며, 개념적으로 봤을 때 heap은 각 노드의 값이 자식 노드들의 값보다 작거나 같은 속성을 가지는 이진 트리이다.
11.3 응용 - Event-Driven 시뮬레이션
An extended example will illustrate the use of priority queues. The example illustrates one of the more common uses for priority queues, which is to support the construction of a simulation model.
A discrete event-driven simulation is a popular simulation technique. Objects in the simulation model objects in the real world, and are programmed to react as much as possible as the real objects would react. A priority queue is used to store a representation of "events" that are waiting to happen. This queue is stored in order, based on the time the event should occur, so the smallest element will always be the next event to be modeled. As an event occurs, it can spawn other events. These subsequent events are placed into the queue as well. Execution continues until all events have been processed.
Finding Smallest Elements
Finding Smallest Elements
Events can be represented as subclasses of a base class, which we will call event. The base class simply records the time at which the event will take place. A pure virtual function named processEvent will be invoked to execute the event.
class event {
public:
event (unsigned int t) : time(t) { }
const unsigned int time;
virtual void processEvent() = 0;
};
The simulation queue will need to maintain a collection of different types of events. Each different form of event will be represented by a different subclass of class event. Not all events will have the same exact type, although they will all be subclasses of class event. (This is sometimes called a heterogeneous collection.) For this reason the collection must store pointers to events, instead of the events themselves. (In theory one could store references, instead of pointers, however the standard library containers cannot hold references).
Since comparison of pointers cannot be specialized on the basis of the pointer types, we must instead define a new comparison function for pointers to events. In the standard library this is accomplished by defining a new structure, the sole purpose of which is to define the function invocation operator (the () operator) in the appropriate fashion. Since in this particular example we wish to use the priority queue to return the smallest element each time, rather than the largest, the order of the comparison is reversed, as follows:
struct eventComparison {
bool operator () (event * left, event * right) const
{ return left->time > right->time; }
};
We are now ready to define the class simulation, which provides the structure for the simulation activities. The class simulation provides two functions. The first is used to insert a new event into the queue, while the second runs the simulation. A data field is also provided to hold the current simulation "time."
Storing Pointers versus Storing Values
Storing Pointers versus Storing Values
class simulation {
public:
simulation () : eventQueue(), time(0) { }
void scheduleEvent (event * newEvent)
{ eventQueue.push (newEvent); }
void run();
unsigned int time;
protected:
priority_queue<event *, vector<event *>, eventComparison> eventQueue;
};
Notice the declaration of the priority queue used to hold the pending events. In this case we are using a vector as the underlying container. We could just as easily have used a deque.
The heart of the simulation is the member function run(), which defines the event loop. This procedure makes use of three of the five priority queue operations, namely top(), pop(), and empty(). It is implemented as follows:
void simulation::run()
{
while (! eventQueue.empty()) {
event * nextEvent = eventQueue.top();
eventQueue.pop();
time = nextEvent->time;
nextEvent->processEvent();
delete nextEvent; // free memory used by event
}
}
11.3.1 아이스크림 가게 시뮬레이션
To illustrate the use of our simulation framework, this example program gives a simple simulation of an ice cream store. Such a simulation might be used, for example, to determine the optimal number of chairs that should be provided, based on assumptions such as the frequency that customers will arrive, the length of time they will stay, and so on.
Our store simulation will be based around a subclass of class simulation, defined as follows:
class storeSimulation : public simulation {
public:
storeSimulation()
: freeChairs(35), profit(0.0), simulation() { }
bool canSeat (unsigned int numberOfPeople);
void order(unsigned int numberOfScoops);
void leave(unsigned int numberOfPeople);
private:
unsigned int freeChairs;
double profit;
} theSimulation;
There are three basic activities associated with the store. These are arrival, ordering and eating, and leaving. This is reflected not only in the three member functions defined in the simulation class, but in three separate subclasses of event.
The member functions associated with the store simply record the activities taking place, producing a log that can later be studied to evaluate the simulation.
bool storeSimulation::canSeat (unsigned int numberOfPeople)
// if sufficient room, then seat customers
{
cout << "Time: " << time;
cout << " group of " << numberOfPeople << " customers arrives";
if (numberOfPeople < freeChairs) {
cout << " is seated" << endl;
freeChairs -= numberOfPeople;
return true;
}
else {
cout << " no room, they leave" << endl;
return false;
}
}
void storeSimulation::order (unsigned int numberOfScoops)
// serve icecream, compute profits
{
cout << "Time: " << time;
cout << " serviced order for " << numberOfScoops << endl;
profit += 0.35 * numberOfScoops;
}
void storeSimulation::leave (unsigned int numberOfPeople)
// people leave, free up chairs
{
cout << "Time: " << time;
cout << " group of size " << numberOfPeople <<
" leaves" << endl;
freeChairs += numberOfPeople;
}
As we noted already, each activity is matched by a subclass of event. Each subclass of event includes an integer data field, which represents the size of a group of customers. The arrival event occurs when a group enters. When executed, the arrival event creates and installs a new instance of order event. The function randomInteger() (see Section 2.2.5) is used to compute a random integer between 1 and the argument value.
class arriveEvent : public event {
public:
arriveEvent (unsigned int time, unsigned int groupSize)
: event(time), size(groupSize) { }
virtual void processEvent ();
private:
unsigned int size;
};
void arriveEvent::processEvent()
{ // see if everybody can be seated
if (theSimulation.canSeat(size))
theSimulation.scheduleEvent
(new orderEvent(time + 1 + randomInteger(4), size));
}
An order event similarly spawns a leave event.
class orderEvent : public event {
public:
orderEvent (unsigned int time, unsigned int groupSize)
: event(time), size(groupSize) { }
virtual void processEvent ();
private:
unsigned int size;
};
void orderEvent::processEvent()
{ // each person orders some number of scoops
for (int i = 0; i < size; i++)
theSimulation.order(1 + rand(3));
theSimulation.scheduleEvent
(new leaveEvent(time + 1 + randomInteger(10), size));
};
Finally, leave events free up chairs, but do not spawn any new events.
class leaveEvent : public event {
public:
leaveEvent (unsigned int time, unsigned int groupSize)
: event(time), size(groupSize) { }
virtual void processEvent ();
private:
unsigned int size;
};
void leaveEvent::processEvent ()
{ // leave and free up chairs
theSimulation.leave(size);
}
To run the simulation we simply create some number of initial events (say, 30 minutes worth), then invoke the run() member function.
int main() {
// load queue with some number of initial events
unsigned int t = 0;
while (t < 30) {
t += rand(6);
theSimulation.scheduleEvent(
new arriveEvent(t, 1 + randomInteger(4)));
}
// then run simulation and print profits
theSimulation.run();
cout << "Total profits " << theSimulation.profit << endl;
}