发表更新课程相关21 分钟读完 (大约3224个字)

OO_U2 - HW5,6阶段性总结

前言

我的调度算法，与我的架构实现耦合度较高，因此我不得不先提一些我自己的电梯实现；不需要的同学，欢迎直接跳开“电梯实现”部分。

这算是本人两周以来的一个总结吧，终于有时间写了…

浅提电梯实现

读前注意，本人的设计并非最佳，其中有不少会引起复杂度增加的设计，请各位参考时务必谨慎。

概况

在完成HW6后，本人的整体架构如下：
Pasted image 20250406221034.png

其中，电梯信息与电梯运行进程分离，便于维护。

我的电梯，将运行状态分为以下几类：

  • IDLE：闲置，此处与常理理解中的闲置是一致的，不多赘述
  • RESERVED：预约，在闲置状态的电梯，收到起点与电梯当前所在位置不同楼的请求时，进入的移动状态。
  • RUNNING：运行，电梯处在非预约状态时的正常移动状态。
  • WAITING：等待，电梯停靠，进行上下客时进入的状态。停靠完成后，视情况转入RUNNING/RESERVED/IDLE状态。

同时，我们还需要记录电梯的运行方向，现规定：

  • 1：上行
  • -1：下行
  • 0：仅在进入IDLE时设为此值。
  • 在电梯进入WAITING时，方向将被设置为下一步要移动的方向

电梯内亦有一子请求表，记录满足以下条件的请求：

  • 请求与电梯运行方向一致
  • 记录当前方向的所有请求；比如，我们的电梯正在处理一个F1-F3的请求，现在处于F2；此时，若有一F4-F5的请求，则该请求可被指派给电梯，加入子请求表

存储状态的额外信息

上面提到，我们的子请求表只允许同向请求加入；在我们现在的实现下，这种情况当然会产生：

  • 电梯在F3，IDLE
  • 出现了一个F1-F7的请求，电梯进入RESERVED，空放到F1
  • 电梯从F3空放去F1途中出现一个F2-F1的请求，我们自然希望捎带它，将其加入子请求表

也就是说，空放方向与发出预约的请求的方向反向。 我们自然需要一个地方暂存这个预约请求；我选择通过继承的方法，将其存在状态内。

具体而言：

  • 上面四个状态均属于一个Status类，内有一enum Type属性，记录当前状态类型
  • 若一个状态需要记录额外信息，则该状态作为Status的子类，额外信息作为子类的属性，存在子类中。

我们此时只需对RESERVED，WAITING两个状态记录额外信息。

RESERVED：

  • allowPickUp：中途是否允许捎带
  • requester：进行预约的请求。允许为null。

WAITING：

  • prevStatus：进入WAITING前的状态。

欲知为何如此，请继续看下文。

兼容SCHE请求

不知各位是否发现，在HW6引入的临时调度，跟我们上面提到的RESERVED略有相似之处？

我们要让我们的现有设计兼容SCHE请求，只需做这么几件事情：

  • SCHE-BEGIN前，把途中无法捎带的请求赶回请求池；
  • 在临时调度至不同层时，SCHE-BEGIN对应转入一个 requester = null，不允许捎带的RESERVED状态
  • 确保已有的RESERVED状态下的电梯运行规则，能够处理上述的RESERVED情况

就这样，我们就做完了SCHE请求的电梯运行部分；剩下的，只需要实现指派电梯进RESERVED的逻辑，很省事吧！？

等待状态的转移规则

WAITING的状态转移规则如下：

  • 先前为RUNNING：
    若仍有请求未到终点，则恢复RUNNING
    若请求已全部满足，则进入IDLE
  • 先前为RESERVED：
    若未到预约者起点，则恢复RESERVED
    若到达了预约者起点，则进入RUNNING，同时将暂存的请求加入子请求表
  • 先前为IDLE：
    直接进入RUNNING，
    因为我们保证，IDLE下的电梯被预约后，直接进入RESERVED状态，
    此时必是因为，有一起点与IDLE状态下电梯所在位置的请求被分给了电梯。

调度算法

交互方面，我采用的是一Dispatcher对多个Elevator的实现，与绝大多数做法一致。

大家都知道影子电梯，不过它需要模拟电梯的整个运行过程，实现略显复杂；那么，有没有一个在复杂度和影子电梯的高效率之间折中的方案呢？

是有的。我的这个策略在思路上与影子电梯有颇多相似之处，只不过：

  • 只需要计算（模拟）当前请求的运行时间
  • 已指派给电梯的其它请求的估计，利用优先级机制实现

是否允许加入

进行计算之前，Dispatcher需要得知当前正在评估的电梯，能否接受当前待加入的请求。

可加入的规则如下：

  • 若电梯此时在IDLE状态下，直接允许加入，否则进行下述流程
  • 请求方向需与电梯当前运行方向一致；方向有关的说明见上文。
  • 电梯同向，且电梯此时没有超过请求的起点
  • 如果状态为（RESERVED）/（WAITING，且前一个状态是RESERVED），则：
    RESERVED状态需允许捎带
    若预约请求方向与当前运行方向相反，则待加入请求的终点不得超过预约请求的起点
  • 加入后，不会出现电梯满员的情况

“电梯满员”视个人实现不同，判断逻辑可能不同；我这里就以我的实现为例，谈谈我的判断逻辑。

正如上文所述架构实现，我们一个电梯的子请求队列不仅包含了当前在电梯内的请求，还包含了将来电梯要捎带的请求；

