這是一個(gè)業(yè)務(wù)上遇到的真實(shí)場(chǎng)景。
我們定義了一個(gè)配置文件格式，給機(jī)器資源分類。
寫出來大概是這個(gè)樣子
GroupA: MachineA, MachineB, MachineC
GroupB: MachineD, MachineE
GroupC: MachineA, MachineC
GroupD: GroupB & GroupC
......
總結(jié)一下， 有如下幾個(gè)規(guī)則:
- Group的名字和Machine的名字都由用戶自己指定
- Group的描述可以是一組機(jī)器(見上圖GroupA, GroupB, GroupC)， 也可以是其它Group的運(yùn)算表達(dá)式(見上圖GroupD)
- 表達(dá)式支持'&', '|', '-' 三種運(yùn)算符, 分別代表集合運(yùn)算中的交集，并集，差集
- 表達(dá)式不能包含括號(hào)， 計(jì)算的時(shí)候按照從左到右的順序
問題來了， 當(dāng)我們拿到這么一份配置文件的時(shí)候，需要知道每個(gè)Group包含多少機(jī)器，請(qǐng)問如何編碼實(shí)現(xiàn)？
這個(gè)問題乍一看很簡(jiǎn)單，如果Group的描述本身已經(jīng)是機(jī)器組，直接計(jì)算Machine的數(shù)量即可。 如果Group的描述是表達(dá)式， 則把表達(dá)式中出現(xiàn)的Group用機(jī)器組替換一下，再求數(shù)量也行啊。 難點(diǎn)在哪呢？
關(guān)鍵就在替換這里， 我們看下面一個(gè)場(chǎng)景
GroupA: GroupB & GroupC
GroupB: GroupD | GroupE
GroupC: MachineA, MachineB
GroupD: GroupA & GroupE
GroupE: MachineC, MachineD
讀者朋友可以自己試一試用代換法求解GroupA, 然后很快就會(huì)發(fā)現(xiàn)"臣妾做不到啊"，原來， A引用了B，B引用了D， D又引用了A， 形成了死循環(huán)。 也就是說這個(gè)配置文件本身就是錯(cuò)誤的， 但是如果我們的代碼不能檢測(cè)到這種錯(cuò)誤，就會(huì)導(dǎo)致因?yàn)橛脩舻腻e(cuò)誤配置造成系統(tǒng)死循環(huán)， 多么可怕啊。
怎么檢測(cè)死循環(huán)呢， 其實(shí)也不難， 仔細(xì)想一想，這其實(shí)就是一個(gè)有向圖環(huán)檢測(cè)問題(如果不理解，可以參考筆者的另一篇文章--業(yè)務(wù)模型抽象成有向圖環(huán)檢測(cè)算法，模型和這個(gè)很像)。
這樣做是解決問題了，但是算法寫起來好復(fù)雜，有沒有簡(jiǎn)單點(diǎn)的方法呢？
其實(shí)筆者當(dāng)初實(shí)現(xiàn)的時(shí)候也是按照上述的方法解決的，但有一天整理這段代碼時(shí)發(fā)現(xiàn)了，根本不用這么復(fù)雜好嘛！轉(zhuǎn)換一下思路， 調(diào)整一下展開表達(dá)式的順序就解決了, 解法如下:
- 遍歷所有的Group, 把所有只需要一層展開的表達(dá)式 轉(zhuǎn)化成 Machine List(一層展開指的是表達(dá)式中引用的Group均為確定的Machine List)
- 重復(fù)步驟1，如果在整個(gè)遍歷過程中，沒有新的表達(dá)式被展開， 說明遇到了死循環(huán)，流程終止。 如果所有的表達(dá)式都被展開， 說明問題解決。
是不是變簡(jiǎn)單了，這種做法連死循環(huán)都不需要檢測(cè)了。其實(shí)，事后想一想，這算法并沒有什么難度(甚至小學(xué)生都會(huì)，因?yàn)檫@就是數(shù)學(xué)中的多元一次方程啊)，只是在一種思維遇到困難的時(shí)候，我們往往可以跳出思維定式，找到簡(jiǎn)潔之道。
