C++事件驱动型银行排队模拟
最近重拾之前半途而废的C++,恰好看到了《C++ 实现银行排队服务模拟》,但是没有实验楼的会员,看不到具体的实现,正好用来作为练习。 模拟的是银行的排队叫号系统,所有顾客以先来后到的顺序在同一个队列中等待,当有服务窗口空闲时,则队首的顾客接受服务,完成后则下一位顾客开始接受服务。 本实现是事件驱动型的,处理对象是事件而不是顾客: 程序的逻辑如下: 事件处理 主流程 永远处理事件队列的头部――即最早发生的事件。 void Manager::run() { while (_event_queue.size() != 0) { _current_event = _event_queue.front(); if (_current_event->occur_time >= _total_serve_time)//超出营业时间 break; if(_customer_queue.size() == 0 && _event_queue.size() <= _service_num)//生成新的顾客到达事件 { 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)//处理顾客到达事件 customer_arrived(); else if (_current_event->event_type == EventType::DEPARTURE)//处理顾客离开事件 customer_departure(); } } 生成顾客到达事件 有2种方法: void Manager::generate_arrived_event(int& current_time) {//生成单位时间内的顾客到达事件并入队,current_time是共享的 Event* event; int customer_per_minute = Random::uniform(RANDOM_PER_MINUTE);//单位时间内随机到达的顾客数量,至少为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是银行的总营业时间 generate_arrived_event(_generate_arrived_time); } (2)分批生成顾客到达事件 _generate_arrived_time = 0;//依旧是以时间顺序生成顾客到达事件 while(_generate_arrived_time < INIT_ARRIVIED_EVENT_NUM) {//选择合适的值,使最初生成的顾客到达事件略多于服务窗口数量,保证服务窗口满载且有等待顾客即可 generate_arrived_event(_generate_arrived_time); } 判断条件并生成到达事件: 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 } 由于顾客到达事件仍是以时间顺序从0到营业时间结束来生成的,之所以能够保证不会在处理了98分钟时的顾客离开事件(可能是5分钟时到达的顾客产生的)后再去处理新插入的10分钟时的顾客到达事件,就是初始化事件队列时选择合适的INIT_ARRIVIED_EVENT_NUM的意义所在:时刻保证事件队列的长度大于服务窗口的数量,新生成的顾客到达事件的时间若早于顾客离开事件的时间(以时间为顺序生成顾客到达事件就保证了新生成的顾客到达事件的时间不小于事件队列中已有的顾客到达事件,而顾客离开事件的时间是随机的,若提前于新生成的顾客到事件处理,可能会失序)也能被正确处理。 生成顾客离开事件 顾客队列头部顾客接受服务并出队,生成顾客离开事件并入队事件队列。顾客离开事件的发生时间 = 当前时间 + 顾客接受服务的时长。 void Manager::generate_departure_event(int service_index,int current_time) { _services[service_index].serve_customer(*_customer_queue.front()); _services[service_index].set_busy();//服务窗口置为“忙” _services[service_index].set_service_start_time(current_time);//服务开始时间 _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); } 处理顾客到达事件 处理“顾客到达事件”的逻辑: 下面是代码: void Manager::customer_arrived() { int idle_service_num = get_idle_service_index();//获取空闲的服务窗口,返回-1说明未找到 int current_time = _current_event->occur_time; Customer* customer = new Customer(current_time);//顾客到达事件发生时间即为顾客到达时间, 顾客接受服务的时长随机 _customer_queue.enqueue(customer); _event_queue.dequeue(); if (idle_service_num != -1) generate_departure_event(idle_service_num,current_time); } 处理顾客离开事件 处理“顾客离开事件”的逻辑: 下面是代码: void Manager::customer_departure() { int current_time = _current_event->occur_time; int service_index = _current_event->service_index;//顾客离开的服务窗口 _customer_stay_time += current_time - _services[service_index].get_customer_arrive_time();//统计顾客在银行的滞留时间 ++_total_served_customer_num;//接受服务的顾客数目加1 _services[service_index].set_idle(); _event_queue.dequeue(); if(_customer_queue.size() > 0) { service_index = get_idle_service_index();//有顾客离开,必然可以获得1个空闲服务窗口,这里获取最小序号的服务窗口 generate_departure_event(service_index,current_time); } } 清理工作: 下面是代码: void Manager::end() { for (int i = 0; i < _service_num; i++) { if (!_services[i].is_idle()) {//统计正在接受服务的顾客的信息 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; } } //释放动态申请的内存 _customer_queue.clear(); _event_queue.clear(); delete[] _services; } 关于队列的说明 程序中使用的是自定义的队列,根据需求,可以使用STL中的优先队列和队列,前者用于事件队列,后者用于顾客队列。 //声明使用greater<Event>作为比较函数的优先队列 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),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的实现,都是通过'<'来完成余下的比较操作符 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;//通过'<'实现'>'的功能 } #endif //BANKQUEUE_EVENT_QUEUE_H (2)比较直观且简单的做法是自定义用于比较的函数对象: //声明使用EventComp作为比较函数的优先队列 std::priority_queue<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种队列的使用。 事件队列的顺序 事件队列要求队首总是发生时间最早的事件,最小堆是非常好的选择,通过前面介绍的STL优先队列可以轻松实现。自定义的队列则使用的是蛮力法,在事件入队时就进行排序,保证队列是以发生时间升序的,在队列中元素较多时(如几百个),效率是低于使用STL优先队列的方法的,这也是为何要分批生成顾客到达事件的原因之一:防止事件队列的元素过多。 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; } 完整代码在这里。 以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持编程小技巧。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |