這是一個業(yè)務上遇到的真實場景矮冬。
我們定義了一個配置文件格式宗雇，給機器資源分類插爹。
寫出來大概是這個樣子
GroupA: MachineA, MachineB, MachineC
GroupB: MachineD, MachineE
GroupC: MachineA, MachineC
GroupD: GroupB & GroupC
......
總結一下炼彪， 有如下幾個規(guī)則:
- Group的名字和Machine的名字都由用戶自己指定
- Group的描述可以是一組機器(見上圖GroupA, GroupB, GroupC)已慢， 也可以是其它Group的運算表達式(見上圖GroupD)
- 表達式支持'&', '|', '-' 三種運算符, 分別代表集合運算中的交集，并集霹购，差集
- 表達式不能包含括號佑惠， 計算的時候按照從左到右的順序
問題來了， 當我們拿到這么一份配置文件的時候齐疙，需要知道每個Group包含多少機器膜楷，請問如何編碼實現(xiàn)？
這個問題乍一看很簡單贞奋，如果Group的描述本身已經(jīng)是機器組赌厅，直接計算Machine的數(shù)量即可。 如果Group的描述是表達式轿塔， 則把表達式中出現(xiàn)的Group用機器組替換一下特愿，再求數(shù)量也行啊。 難點在哪呢勾缭？
關鍵就在替換這里揍障， 我們看下面一個場景
GroupA: GroupB & GroupC
GroupB: GroupD | GroupE
GroupC: MachineA, MachineB
GroupD: GroupA & GroupE
GroupE: MachineC, MachineD
讀者朋友可以自己試一試用代換法求解GroupA, 然后很快就會發(fā)現(xiàn)"臣妾做不到啊"，原來俩由， A引用了B毒嫡，B引用了D， D又引用了A幻梯， 形成了死循環(huán)兜畸。 也就是說這個配置文件本身就是錯誤的， 但是如果我們的代碼不能檢測到這種錯誤碘梢，就會導致因為用戶的錯誤配置造成系統(tǒng)死循環(huán)咬摇， 多么可怕啊。
怎么檢測死循環(huán)呢煞躬， 其實也不難肛鹏， 仔細想一想，這其實就是一個有向圖環(huán)檢測問題(如果不理解，可以參考筆者的另一篇文章--業(yè)務模型抽象成有向圖環(huán)檢測算法龄坪，模型和這個很像)昭雌。
這樣做是解決問題了，但是算法寫起來好復雜健田，有沒有簡單點的方法呢调鬓？
其實筆者當初實現(xiàn)的時候也是按照上述的方法解決的盖灸，但有一天整理這段代碼時發(fā)現(xiàn)了，根本不用這么復雜好嘛！轉換一下思路仗处， 調整一下展開表達式的順序就解決了, 解法如下:
- 遍歷所有的Group, 把所有只需要一層展開的表達式 轉化成 Machine List(一層展開指的是表達式中引用的Group均為確定的Machine List)
- 重復步驟1党饮，如果在整個遍歷過程中即彪，沒有新的表達式被展開奶卓， 說明遇到了死循環(huán)，流程終止存炮。 如果所有的表達式都被展開炬搭， 說明問題解決。
是不是變簡單了穆桂，這種做法連死循環(huán)都不需要檢測了宫盔。其實，事后想一想享完，這算法并沒有什么難度(甚至小學生都會灼芭，因為這就是數(shù)學中的多元一次方程啊)，只是在一種思維遇到困難的時候般又，我們往往可以跳出思維定式彼绷，找到簡潔之道。
