C++事件驅(qū)動型銀行排隊(duì)模擬
最近重拾之前半途而廢的C++，恰好看到了《C++ 實(shí)現(xiàn)銀行排隊(duì)服務(wù)模擬》，但是沒有實(shí)驗(yàn)樓的會員，看不到具體的實(shí)現(xiàn)，正好用來作為練習(xí)。
模擬的是銀行的排隊(duì)叫號系統(tǒng)，所有顧客以先來后到的順序在同一個隊(duì)列中等待，當(dāng)有服務(wù)窗口空閑時，則隊(duì)首的顧客接受服務(wù)，完成后則下一位顧客開始接受服務(wù)。
本實(shí)現(xiàn)是事件驅(qū)動型的，處理對象是事件而不是顧客：
有2種事件：顧客到事件和顧客離開事件。
有2個隊(duì)列：顧客隊(duì)列和事件隊(duì)列。
程序的邏輯如下：
1.初始化事件隊(duì)列，填充顧客到達(dá)事件；
2.處理事件隊(duì)列的頭部（總是為最早發(fā)生的事件），若為“顧客到達(dá)事件”，轉(zhuǎn)向處理“顧客到達(dá)事件”，若為“顧客離開事件”，轉(zhuǎn)向處理“顧客離開事件”；
3.循環(huán)進(jìn)行2，直到事件隊(duì)列為空或超出營業(yè)時間；
4.進(jìn)行清理工作。
事件處理
主流程
永遠(yuǎn)處理事件隊(duì)列的頭部——即最早發(fā)生的事件。
void Manager::run() {
while (_event_queue.size() != 0) {
_current_event = _event_queue.front();
if (_current_event->occur_time >= _total_serve_time)//超出營業(yè)時間
break;
if(_customer_queue.size() == 0 && _event_queue.size() <= _service_num)//生成新的顧客到達(dá)事件
{
generate_arrived_event(_generate_arrived_time);
_current_event = _event_queue.front();//update current event, deal it with order
}
if (_current_event->event_type == EventType::ARRIVIED)//處理顧客到達(dá)事件
customer_arrived();
else if (_current_event->event_type == EventType::DEPARTURE)//處理顧客離開事件
customer_departure();
}
}
生成顧客到達(dá)事件
有2種方法：
（1）一次性生成全部顧客到達(dá)事件
設(shè)定單位時間內(nèi)到達(dá)的顧客數(shù)量，生成銀行營業(yè)時間內(nèi)所有的到達(dá)事件，處理這些事件，直到事件隊(duì)列為空或是超過了銀行的營業(yè)時間。
void Manager::generate_arrived_event(int& current_time) {//生成單位時間內(nèi)的顧客到達(dá)事件并入隊(duì)，current_time是共享的
Event* event;
int customer_per_minute = Random::uniform(RANDOM_PER_MINUTE);//單位時間內(nèi)隨機(jī)到達(dá)的顧客數(shù)量，至少為1例
while (customer_per_minute > 0) {
event = new Event(current_time);
_event_queue.enqueue(event);
--customer_per_minute;
}
++current_time;
}
_generate_arrived_time = 0;
while(_generate_arrived_time < _total_serve_time) { //_total_serve_time是銀行的總營業(yè)時間
generate_arrived_event(_generate_arrived_time);
}
（2）分批生成顧客到達(dá)事件
僅在需要時生成顧客到達(dá)事件，因?yàn)轭櫩徒邮芊?wù)需要一定的時間，通常來說第1種方法生成的到達(dá)事件在達(dá)到銀行營業(yè)時間后不能全部處理完成，這就造成了時間和空間上的浪費(fèi)。分批生成到達(dá)事件的實(shí)現(xiàn)是基于這樣的事實(shí)：如果顧客隊(duì)列為空且事件隊(duì)列的長度小于等于服務(wù)窗口的數(shù)量時，說明余下的事件將不能讓服務(wù)窗口滿載并產(chǎn)生等待服務(wù)的顧客，此時就需要生成新的顧客到達(dá)事件。
初始化事件隊(duì)列：
_generate_arrived_time = 0;//依舊是以時間順序生成顧客到達(dá)事件
while(_generate_arrived_time < INIT_ARRIVIED_EVENT_NUM) {//選擇合適的值，使最初生成的顧客到達(dá)事件略多于服務(wù)窗口數(shù)量，保證服務(wù)窗口滿載且有等待顧客即可
generate_arrived_event(_generate_arrived_time);
}
判斷條件并生成到達(dá)事件：
if(_customer_queue.empty() && _event_queue.size() <= _service_num)
{
generate_arrived_event(_generate_arrived_time);
_current_event = &_event_queue.top();//update current event, deal it with order
}
由于顧客到達(dá)事件仍是以時間順序從0到營業(yè)時間結(jié)束來生成的，之所以能夠保證不會在處理了98分鐘時的顧客離開事件（可能是5分鐘時到達(dá)的顧客產(chǎn)生的）后再去處理新插入的10分鐘時的顧客到達(dá)事件，就是初始化事件隊(duì)列時選擇合適的INIT_ARRIVIED_EVENT_NUM的意義所在：時刻保證事件隊(duì)列的長度大于服務(wù)窗口的數(shù)量，新生成的顧客到達(dá)事件的時間若早于顧客離開事件的時間（以時間為順序生成顧客到達(dá)事件就保證了新生成的顧客到達(dá)事件的時間不小于事件隊(duì)列中已有的顧客到達(dá)事件，而顧客離開事件的時間是隨機(jī)的，若提前于新生成的顧客到事件處理，可能會失序）也能被正確處理。
生成顧客離開事件
顧客隊(duì)列頭部顧客接受服務(wù)并出隊(duì)，生成顧客離開事件并入隊(duì)事件隊(duì)列。顧客離開事件的發(fā)生時間 = 當(dāng)前時間 + 顧客接受服務(wù)的時長。
void Manager::generate_departure_event(int service_index, int current_time) {
_services[service_index].serve_customer(*_customer_queue.front());
_services[service_index].set_busy();//服務(wù)窗口置為“忙”
_services[service_index].set_service_start_time(current_time);//服務(wù)開始時間
_customer_queue.dequeue();
int duration = _services[service_index].get_customer_duration();
Event* event = new Event(current_time + duration, EventType::DEPARTURE, service_index);//生成顧客離開事件
_event_queue.enqueue(event);
}
處理顧客到達(dá)事件
處理“顧客到達(dá)事件”的邏輯：
1.生成1個顧客，入隊(duì)顧客隊(duì)列；
2.出隊(duì)事件隊(duì)列；
3.若有空閑的服務(wù)窗口，則生成“顧客離開事件”。
下面是代碼：
void Manager::customer_arrived() {
int idle_service_num = get_idle_service_index();//獲取空閑的服務(wù)窗口，返回-1說明未找到
int current_time = _current_event->occur_time;
Customer* customer = new Customer(current_time);//顧客到達(dá)事件發(fā)生時間即為顧客到達(dá)時間， 顧客接受服務(wù)的時長隨機(jī)
_customer_queue.enqueue(customer);
_event_queue.dequeue();
if (idle_service_num != -1)
generate_departure_event(idle_service_num, current_time);
}
處理顧客離開事件
處理“顧客離開事件”的邏輯：
1.顧客所在服務(wù)窗口置為空閑，統(tǒng)計顧客信息；
2.出隊(duì)事件隊(duì)列；
3.若顧客隊(duì)列不為空且有空閑的服務(wù)窗口，生成“顧客離開事件”。
下面是代碼：
void Manager::customer_departure() {
int current_time = _current_event->occur_time;
int service_index = _current_event->service_index;//顧客離開的服務(wù)窗口
_customer_stay_time += current_time -
_services[service_index].get_customer_arrive_time();//統(tǒng)計顧客在銀行的滯留時間
++_total_served_customer_num;//接受服務(wù)的顧客數(shù)目加1
_services[service_index].set_idle();
_event_queue.dequeue();
if(_customer_queue.size() > 0) {
service_index = get_idle_service_index();//有顧客離開，必然可以獲得1個空閑服務(wù)窗口，這里獲取最小序號的服務(wù)窗口
generate_departure_event(service_index, current_time);
}
}
清理工作：
1.尋找仍在接受服務(wù)的顧客并統(tǒng)計他們的信息；
2.釋放動態(tài)申請的內(nèi)存。
下面是代碼：
void Manager::end() {
for (int i = 0; i < _service_num; i++) {
if (!_services[i].is_idle()) {//統(tǒng)計正在接受服務(wù)的顧客的信息
int service_start_time = _services[i].get_service_start_time();
int arrive_time = _services[i].get_customer_arrive_time();
int duration = _services[i].get_customer_duration();
_customer_stay_time += service_start_time + duration - arrive_time;
++_total_served_customer_num;
}
}
//釋放動態(tài)申請的內(nèi)存
_customer_queue.clear();
_event_queue.clear();
delete[] _services;
}
關(guān)于隊(duì)列的說明
程序中使用的是自定義的隊(duì)列，根據(jù)需求，可以使用STL中的優(yōu)先隊(duì)列和隊(duì)列，前者用于事件隊(duì)列，后者用于顧客隊(duì)列。
優(yōu)先隊(duì)列的頭部總是優(yōu)先級最高的節(jié)點(diǎn)，對于事件來說，就是發(fā)生的時間越早，事件優(yōu)先級越高，所以這是一個最小堆——時間發(fā)生的時間最?。ㄗ钤纾┑奈挥诙秧?。這涉及到對Event類型的比較，使用STL的greater<Event>（需要重載operator>）或是自定義的函數(shù)對象來比較2個Event對象：
（1）重載operator>運(yùn)算符
//聲明使用greater<Event>作為比較函數(shù)的優(yōu)先隊(duì)列
std::priority_queue<Event, std::vector<Event>, std::greater<Event>> _event_queue; //event_queue.h
#ifndef BANKQUEUE_EVENT_QUEUE_H
#define BANKQUEUE_EVENT_QUEUE_H
#include "random.h"
enum class EventType : int {
ARRIVIED,
DEPARTURE
};
class Event {
public:
Event():occur_time(Random::uniform(RANDOM_PARAMETER)),
event_type(EventType::ARRIVIED),
service_index(-1),
next(nullptr){}
Event(int occur_time):occur_time(occur_time),
event_type(EventType::ARRIVIED),
service_index(-1),
next(nullptr){}
Event(int occur_time, EventType event_type, int service_index):
occur_time(occur_time),
event_type(event_type),
service_index(service_index),
next(nullptr) {}
friend bool operator< (const Event& event1, const Event& event2);//模仿STL的實(shí)現(xiàn)，都是通過'<'來完成余下的比較操作符
friend bool operator> (const Event& event1, const Event& event2);//供`greater<Event>`使用
public:
int occur_time;
int service_index;
EventType event_type;
Event *next;
};
inline bool operator< (const Event& event1, const Event& event2) {
return event1.occur_time < event2.occur_time;
}
inline bool operator> (const Event& event1, const Event& event2) {
return event2 < event1;//通過'<'實(shí)現(xiàn)'>'的功能
}
#endif //BANKQUEUE_EVENT_QUEUE_H
（2）比較直觀且簡單的做法是自定義用于比較的函數(shù)對象：
//聲明使用EventComp作為比較函數(shù)的優(yōu)先隊(duì)列
std::priority_queue<Event, std::vector<Event>, EventComp> _event_queue; struct EventComp
{
bool operator()(const Event& lhs, const Event& rhs) const
{
return lhs.occur_time > rhs.occur_time;//occur_time是公有的，若是私有的，則需要提供接口
}
};
可以在test.h中通過USE_SELF_DEFINE_QUEUE宏來切換2種隊(duì)列的使用。
事件隊(duì)列的順序
事件隊(duì)列要求隊(duì)首總是發(fā)生時間最早的事件，最小堆是非常好的選擇，通過前面介紹的STL優(yōu)先隊(duì)列可以輕松實(shí)現(xiàn)。自定義的隊(duì)列則使用的是蠻力法，在事件入隊(duì)時就進(jìn)行排序，保證隊(duì)列是以發(fā)生時間升序的，在隊(duì)列中元素較多時（如幾百個），效率是低于使用STL優(yōu)先隊(duì)列的方法的，這也是為何要分批生成顧客到達(dá)事件的原因之一：防止事件隊(duì)列的元素過多。
顧客隊(duì)列是不需要排序的，所以以模板特例化的方式實(shí)現(xiàn)了事件隊(duì)列的入隊(duì)方法：
template<>
void Queue<Event>::enqueue(Event* event) {
Event *cur = _front, *prev = nullptr;
while (cur != nullptr) {
if (cur->occur_time < event->occur_time) {
prev = cur;
cur = cur->next;
}
else
break;
}
if (prev == nullptr) {
event->next = _front;
_front = event;
if (_rear == nullptr)
_rear = event;//_rear is useless to Event queue
}
else {
event->next = prev->next;
prev->next = event;
if (prev == _rear)
_rear = event;
}
++length;
}
完整代碼在這里。
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
- VC++實(shí)現(xiàn)文件與應(yīng)用程序關(guān)聯(lián)的方法(注冊表修改)
- C++寫注冊表項(xiàng)實(shí)例
- C++訪問注冊表獲取已安裝軟件信息列表示例代碼
- C++中事件機(jī)制的簡潔實(shí)現(xiàn)及需要放棄的特性
- C++設(shè)置事件通知線程工作的方法
- 解決C++中事件不響應(yīng)的方法詳解
- C++事件處理中__event與__raise關(guān)鍵字的用法講解
- 深入解析C++程序中激發(fā)事件和COM中的事件處理
- C++事件處理中的__hook與__unhook用法詳解
- VC++實(shí)現(xiàn)添加文件關(guān)聯(lián)的方法示例
相關(guān)文章
這篇文章主要介紹了C語言實(shí)現(xiàn)的PNPoly算法代碼例子,PNPoly算法j是判斷一個坐標(biāo)點(diǎn)是否在不規(guī)則多邊形內(nèi)部的算法,需要的朋友可以參考下2014-07-07
OpenCV實(shí)現(xiàn)圖像轉(zhuǎn)換為漫畫效果
這篇文章主要為大家詳細(xì)介紹了OpenCV實(shí)現(xiàn)圖像轉(zhuǎn)換為漫畫效果，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-08-08
C++ 將數(shù)據(jù)轉(zhuǎn)為字符串的幾種方法
這篇文章主要介紹了C++ 將數(shù)據(jù)轉(zhuǎn)為字符串的幾種方法，十分的實(shí)用，有需要的小伙伴可以參考下。2015-06-06
Objective-C中常用的結(jié)構(gòu)體NSRange,NSPoint,NSSize(CGSize),NSRect實(shí)例分析
這篇文章主要介紹了Objective-C中常用的結(jié)構(gòu)體NSRange,NSPoint,NSSize(CGSize),NSRect實(shí)例分析,有助于更加直觀的理解Object-C常用的結(jié)構(gòu)體,需要的朋友可以參考下2014-07-07
在編寫C程序時，如果想要打印某個字符串，而字符串的內(nèi)容比較多，這就涉及到對這個長字符串進(jìn)行書寫換行，本片文章就帶你了解一下2021-09-09
QT quick-Popup彈出窗口自定義的實(shí)現(xiàn)
本文主要介紹了QT quick-Popup彈出窗口自定義的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-07-07
C++實(shí)現(xiàn)圖書館管理系統(tǒng)源碼
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)圖書館管理系統(tǒng)源碼，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
這篇文章主要為大家詳細(xì)介紹了C語言之指針和數(shù)組，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-01-01
這篇文章主要為大家詳細(xì)介紹了Qt實(shí)現(xiàn)簡單的TCP通信，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-08-08
C++?OpenCV實(shí)現(xiàn)物體尺寸測量示例詳解
本文主要介紹了利用OpenCV對物體的尺寸進(jìn)行測量，即先定位到待測物體的位置，然后測量物體的寬高。感興趣的同學(xué)可以跟隨小編一起學(xué)習(xí)學(xué)習(xí)2022-01-01