这是一个业务上遇到的真实场景。
我们定义了一个配置文件格式，给机器资源分类。
写出来大概是这个样子
GroupA: MachineA, MachineB, MachineC
GroupB: MachineD, MachineE
GroupC: MachineA, MachineC
GroupD: GroupB & GroupC
......
总结一下， 有如下几个规则:
- Group的名字和Machine的名字都由用户自己指定
- Group的描述可以是一组机器(见上图GroupA, GroupB, GroupC)， 也可以是其它Group的运算表达式(见上图GroupD)
- 表达式支持'&', '|', '-' 三种运算符, 分别代表集合运算中的交集，并集，差集
- 表达式不能包含括号， 计算的时候按照从左到右的顺序
问题来了， 当我们拿到这么一份配置文件的时候，需要知道每个Group包含多少机器，请问如何编码实现？
这个问题乍一看很简单，如果Group的描述本身已经是机器组，直接计算Machine的数量即可。 如果Group的描述是表达式， 则把表达式中出现的Group用机器组替换一下，再求数量也行啊。 难点在哪呢？
关键就在替换这里， 我们看下面一个场景
GroupA: GroupB & GroupC
GroupB: GroupD | GroupE
GroupC: MachineA, MachineB
GroupD: GroupA & GroupE
GroupE: MachineC, MachineD
读者朋友可以自己试一试用代换法求解GroupA, 然后很快就会发现"臣妾做不到啊"，原来， A引用了B，B引用了D， D又引用了A， 形成了死循环。 也就是说这个配置文件本身就是错误的， 但是如果我们的代码不能检测到这种错误，就会导致因为用户的错误配置造成系统死循环， 多么可怕啊。
怎么检测死循环呢， 其实也不难， 仔细想一想，这其实就是一个有向图环检测问题(如果不理解，可以参考笔者的另一篇文章--业务模型抽象成有向图环检测算法，模型和这个很像)。
这样做是解决问题了，但是算法写起来好复杂，有没有简单点的方法呢？
其实笔者当初实现的时候也是按照上述的方法解决的，但有一天整理这段代码时发现了，根本不用这么复杂好嘛！转换一下思路， 调整一下展开表达式的顺序就解决了, 解法如下:
- 遍历所有的Group, 把所有只需要一层展开的表达式 转化成 Machine List(一层展开指的是表达式中引用的Group均为确定的Machine List)
- 重复步骤1，如果在整个遍历过程中，没有新的表达式被展开， 说明遇到了死循环，流程终止。 如果所有的表达式都被展开， 说明问题解决。
是不是变简单了，这种做法连死循环都不需要检测了。其实，事后想一想，这算法并没有什么难度(甚至小学生都会，因为这就是数学中的多元一次方程啊)，只是在一种思维遇到困难的时候，我们往往可以跳出思维定式，找到简洁之道。
网友评论