我们的判断逻辑是，假设请求加入了子请求表，得出各楼层处，最多同时出现的请求数；

这一“同时出现的请求数”，反映了那一运行区间内，电梯内的人数。

若各区间的同时出现请求数的最大值，大于电梯容量，则认为此时加入请求会导致超员。

Pasted image 20250406214224.png

如图所示，待加入请求在F2-F3区间会导致超员，故我们不应加入这一待加入请求。

需要注意的是，如果采用了上文RESERVED状态的实现，若预约请求方向与电梯空放方向一致，此时还需将预约请求放进上面的图里进行比较。

计算评价指数

在上述复杂的判断后，我们终于可以开始计算了…

我们的计算公式如下：

$$index = index_{base} + priorityPenalty * elevStopTime$$

$index_{base}$

我们先需要得知：

  • $dis$：电梯所在位置，与请求起点的楼层数
  • $travel$：请求跨越的楼层数
  • $stopCount$：请求沿途需要停靠，以让自己进电梯/捎带其它请求；stopCount即中途停靠的次数

随后即可算出当前请求的运行时间，作为我们评价指数计算的第一步；

$$index_{base} = (dis + travel)*elevSpeed + stopCount * elevStopTime $$

$priorityPenalty$

优先级惩罚，是所有请求的优先级惩罚之和：

$$priorityPenalty = \sum_{i=1}^{n}{penalty_{R_i}}$$

对于一个请求$R$，设其优先级为$priority$，楼层跨度为$travel$，则我们规定该请求允许的中途停靠次数$maxAllowedStops$如下：
$$maxAllowedStops = round(travel * (1 - \frac{priority}{100}))$$
其中，$round(x)$取$x$最靠近的整数。

在我们进行评价指数的计算时，我们先假设待加入请求已被加入；随后，对原有的请求$R_i$，算出加入后的总停靠次数$stops$。

  • 若$stops <= maxAllowedStops$：$penalty_{R_i} = 0$
  • 否则：$penalty_{R_i} = (stops - maxAllowedStops) * priority$

小总结

由此，我们就可以算出各个（可加入请求的）电梯的评价指数，选择评价指数最低者加入。

上述是一个相对简单的模型，相信各位有更好的实现。

评测方案

我选择构建评测机框架，留出随机数据生成器（dataGen）与正确性检查器（Checker）的接口。这样有利于提高不同题目下评测的灵活性。

评测机框架方面，我构建了一个可以评测多程序、多测试点的多线程评测机，按照以下两种策略运行：

  • 测试深度优先：评测机优先对一个待测程序，测试多个测试点
  • 测试广度优先：评测机优先对一个测试点，测试多个程序

评测机框架建议允许添加数据生成器生成的数据以外的数据，从而为人工构造高强度数据提供可能。

运行测试程序方面，我选用了Python的subprocess库，其中的POpen方法十分有用，不仅可以指定子进程的工作目录，还可重定向子进程的输出。

注意到，我们的数据投喂器读取的是**当前工作目录下的stdin.txt**；因此，我们可以通过指定不同工作目录的方法，来让投喂器同时测试多个样例。

随后，我们即可使用数据投喂器+打包好的.jar进行评测；两个子进程需要用管道串起来，实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
input_process = subprocess.Popen(
                ['input.exe'],  # input.exe 读取当前目录的 stdin.txt
                cwd=case_dir,    # 设置工作目录为测试用例目录
                stdout=subprocess.PIPE,
                stderr=subprocess.DEVNULL,
                text=True
            )

java_process = subprocess.Popen(
                ['java', '-jar', os.path.join(target_dir, jar_file), f"-Xmx{memLimit}"],
                stdin=input_process.stdout,
                stdout=fileout,
                stderr=fileerr,
                text=True
            )

据闻Python的psutils库有办法记录CPU使用时间，不过我的尝试没有成功，希望做过尝试的同学多多分享经验:P

我两次作业的随机数据生成器与Checker均先由AI生成，再由人工进行细节修改。

注意到，AI生成的Checker并不完全准确，在HW6时这一问题尤为显著，需要多处人工修正；在寻求AI工具的帮助，节省时间的同时，请务必仔细检查AI生成的工具是否能如预期般工作。

之前写过的一些总结

总结

  • 本单元，我感觉最需要的其实是细心，不然线程间交互很容易出现问题。

  • 架构设计同样起到了关键的作用。本人架构中RESERVED状态的抽象，大大节省了本单元的开发时间。

    我认为，只要架构：

    • 易于维护；
    • 复杂度低（可以归进上条）；
    • 运行效率在可接受范围内；

    就可以算一个好设计。

    不过，我自己不得不承认，我本单元架构在不少实现细节上的复杂度实在太高，因此带来的BUG与维护的不便不在少数。

  • 本单元亦让我直观地感受到了算法和数学模型，于程序的重要性何在。

    本人实现中，判断电梯是否满员的问题，可以抽象为计算一个二维空间内，所有线段的最多重叠次数；没有算法的帮助，计算效率很难提升。

    处理优先级问题的方法，其实就是简单的数学建模。

  • 感受到了AI的力量。使用AI生成checker+人工修改的效率，远比纯手搓要高。

OO_U2 - HW5,6阶段性总结

http://lajipz.top/2025/04/17/OO_U2 - HW5,6阶段性总结/

作者

LajiPZ

发布于

2025-04-17

更新于

2025-04-21

许可协议

#

评论

×