See Elevator Run Floors

“在我短暂的电梯作业中我发现，架构的优化能力是有限的。越是工于优化算法…越是会被自己的架构所制约…。想要更好的优化，唯有超越架构………"

零、基础

优化建立在架构之上，这句话莫得问题，也莫得感情。

一个蒻小的架构往往会被（我）因为一点点微小的优化工作而将架构破坏的面目全非，甚至失去了正确性。

所以我这次使用的是Floor类的策略：

废话不多言，直接上图（单电梯为例）：

简单地说说，Floor类是请求队列的另一种表现形式，直接的好处是从开始引入了对请求的“分配”概念，还有从开始就镶嵌入架构的LOOK调度算法。这些从开始就加入的要素往往会对优化产生极大的积极效果，

那么下面请让我介绍一下我的优化算法/优化架构：

一、单电梯与贪心的LOOK

1.1. 标准化的LOOK（这也算优化？！？）

标准而且依赖于信息交互而非算法计算的LOOK是优化的起点，那么什么是标准的LOOK呢？

首先便是非同向请求慎接，举个例子：现在在5楼往上走，没有6楼Er请求，然后有一个233-FROM-6-TO--2。这样其实我们在去的途中是不接他的——回来再接。这个是在不造成损失的情况下让请求尽量能和其他请求聚堆处理，也是LOOK的一个重要特征。我对这个的实现依赖于分配，在单电梯作业里将一层楼内的请求分为向上的和向下的，从而顺利解决问题。

然后是单方向最远策略，举例：电梯里没人在5楼，同时俩请求：233-FROM-6-TO--2，322-FROM-10-TO-15，这样我们在接完233后其实是要继续往上走接322的。这个的实现依赖于架构，人人各有一套简单方法，故略去不表。

1.2. 贪心转向

这个心怎么贪呢？我的电梯有仨状态：向上走、向下走、停车。除开用来处理一些特殊情况的停车，我们只需要知道是向上走还是向下走更优（这里的性能更优指能更快解决当前的所有请求。我们当然也知道我们电梯的算法，所以计算出来时间进行比较选择更优的那种显然是可行的方案。

我想到了两种方案去实现这个贪心算法，其一是手工算，或是对当前情况做一些简化或对算法精确度降低要求然后计算，都会得到不错的结果。其二是在电梯中模拟一个电梯，新电梯比之之前的电梯货真价实的“停”了400ms相比，是将400ms这个胺数值累计起来，同时将当前情况完全clone出来让电梯自行模拟运动过程，最后访问累计的时间值就能获得真实的运动时间。

1.3. 唯有超越现实

“即充分利用等待时间。”

我们常常会遇到这样的情况：电梯用sleep或wait去模拟等待时间，结果却在这段时间后发生了新的事件并且新情况很可能已将不再适合于我们之前的运动形式。虽然这个世界上没有后悔药可以吃，但是我们确实可以用这段时间来做一些“弥补”工作：

比如说我们用贪心算法计算出来最佳朝向后仿真运动400ms时间内出现了打破了策略平衡性的请求，我们这时候就可以通过进一步的计算来修正我们的方向（其实就是重新算一遍，算两遍可以减少卡算法的可能）。

再比如对于门的操作有400ms，如果我们使用了先进出人再执行操作的策略，我们就可以通过判断400ms后是否还有未处理的请求，有则继续等这样的算法来避免连续一段时间每隔一段时间来一个请求这样的请求状况。

也许还会有人会问既然如此为什么不直接将转向判定直接放在400ms之后。

因为这不OO，over。

二、多电“踢”与暴力枚举优化架构规划

2.0. 分配器和能将请求分割的人

在多电梯调度里，我们遇见的第一个问题就是可能一个电梯无法把一个请求直接运到目的地，这就需要我们将这个请求分割，让多个电梯共同处理，我们也会遇到这样的问题：可能有多个电梯同时能处理一个请求，那么让谁来处理这个请求最好呢？这种分配请求不免让我们想把一开始的针对楼层的分配与之相结合——我就是这么做的：一个分配器。

同时我们需要能有中间层的“人”类，这样我们就话不是简单的将一个请求分割成两个了，而是一个请求能有动态的完成阶段。这同时也是为我们未来的动态规划做准备。

2.1. 电“踢”与动态分配

因为想要枚举各种事件的走向需要考虑要素过多不易考虑，而且三部电梯必须协同实现优化，难度又更上一层楼。所以我使用了一种比较省事的方法，在每次电梯开门时触发这一层电梯内外所有人的重新分配。

我的实现方法依赖于分配器的实现，一个可以随时将任何请求按照当前情况重新分配的分配器，他同时担任着重新分配器的角色。每当我的电梯开门，就会触发一次踢人操作，将所有当前楼层的人踢入分配器中然后由其重新分配，以此使每个请求分配针对的时机相较于开始有了更新，达到了片面的动态分配。

2.2. 搭配暴力枚举分配方案食用更佳

时常在想，怎样的分配方式才算是最好的分配。往往这种思考会以CPU过热无法继续而告终。最后的结论是，个性化的分配是最适的分配，既先对不同楼层分类，然后针对不同分类间的From-To关系进行枚举分配，这样既不容易遗漏情况，也有一个针对性的优化策略。

三、写在最后

在本单元作业我发现，没有哪种优化策略是完美无缺的，性能好坏是放在了某种特定的请求投放情况下而谈的。所以优化只是锦上添花，真正我们应该关心的，是我们的架构。

巴特西