优化座位编排算法思考过程

绝地灬酷狼 2022-05-31 02:26 79阅读 0赞

**座位编排算法**

**任务**：提高座位利用率，优先代码结构。

**问题描述**：在实际考试的机房中，存在大量考试机未被使用的现象。造成物力人力的不合理。

**挑战：座位编排算法复杂，代码结构不清晰，代码量接近1万行（十年前写的）。因为本算法是公司最难的一个算法。所以想要读懂这个座位编排算法本身就有难度。**

### 思考方向 ###

1，可以自行设计一个更好的算法实现座位编排。

2，可以在已经有的基础上优化，优化方向尽可能提高座位利用率，根据其算法思想，重新组织其类关系，使其结构清晰易懂。

### 自己是怎么做的？ ###

#### 先理解整个背景知识。 ####

1，有两种排座的方式机考和纸考。策略有自动编排和手动编排，其中手动编排是对自动编排的一个有力补充，目的也是为了提高座位利用。

2，编排规则有同单位隔离，同专业隔离，同单位和同专业隔离。隔离（前后桌满足这个要求就会被隔离）。

3，优先规则有考生报满四科先排座。按照专业优先排座。按照身份号排座（给考生的身份证号排个序列）。

4，地区范围限制。考区，考点，考试场地，试室（某个考点下从第二试室到第八试室进行排座，目的也是尽可能提高座位使用率）。

5，考生范围限制，这些考生是哪个考区的，又是哪些考点的。（目的也是提高座位利用率）

6，这个功能是开放给各个考点的，由考点的管理员使用。

#### 学习并分析 ####

1，准备300个考生的基础数据，进行自动座位编排，debug方式进行理解学习。

2，整理出整个类图及其相应关系。在National Rose工具中画出所有类图关系，理解每一个类的字段属性和类的方法。当然命名上的不规范或者摸棱两可是存在的。很是苦恼。也从此懂得了一个好的命名甚至比算法和代码结构更为重要。

3，分析其算法实现的思想。上万行的代码dubug一次会花费很多时间。

4，理解其算法实现过程，本身就有一定难度，但是最终还是理解了（只能说是读懂了而已），就是花费了很多的时间和精力。加班，但是不给加班工资。

### 最终决定做什么？ ###

我选择在已有的算法基础上进行优化，因为并没有想出更好的实现方式。原有的实现方式也在生产环境上跑了10多年，想必是非常稳定和值得学习借鉴的。

### 优化的点。 ###

自动编排处，增加试室范围方式。

手动编排处，查询出有且只有满足查询条件的场次的考生。

设计其部分类图关系和移动一些方法到相应的类中，提高代码的整洁度和降低代码理解的难度。

#### 针对已经有的算法实现过程。分析出其缺陷。 ####

1，类的命名不规范。或者见名并不知意。

2，字段名不规范，还出现拼音的方式。

3，合适的方法并没有出现在合适的类里。

4，大量使用构建器方式进行获取对象。当然也有三处是使用单例模式的getInstance()方法获取对象。

5，代码弹性不好。设计其类图及其关系，字段名称及方法。但是还是使用其原有的算法思想，只是重新组织了代码结构，让其能够清晰易懂。

![SouthEast][]

### 说明自己增加了些什么。 ###

1，把原来的单一试室选择修改为范围性的试室选择。

2，在手动编排处，原来：查询出满足场次一的考生，是只要报了的科目存在场次一都会被查询出来，对提高座位利用率根本没有任何作用。修改：查询只报了场次一的考生，并支持多个场次查询。实际情况是，一个专业是四个科目，一个科目对应一个场次。但是查询的时候，需要传入合理的场次信息。12个场次（总是4的倍数）。分成1234是一组，5678是一组，9101112是一组。在js处写算法实现合理的场次（当我勾选场次一的时候，5678，9101112都会被置灰）。这个是一个小算法。可以先想想如何实现，然后学习一下，你们的更简洁思路。要简洁哟。

![SouthEast 1][]

3，把原来的编排规则，采用面向接口的方式进行编程，利于扩展。

![SouthEast 2][]

4，把原来的所有基于构建器的方式修改为静态工厂方法。（思路来源:《Effictive Java》的条目一）。

5，把原来的方法的多参数修改为builder方式。（思路来源：《Effictive Java》的条目二）。

3，多态的方式取消原来的if  else  语句。

### 成果 ###

1，满足生成环境的座位编排功能，管理员自动编排然后使用手动编排对单个不合理的考生占座位进行移出移入，提高了座位利用率。

2，贡献了一张整理的类图，而类图就表达了一切。我相信后面的维护此功能的人会更加愉悦。所以做这一件事情是非常有意义的。

3，代码结构清晰易懂。

4，收获，提高了对命名的认识深度，提高了代码阅读能力，提高了理解力。基础知识的运用更加熟练。也认识到复杂的东西，只要足够耐心和努力也是可以攻克的

#### 核心类设计 ####

![SouthEast 3][]

[SouthEast]: /images/20220531/6dc3dac237804b15a685fcc0d3ff91bd.png
[SouthEast 1]: /images/20220531/cddb6f3f3c064d3c9986fccdd48d820b.png
[SouthEast 2]: /images/20220531/998134a01bdd4d1997870671af350927.png
[SouthEast 3]: /images/20220531/e214cff085524685bf632b157021ba57.png