之前在这篇文章:基于班级条件权重表的试探性学生分班算法(详解篇)中介绍过分班算法的理论步骤。

分班算法设计仅仅是给出了一个大致的思路。

其实算法中的很多步骤在实现过程中是可以进一步优化的。

本篇文章记录一下我在实现分班算法的过程中,进行的一些优化,主要包括以下几方面:

1. 单一条件分班时采用循环算法得到最优解
2. 可配置的权重系数计算规则
3. 增加redis锁防止重复分班
4. 引入线程池将分班过程多线程化


单一条件分班时的特殊处理

单一条件分班其实是一种特殊的分班情况,这种情况下的分班结果是有最优解的,达成最优解的分班方式就是将所有学生按照分班条件排序,然后循环分班。

举个简单的例子来说明:
假设有6个学生,3个班级,每个班级分配两人。
由于是单条件分班,那么可以假设这个6个学生条件对应值分别为:a,b,c,a,d,b
首先将学生按照条件进行排序,升序和降序都可以,因为排序的目的只是为了属性相同的学生挨在一起,这里采用升序进行排序:a,a,b,b,c,d
接下来进行循环分班,循环分班的意思就是将第i(i属于0~n-1,n为学生总数)个学生,分配到第i%m+1个班级(m为班级总数)中去

  1. 第0个学生a,0%3+1==1,即分配到第1个班级
  2. 第1个学生a,1%3+1==2,即分配到第2个班级
  3. 第2个学生b,2%3+1==3,即分配到第3个班级
  4. 第3个学生b,3%3+1==1,即分配到第1个班级
  5. 第4个学生c,4%3+1==2,即分配到第2个班级
  6. 第5个学生d,5%3+1==3,即分配到第3个班级

分班完成后,每个班级的学生情况:

  • 1班学生:a b
  • 2班学生:a c
  • 3班学生:b d

可以看到这种分班过程是能够得到一个最优分班结果的。

并且这种分班方式的效率很高,无需进行比较,只需挨个把学生放入不同的班级即可。

因此我在实现分班算法的过程中,增加了额外的判断,当发现用户配置的分班条件只有一个时则直接进行循环分班。


权重系数计算规则的扩展性

第二个优化的点则是关于每个条件的权重系数计算规则。

在算法设计的文章中我提到过,由于条件是存在优先级的,因此需要使用权重系数的概念来体现条件的优先级。

最基础的权重系数就是取规则的反序(取反序的原因是因为在我设计的算法中,权重值越大则代表班级中与当前学生属性重合的人数越多)。

但是权重系数的取值其实是有现实意义的(具体见我算法设计文章中3.5.1节的介绍),如果只取规则的反序的话,可能有时并不能特别好的体现规则间的优先级。

因此我在算法的实现过程中,将权重系数的计算规则抽取出来放入配置文件中,并提供了三种档位供用户选择,一档取规则的反序,二档取规则反序的两倍,三挡取2的规则反序次方,档位越高则代表规则间的优先级体现越强,可以更好的保证在分班过程中先满足优先级高的规则,再满足优先级低的规则。


分班时增加redis锁

虽然从业务角度来看,分班操作不会存在并发问题,因为基本只有管理员才有权限使用这个功能。

不过由于我们系统是支持多用户以及多角色的,因此为了避免多个管理员用户同时进行分班而可能造成的数据库冲突,我增加了用来控制并发的redis锁。

具体的方法是利用redis中的 setnx key value 命令,该命令的作用是将 key 的值设为 value ,当且仅当 key 不存在。设置成功返回 1,设置失败则返回 0。这也是利用redis实现分布式锁的常见方法。

当某个管理员用户进行分班操作的请求发到服务器后,首先读取数据库判断是否已经分班完成,如果尚未分班,则执行setnx尝试获取锁,如果返回值为1则代表拿到了锁,然后进行分班操作,分班完成后进行相关的数据库更新,之后将之前setnx设置的key值从redis删除,即释放锁。

如果在该用户进行分班的过程中,另外一个管理员的分班请求也发到服务器上了(不一定是同一个服务器,可能是集群中的其他服务器),此时进行setnx操作会得到返回值0,这代表有别的用户已经提前执行了分班操作,这个时候向客户端返回一个提示信息即可。


