电梯优化奇技淫巧

多线并行，多策略竞争

此处 特意感谢 lsj 霸霸提出的这一神奇思路，我只是把这个想法变为现实。

很惭愧，只做了一点一点微小的工作（端起茶杯）

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

一、提出背景

已知的各种算法都有各自的局限性

  1. ALS 在处理大多数情况的时候效果明显差于 Look ，但是ALS，在面对

    1-FROM-1-TO-3

    2-FROM--2-TO-3

    3-FROM-10-TO-15

    这种情况的时候，反而会因为它 先来先选 的沙雕策略比 Look 折返路程更少。

  2. 贪心算法在面对精心构造的数据的时候可能会被来回 放风筝 这是 坠痛苦的 。

防止互测被卡TMax

指导书最开始并没有禁止互测通过针对对方算法构造一个极具针对性的数据点。

个人看法是，针对一个多数情况下较优的算法，通过一个很极端的例子，去卡爆对方性能，获取hack分数

是有点缺德的。同时这个所谓的Bug还难以修复。

开发这个多策略的 初心 是防止自己的程序出现在极端情况下慢于纯ALS的情况。

前三次的经验积累

第二次和第三次作业当中，我的一些优化算法，可能在某些情况下出现负优化，于是我需要根据判断

优化前后的字符串长度取舍本次的优化。 于是lsj julao提出能不能在此处根据时间取舍优化，并初步提出了

多电梯并行的操作。

二、实现

大体思路

多策略可以理解为一种在 算法选择 层面的贪心，整体思路如下

  • 开多个电梯线程，这些电梯线程不同于第三次作业的合作关系，他们不仅算法不同，且他们之间的运行是完全独立的。
  • 主线程获取新的请求，把这个请求给每个电梯线程各分配一次。
  • 各个线程把自己的输出 重定向 到一个缓冲区中，这里我用的是官方输出接口自带的一个指定PrintStream的重载，把输出重定向到一个ByteArrayStream 当中。
  • 设置设置一个输出类，这个输出类有一个静态锁，用于保证全局输出的线程安全。最先执行完所有请求的线程获得这个静态锁，把自己缓冲区内的数据全部输出出来，并通过一些标记之类的东西阻止其他线程也进行输出。 之后直接exit(0)用最暴力的方式结束程序。

部分源码

主线程

public class ElevatorSystem {
    public static void main(String[] args) {
        GlobalPermission permission = new GlobalPermission();

        Rail rail0 = new Rail(16,3);
        Rail rail1 = new Rail(16,3);
        Rail rail2 = new Rail(16,3);

        Dispatcher dispatcher0 = new Dispatcher(rail0,permission);
        Dispatcher dispatcher1 = new Dispatcher(rail1,permission);
        Dispatcher dispatcher2 = new Dispatcher(rail2,permission);

        dispatcher0.addSillyElevator();
        dispatcher1.addLookElevator();
        dispatcher2.addAlsElevator();

        ArrayList<Elevator> elevators0 = dispatcher0.getElevators();
        ArrayList<Elevator> elevators1 = dispatcher1.getElevators();
        ArrayList<Elevator> elevators2 = dispatcher2.getElevators();
        TimableOutput.initStartTimestamp();
        permission.systemStart();
        Thread elevator0 = new Thread(elevators0.get(0));
        Thread elevator1 = new Thread(elevators1.get(0));
        Thread elevator2 = new Thread(elevators2.get(0));
        elevator0.start();
        elevator1.start();
        elevator2.start();

        ElevatorInput elevatorInput = new ElevatorInput(System.in);

        while (true) {
            PersonRequest request = elevatorInput.nextPersonRequest();
            if (request == null) {
                permission.systemQuit();
                try {
                    elevatorInput.close();
                } catch (Exception e) {
                    e.printStackTrace();
                }
                break;
            }
            try {
                // 每拿到一个新的请求，把这个请求给每个电梯各分配一次
                dispatcher0.getBuffer().put(request);
                dispatcher1.getBuffer().put(request);
                dispatcher2.getBuffer().put(request);

            } catch (Exception e) {
                e.printStackTrace();
            }
        }

    }
}

