电梯调度算法

1 有关结对编程的思考

结对编程技术是指两位程序员肩并肩地坐在同⼀台电脑前合作完成同⼀个设计、同⼀个算法、同⼀段代码或同⼀组测试。通过这次的结对编程练习我结识了李承晗同学，体验了结对编程这样⼀种新的编程⽅式。在结对编程的过程中，对结对编程的体验总结如下：结对编程的优点如下：

在独⽴设计、实现代码的过程中不免要犯这样那样的错误。在结对编程中，因为有随时的复审和交流，程序各⽅⾯的质量便取决于⽔平较⾼的那⼀位。这样，程序中的错误就会少得多，程序的初始质量会⾼很多，同时也省下很多以后修改、测试的时间。这样⾼质量的产出能够给程序员，尤其是能⼒较低的（我）那⼀位带来⼀些信⼼。⽽且，在结对编程的过程中两位程序员互相交流，相互学习传递经验，能够在结对编程的过程中学习到更多的东西。但是结对编程也存在着⼀定的缺点：

结对编程的过程中，代码⼀直处于“复审”的过程，即不断地审核，提⾼设计和编码质量的过程。这样对于提⾼代码质量有很⼤的帮助，但是在互审的过程中也存在着⼀些问题：例如，复审的程序员对代码不及编写代码的程序员深⼊了解降低了复审的效果。⽽且，这次结对编程是随机分组的，以前并不熟悉，这次结对编程的过程也会因为互相并不熟悉⽽产⽣⼀些缺少交流的问题。结对编程队员的优缺点：

李承晗学习态度⽐较好，且基础扎实，不懂就问，积极上进，就是有点内向，需要交流。

2 有关Information Hiding, interface design, loose coupling

Information Hiding：在⾯向对象⽅法中Information Hiding是通过对象的封装实现的。隐藏对象的属性和实现细节，仅对外公开接⼝，控制在程序中属性的读和修改的访问级别；将抽象得到的数据和⾏为（或功能）相结合，形成⼀个有机的整体。在程序设计过程中可以通过控制访问权限来实现。例如⽤private，public，protected修饰属性和⽅法。interface design：interface design包括三个⽅⾯：1 ⽤户接⼝

⽤来说明将向⽤户提供的命令和它们的语法结构，以及软件的回答信息。2 外部接⼝

⽤来说明本系统同外界的所有接⼝的安排包括软件与硬件之间的接⼝、本系统与各⽀持软件之间的接⼝关系。3 内部接⼝

⽤来说明本系统之内的各个系统元素之间的接⼝的安排

loose coupling：类与类之间的互相调⽤，这两个类之间就会有⽐较⾼的耦合程度，降低类与类之间的耦合程度，可以通过接⼝实现。3 有关Design by Contract

契约式设计或者Design by Contract (DbC)是⼀种设计计算机软件的⽅法。这种⽅法要求软件设计者为软件组件定义正式的，精确的并且可验证的接⼝，这样，为传统的抽象数据类型⼜增加了先验条件、后验条件和不变式。这种⽅法和商业契约的情况有点类似。所谓契约，也就是合约，规定两个交互物件上的权利和责任。雇佣合同规定你的⼯作时数和你必须遵守的⾏为规则，作为公司则付你薪⽔，双双履⾏义务，双双受益。DbC的核⼼思想是对软件系统中的元素之间相互合作以及“责任”与“义务”的⽐喻。在⾯向对象程序设计中⼀个类的函数提供了某种功能，那么它要：

1.期望所有调⽤它的客户模块都保证⼀定的进⼊条件：这就是函数的先验条件—客户的义务和供应商的权利，这样它就不⽤去处理不满⾜先验条件的情况。

2.保证退出时给出特定的属性：这就是函数的后验条件—供应商的义务，显然也是客户的权利。3.在进⼊时假定，并在退出时保持⼀些特定的属性：不变式。因此在进⾏Dbc的时候我们通常要考虑三个问题：1.它期望的是什么？2.它要保证的是什么？3.它要保持的是什么？DbC六⼤原则

原则1 区分命令和查询。查询返回⼀个结果，但不改变对象的可见性质。命令改变对象的状态，但不返回结果。（应当是不⼀定返回结果）

原则 2 将基本查询同派⽣查询分开。派⽣查询可以⽤基本查询来定义。

原则 3 针对每个派⽣查询，设定⼀个后验条件，使⽤⼀个或多个基本查询的结果来定义它。这样我们只要知道基本查询的值，也就能知道派⽣查询的值。

原则 4 对于每个命令都撰写⼀个后验条件，规定每个基本查询的值。结合“⽤基本查询定义派⽣查询”的原则，我们现在已经能够知道每个命令的全部可视效果。

原则 5 对于每个查询和命令，采⽤⼀个合适的先验条件。先验条件限定了客户调⽤查询和命令的时机。

原则 6 撰写不变式来定义对象的恒定特性。类是某种抽象的体现，应当将注意⼒集中在最重要的属性上，以帮助读者建⽴关于类抽象的正确概念模型。

4 uml图5 UnitTest6 算法概述：

对于每个电梯，建⽴⼀个List存放该电梯需要访问的楼层列表，dst类包含⼀个int和⼀个Direction参数，⼀个表⽰⽬标楼层，⼀个表⽰该请求的⽅向。该列表通过⼀个sortList()⽅法进⾏排序（根据电梯当前⽅向和楼层来确定List中元素的访问顺序）。

每次调⽤run()⽅法时，⾸先遍历所有电梯，调⽤gotoFirst()⽅法访问它们访问列表的⾸项，如果没有⾸项，根据当前客流情况（上下班之类的）添加⼀个⽬的地。

随后我们扫描当前请求列表中的请求，对于每个请求，我们扫描每个电梯，通过⼀个估价函数upValue()来确定当前请求插⼊后所产⽣的代价，然后选取代价最⼩的电梯，将该请求插⼊到访问列表中。然后调⽤sortList()⽅法进⾏排序。

算法关键：

排序算法sortList()的应该算是⼀个关键吧，排序要考虑当前⽅向和楼层，然后根据请求的⽅向和楼层来排访问列表，这⾥情况很多，所以代码量很⼤。另⼀个关键就是估价函数upvalue()，对于⼀个请求，扫描电梯的访问列表确定其所在位置，然后返回⼀个代价，这⾥找位置也不太容易实现，其实最后我也没有精确的找到这个位置，只是给出了⼀个⼤概的位置和估价。sortList()⽅法调试了我好久，重写了⼤概3次吧，因为如果稍微顺序错了，就会导致⼈上不了电梯，更诡异的还会直接把这个⼈给忽略掉。