模拟银行窗口排队叫号系统的运作

待我称王封你为后i 2022-09-30 04:58 184阅读 0赞

最近在网上看到了一道面试题，初看很简单，细看有点意思的一道题目：

[http://blog.csdn.net/zhangxiaoxiang/archive/2011/04/01/6294132.aspx][http_blog.csdn.net_zhangxiaoxiang_archive_2011_04_01_6294132.aspx]

为避免版权纠纷，我这里就不引用原文了。

各人对题目的理解不一样，我把它当成一道离散事件仿真题目来做，用一个优先队列解决。

完整的代码见 [https://github.com/chenshuo/recipes/tree/master/java/bankqueue][https_github.com_chenshuo_recipes_tree_master_java_bankqueue] 。

# 离散事件模拟 #

《数据结构》课程常以离散事件模拟为例介绍优先队列的应用。其基本思路是，以事件发生的时刻为序，模拟事件的执行，优先队列的 key 就是事件发生的时间点，这样每次从队列取出头一个元素就是下一个要发生的事件。关键代码如下：

事件 Event class 是 immutable，它有一个 abstract method，供派生类覆写 (override)。

import java.util.concurrent.atomic.AtomicInteger;
    
    public abstract class Event implements Comparable {
    
        private static AtomicInteger numEventsCreated = new AtomicInteger();
    
        public final int scheduledTime;
        public final int tieBreaker;
    
        public Event(int time) {
            this.scheduledTime = time;
            this.tieBreaker = numEventsCreated.getAndIncrement();
        }
    
        public int compareTo(Event rhs) {
            if (scheduledTime != rhs.scheduledTime)
                return scheduledTime - rhs.scheduledTime;
            else
                return tieBreaker - rhs.tieBreaker;
        }
    
        public abstract void happen(EventSimulator simulator);
    }

事件模拟器 EventSimulator 以 PriorityQueue 为成员，依次取出其元素，模拟事件运行。

import java.util.PriorityQueue;
    
    public class EventSimulator {
    
        private int now = 0;
        private PriorityQueue queue = new PriorityQueue();
    
        public int getNow() {
            return now;
        }
    
        public void addEvent(Event e) {
            queue.add(e);
        }
    
        public void run() {
            Event ev = queue.poll();
            while (ev != null) {
                assert ev.scheduledTime >= now;
                now = ev.scheduledTime;
                ev.happen(this);
                ev = queue.poll();
            }
        }
    }

这个 simulator 运转起来之后，Event.happen() 在执行期间可以添加新的事件。比方说 queue 里目前只有一个 CustomerArriveEvent 事件：某客户在 800(秒) 时刻到达，他的服务耗时是 300 秒。在 800 时刻，simulator 触发这个事件，调用 CustomerArriveEvent.happen()，如果这时有空余窗口，Customer 会坐到那个窗口，再向 simulator 添加一个 CustomerLeaveEvent 事件，其将会发生在 1100 时刻。到了 1100 时刻（simulator 可以立刻跳到这个时刻，如果之前没有别的事件等待发生的话。）触发 CustomerLeaveEvent 事件，该客户办完业务离开窗口，这时候有一个窗口空出来了，可以从等待队列里边找一个合适的客户来服务。

# 分析 #

我采用相对时间，以秒为单位，银行早上开门为时间的起点。这个系统只模拟一天的运行，毕竟银行到了下午就要关门，第二天又是新的开始，从头再来。

这个系统只模拟窗口叫号，跟银行的金融业务没关系，客户 Customer 也仅仅是排队叫号系统的客户，跟银行账户没关系。（一个来办理新开户的客户可能根本没有银行账户。）

客户的身份在到达银行的时候就确定了，他在排队的时候不会改变身份，这样我们可以用 Customer 的三个派生类来封装每种客户的行为，避免 type-switch。

客户的身份由他要办理的业务决定，比如张三上午来交水电费，他就是快速客户，他下午来取工资款，他就是普源客户。

根据题目描述，实际上普通客户可以去任何窗口办理业务，而 VIP 客户只能在 VIP 窗口办理，快速客户只能在快速窗口办理。

客户到达之后，如果当前有空余窗口，那么他可以立刻开始办理业务，并于预设的秒数之后离开。如果当前没有空余窗口，那么他开始排队。

系统只有一个客户队列，客户按到达的先后顺序在此排队。也就是说客户不会自行走到窗口前排队，而是拿一个号，等在大厅里。由系统在窗口上方显示“XX 号客户请去 Y 号窗口办理业务”。

客户在排队的时候不会主动离开，他会一直等在队列里，直到被叫号。

一个客户只能在一个窗口办理完业务，当他坐下来开始办理业务之后，他不会再换窗口。

一个窗口同时只能服务一个客户。

当一个客户办理完业务离开，空余出窗口，系统会在客户队列里找一个合适的客户，开始为他办理业务。

客户是彼此独立的。每个客户的到达的时刻是独立事件，跟别的客户无关，跟银行的拥挤程度也无关。客户办理业务的耗时是独立的，与其他客户无关，跟银行的拥挤程度也无关。

由上分析可知，系统只处理两种事件：客户到达，客户离开。客户离开的时刻不完全由他到达的时刻确定，而是由银行拥挤程序确定。

鉴于仿真系统的特点，我们可以假定一天之内每个客户的到达时刻和办理业务耗时是事先确定的（尽管二者都是随机数），这样我们可以在程序初始化的时候就把一天之内的全部客户到达事件加到优先队列中，由程序仿真。这样仿真的结果与“在运行时随机添加客户”是一样的。

当事件队列中没有新的事件时，银行一天的业务结束，程序退出。（这时候每个窗口都是空闲的，客户队列里也没有人排队。）

# 设计要点 #

*  正确性。要让系统的结果可以自动化测试，而不是靠人眼去看 log。
 *  确定性。 只要“一天之内每个客户的到达时刻和办理业务耗时是事先确定的”，那么系统仿真的结果也应该是确定的。
 *  高效率。如果真的按题目要求的采用 Sleep 来模拟，一个耗时 5 分钟的客户真的要 Sleep(300) 吗？要模拟银行一天的业务岂不是程序要 run 8 小时？
 *  配置性。假设客户的比例变成 2:4:4，那么代码的改动应该很直接。

以上四点请读者评鉴 [http://blog.csdn.net/zhangxiaoxiang/archive/2011/04/01/6294132.aspx][http_blog.csdn.net_zhangxiaoxiang_archive_2011_04_01_6294132.aspx] 的实现。

*  扩展性？增加一个“企业”窗口会有哪些改动？面向对象的可扩展性是针对程序员而言，能不能让不懂编程的普通用户也能扩展 simulator 的功能？
 *  面向对象？面向对象不是目的，我的代码里 Customer 是一个继承树，而 Window Type 采用了 type-switch，好在 type-switch 只出现了一处，尚不到“事不过三，三则重构”的标准。type-switch 有时候是不可避免的，比如 Customer createCustomer(enum CustomerType type)。

# 代码 #

完整的代码见 [https://github.com/chenshuo/recipes/tree/master/java/bankqueue][https_github.com_chenshuo_recipes_tree_master_java_bankqueue] 。注意，代码中 Event 和 Customer 都是 immutable，程序的可变状态主要集中在 Bank class 中，换言之“逻辑分散、数据集中”。由于是 immutable，所有某些数据成员是 public final 的。

# 测试 #

我编写了一些单元测试，比如单个客户到达，多个客户到达，有客户排队，有客户离开窗口后找人填空 等等。这些测试还不完整，仅仅做到了基本的覆盖。

代码见 [https://github.com/chenshuo/recipes/tree/master/java/bankqueue/tests][https_github.com_chenshuo_recipes_tree_master_java_bankqueue_tests]

为了简化起见，测试代码直接拦截了 simulator 的输出，这么做比较脆弱，不过既然题目要求用 log 展示结果，那么直接检查最终的 log 输出似乎也是说得过去的。。

# 不用面向对象怎么做？ #

假设要设计一个通用的窗口排队叫号仿真软件，这个软件的用户不懂编程，当然也不懂继承与面向对象，那么如何做到他能自由配置窗口的种类和数量，以及用户的种类和数量？这个软件可以卖给银行的营业部，他们可以用来仿真各种窗口配置比例下客户的平均等待时间，以优化窗口的配比。

我的想法是：表驱动。

业务逻辑用两个表来配置：

![bankqueue.png][]

第一个表说明如果窗口空闲，那么客户到达之后可以去哪个窗口办理业务，以及客户选择的优先级。如果 VIP 窗口空闲，那么普通客户和 VIP 客户都可以去办理业务，但快读客户不允许。普通用户到达，如果所有窗口都空闲，那么他应该优先选择普通窗口。

第二个表说明当客户离开，空出一个窗口时，该窗口应该在客户队列里找什么客户来办理业务。如果空出一个快速窗口，它会先在客户队列里找快速客户，如果没有，再找普通客户。如果都没有，它就空闲。

这样如果增加或减少窗口的类型（而不仅仅是窗口的数目），或者增加或减少客户类型（不仅仅是客户比例），只需要修改配置表，不用动代码，也不用劳烦程序员。

这个想法我还没有实现。

# 小结 #

或许我的解法不符合出题人的意愿，但愿能让读者点点头。

[http_blog.csdn.net_zhangxiaoxiang_archive_2011_04_01_6294132.aspx]: http://blog.csdn.net/zhangxiaoxiang/archive/2011/04/01/6294132.aspx
[https_github.com_chenshuo_recipes_tree_master_java_bankqueue]: https://github.com/chenshuo/recipes/tree/master/java/bankqueue
[https_github.com_chenshuo_recipes_tree_master_java_bankqueue_tests]: https://github.com/chenshuo/recipes/tree/master/java/bankqueue/tests
[bankqueue.png]: http://chenshuo.com/upload/bankqueue.png