采用多线程分班以提升效率

其实我平常写的代码用到多线程的机会很少,因此一开始在实现分班算法的时候,并没有想到用多线程来进行分班操作。

由于上一个班的分班算法是纯sql实现的,利用了数据库的效率,因此执行速度很快。而我实现的版本虽然分班的结果比上一版本的好了,但是分班的执行时间也变长了。

因为我的算法复杂度确实会高一些,而且分班的过程是按照专业来划分的,每次轮到新的专业分班时,会首先进行数据库的查询,获取该专业下的班级以及学生信息,然后才开始执行分班,所以比起之前的版本慢了很多,大概用户点击分班按钮之后需要等到2到3秒钟才能分班完成,而之前的版本则是感觉瞬间就分完了。

为此我还专门为分班操作写了一个异步的loading动画,避免用户觉得页面卡顿。

但我之后某天突然反应过来,我设计的分班算法是一个典型的CPU密集型的程序(因为大部分时间实在内存进行可选班级的判断),那么提升CPU密集型的程序执行效率的最好方式就是最大程度地利用服务器的多核cpu。

而由于不同专业之间的分班其实是互不影响的,每个专业的分班过程就可以抽成一个独立的线程来完成,比如在等待B专业的学生数据加载时,cpu可以去已经加载完学生数据的A专业进行分班,这样就能大大提高分班效率。

但是引入多线程也将会带来一些问题:

  1. 由于数据库访问的daoExcutor对象是基于spring的IOC的,而每个专业分班线程都需要依赖daoExcutor去访问数据库,请求该专业的学生数据,但是分班线程肯定是需要多例的,因此需要想办法使得分班线程能够持有springIOC中的daoExcutor对象。

  2. 一个学校的专业可能有上百个,如果每个专业都起一个线程是否线程数太多占内存不说还会带来额外的线程切换开销,是否要考虑线程池的引入。

  3. 如果引入线程池,那么要考虑线程池的创建开销是比较大的,每次来一个请求就新建一个线程池是不是不合理,是应该提前用单例模式初始化好线程池常驻内存,还是来一次请求初始化一次,然后gc释放内存空间。(分班请求不是一个访问频率很高的请求)

  4. 线程池的默认线程数问题。

上述这些问题的解决方法:

  1. 需要创建一个@Component实例,名称为ClassDivideThreadProvider分班线程提供器,在这个@Component中,自动注入appContext,daoExcutor作为该类的静态对象,然后该类提供一个create方法,参数接收一个专业代码,返回一个ClassDivideThread分班线程对象。
    在create方法中,使用专业代码和daoExcutor查询出该专业下的学生数据,传递给ClassDivideThread分班线程的构造函数,于是一个拥有学生数据的分班线程就创建好了。
    注意,分班线程一定是一个Callable对象,在分班线程中实现分班算法divide(List),然后覆盖call方法,call方法调用divide方法,返回一个List,StudentWithClassId对象持有学生id和班级id,代表这个学生被分配到了哪个班级。

  2. 关于分班线程池的创建开销问题,可以考虑3种方案:(1)直接利用枚举实现完美的单例,但是由于枚举类其实本身是继承了Enum的一个子类,在Enum的静态代码块中会进行枚举量的初始化,因此使用枚举实现的单例是饿汉模式,这使得在服务器启动时,类加载过程就执行了线程池的初始化操作。(2)也可以利用volatile关键字加双重检测机制实现懒汉模式单例,这样的话只有当第一次分班请求出现时,才会初始化线程池。(3)不再使用单例模式创建线程池,而是每次请求到来时,创建一个局部线程池变量,用完就等待被gc,这样虽然增加了执行时间,但是节省了内存空间。

  3. 关于线程池大小的问题,为了更好的利用服务器的多核计算,使得每个核都能同时执行一个线程,并且线程数不会太多,避免线程所占内存空间过多以及线程间切换的开销,那么最好将线程池的corePoolSize设置为服务器cpu核数一样。所以可以用一个配置文件寸放服务器核数,默认为8.

发表评论

电子邮件地址不会被公开。 必填项已用*标注