输出辅助类

我把缓冲区以及最后的带锁输出方法封装到了一个OutputHelper类中，每个电梯都自带一个OutputHelper对象

public class OutputHelper {
    private static boolean hasOuput = false;
    private ByteArrayOutputStream storeStream = new ByteArrayOutputStream();
    private PrintStream stream = new PrintStream(storeStream);

    public static synchronized void output(OutputHelper helper) {
        if (!hasOuput) {
            helper.finalOutput();
            hasOuput = true;
        }
    }

    public void println(String string) {
        TimableOutput.println(string,stream);
    }

    public void finalOutput() {
        Scanner scanner = new Scanner(storeStream.toString());
        while (scanner.hasNextLine()) {
            System.out.println(scanner.nextLine());
        }
    }
}

电梯运行线程

public void run() {
        dispatcher.updateRequests();
        while (this.hasMoreWork()) {
            dispatcher.updateRequests();
            ElevatorOrder order = getOrderAndUpdateBuffer();
            dispatcher.updateRequests();
            executeOrder(order);
        }
        // 任务执行完毕，开始输出
        OutputHelper.output(helper); // 输出！
        System.err.println(scheduler); // 输出“优胜者”的信息，便于统计算法性能
        System.exit(0); // 暴力关程序
    }

强测运行效果

根据本人利用err流输出的统计信息，在强测数据中，本人的高分数据点（95+）的最优策略包含了本人使用的三种算法，可见这种多策略对性能的提升是很大的。

当然，在这里我必须得膜那些用单策略但是性能分高于我的dalao，三个算法比不过对方一个算法，哭哭。

方法两个优势

  1. 较为简单地大幅度提高性能
  2. 可以规避掉自己某一算法中出现疯狂怼门、电梯摸鱼的Bug。 因为这种情况，电梯一定无法完成任务，那么他们一定无法输出，那么正确执行的电梯就会掩盖这一错误。

三、更多的拓展（事后孔明）

动态地改变所采用的算法

此方法出自shh，但是他摸了，没去实现，哭哭。

这里大概讲一下shh的思路。

我们之前所说的多策略都是每个线程给定一个算法，然后取最优。

如果遇到一下这种情况，这个方法的效果可能会大打折扣

  • 请求具有明显的阶段性
  • 不同阶段的请求的特征明显适合不同的算法

那么这样子看来，我们的多策略还是不够 窝窝电梯优化 随笔

于是，shh提出了根据每固定执行步数给各个算法打个分，然后调整算法的操作。

（反正我是不会实现的，哭哭）

加入评测机检验自己的输出

前文我们提到，多策略在其中一个线程因为bug而陷入长时间无法运行的状态时，一般不会输出错误。

因为那个bug线程一直摸鱼，无法输出，就会使得正确执行的线程可以输出。

那么，这就带来另一个问题 如果一个线程因为Bug，执行错误地线程最先结束，那么输出将会是错误的。

这里，我们就可以把自己评测机的评测模块加进来，对我们自己的输出结果进行检验。

如果是正确的输出，则正常输出并结束程序，如果不是正确数据则等待下一个可以输出的线程，直到等到第一个正确的输出。

此外如果担心自己电梯出现异常的问题，可以try-catch一下，如果有异常就失去输出的权力。

这样，就可以大幅度降低自己程序出错的概率~

用于统计各个算法的执行效果

在第三次作业中，我需要统计为三部电梯选择合适的控制算法。

于是我通过根据三部电梯的任务特征生成针对性数据，通过运行多策略电梯统计各个策略的效果。

最后根据统计结果为三部电梯的调度策略做出调整。

更多sao东西，还未发现，哭哭

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