本文是[TDD磕算法] 我為什么嘗試用TDD解算法題系列的一篇。
前情提要見
題目
考慮到可能有人沒看前兩篇芒粹，這里把題目再描述一次斟赚。
假定一隊人排成一列
每個人向前看娘侍，如果看到前面有1個比自己高、或者和自己同樣高的人互站。就舉個牌子報數(shù)1私蕾。同理如果有3個，就報3胡桃。
如果把每個人的身高和報數(shù)列出來踩叭，就形成一個二元組的隊列，比如：
[(172, 0), (160, 1), (182, 0), (170, 2)]
就表示第一個人172cm翠胰，前面沒有高于或等于他高度的人容贝；第二個160cm，前面有一個之景；……
這道題目是斤富，給定打亂順序的一個序列，把他們排回應有的順序锻狗。
比如：
輸入：[ (7,2), (4,3), (8,0), (7,1), (6,0)]
輸出：[ (6,0), (8,0), (7,1), (4,3), (7,2)]
性能分析
leetcode上的題目不但會測試功能是否正確满力，還會特意準備幾個比較大的測試數(shù)據(jù)來測試性能。雖然不算是非常嚴謹?shù)男阅軝z驗轻纪，但足以說明時間復雜度上的級別油额。
前一篇雖然解出了題目，但是那段程序的性能是很差的刻帚。差到什么程度呢潦嘶？
在所有的JavaScrip提交中，擊敗了0%崇众。也就是說沒有比它更慢的解法了掂僵。我很驚訝竟然沒有被判超時。
簡單分析一下慢在哪里顷歌。
這個解用文字來描述的話锰蓬，就是把這些人按照前面更高人的個數(shù)排列。先從前面有0個人的開始眯漩，加入新隊列互妓，然后是前面有1個的，然后前面2個人的坤塞，以此類推……
每次加人的時候，從頭開始數(shù)隊列里不低于他的人數(shù)澈蚌，直到比他應有的前面人數(shù)大摹芙，然后在數(shù)到的這個人前面加入。
下面用[ (7,2),(2,0),(4,3),(3,2),(8,0),(7,1),(6,0) ]作為例子展示加入的過程宛瞄，| 表示插入位置浮禾。
(2,0) => [ |]
(8,0) => [ (2,0) |]
(6,0) => [ (2,0), |(8,0) ]
(7,1) => [ (2,0), (6,0), (8,0) |]
(7,2) => [ (2,0), (6,0), (8,0), (7,1) |]
(3,2) => [ (2,0), (6,0), (8,0), |(7,1), (7,2)]
(4,3) => [ (2,0), (6,0), (8,0), (3,2), (7,1), |(7,2)]
[ (2,0), (6,0), (8,0), (3,2), (7,1), (4,3), (7,2)]
可以看出時間耗費有兩個方面：
- 每次向隊列里加人的時候交胚，都需要遍歷隊列里已有的人。這應該是O(n2)的復雜度盈电。我算法基礎不好蝴簇，如果算錯了還望指正。
- 重排之后的隊列長度其實是已知的匆帚，但是這段程序不知道熬词。不斷插入新元素會造成數(shù)組容量調整，以及插入點之后所有已有元素更新位置吸重。
有一個顯而易見的優(yōu)化互拾，找插入點時不需要數(shù)到[x,n]的n+1位置，只要能保證插入的順序嚎幸，數(shù)夠n個人就可以了颜矿。
經過驗證，這個改變可以提高一些性能嫉晶，但仍然慢于大部分的解骑疆。因為它只是讓每次遍歷查找變快了一些，但是遍歷的次數(shù)沒變替废，還是原來的時間復雜度箍铭。
要想有更好的性能，需要另起爐灶實現(xiàn)這個調整順序的過程舶担。
優(yōu)化解求解過程
根據(jù)前面的分析坡疼，要讓整個過程更快，需要避免每次遍歷隊列中的人衣陶。此外柄瑰，最好一次就把人加入最終的位置，不要每次加人都要調整很多人的位置剪况。
根據(jù)這兩點和前兩次嘗試的經驗教沾。大體思路如下：
- 首先，按照高度從低往高逐個加入译断。這樣就可以保證已經加入隊列的人比將要加入的人低授翻。
- 其次，根據(jù)被加入者前面更高的人的個數(shù)孙咪，調整加入隊列的位置堪唐，要空出幾個位置給后面更高的人。
具體怎么做到還沒有想的非常清楚翎蹈，準備在做的過程中逐步搞清楚淮菠。
實現(xiàn)全過程見：http://cyber-dojo.org/review/show/8922CE128B?avatar=toucan&was_tag=1&now_tag=1
第一個和第二個測試與上次練習一致。單個人以及兩人低的在前荤堪。這里略過合陵。
第三個測試
由上次的經驗可知枢赔，關鍵的區(qū)別是排在前面更高的人數(shù)。而隊列總人數(shù)不是最重要的拥知。
因此這個測試選擇：三個人踏拜，最低的排在中間。引入有1個人需要向后調整1位的變化低剔。
reconstruct_should_be([[8,0],[2,1],[3,0]], [[3,0],[2,1],[8,0]]);
仍然先用硬編碼通過測試速梗。
if (sorted[0][1] == 1) {
return [[3,0],[2,1],[8,0]];
}
之后和上次練習類似，通過大段的重構（17步）建立處理[x,1]的邏輯户侥。過程這里略過镀琉。
最終代碼如下。
function reorder(sorted) {
let result = [];
let current = 0;
let toBeFilled = 0;
for (let i = 0; i < sorted.length; i ++) {
if (toBeFilled > 0) {
let inFrontIndex = current - toBeFilled - 1;
result[inFrontIndex] = sorted[i];
toBeFilled--;
} else {
toBeFilled = sorted[i][IN_FRONT];
if (toBeFilled > 0) {
current += toBeFilled;
}
result[current++] = sorted[i];
}
}
return result;
}
大體的思路是如果是[x,0]的情況蕊唐，順序加入新的數(shù)組即可屋摔。
如果碰到[x,1]的時候，就加入當前位置的下一個位置替梨，并記下有1個位置需要后面的人填進去钓试。即代碼中的else分支。
在加入下一個人的時候副瀑，如果發(fā)現(xiàn)有空位需要補充弓熏，就把他加入前面空出的位置。即if分支糠睡。
第四個測試
三個人挽鞠，最高的在前，后面兩人按高低排序狈孔。
reconstruct_should_be([[3,1],[8,0],[2,1]], [[8,0],[2,1],[3,1]]);
運行測試信认，[2,1]空出一個位置，但是后面的[3,1]錯誤的補充到了第一個位置均抽。所以if分支需要補充嫁赏。
實現(xiàn)代碼
這時候忽然發(fā)現(xiàn)并不很容易通過測試，又一次感覺到了第一次失敗嘗試時代碼結構與測試方向不匹配的感覺油挥。
仔細思考了一下潦蝇，發(fā)現(xiàn)是前一段重構時寫了過多的代碼。當時的測試只有[x,1]的例子深寥，也就是說每次最多有一個位置需要留在后面補充攘乒。而代碼里用了一個整數(shù)toBeFilled去記錄需要補填的個數(shù)，因為猜想要處理多個位置需要補填的情況惋鹅。而這個邏輯是沒有經過測試檢驗的则酝。
因此，通過重構改為用一個變量記錄這一個預留的位置负饲。去掉多個位置的邏輯堤魁。
let toBeFilled = null;
for (let p of sorted) {
if (toBeFilled !== null && p[IN_FRONT] === 0) {
result[toBeFilled] = p;
toBeFilled = null;
} else {
if (toBeFilled === null && p[IN_FRONT] === 1 ) {
toBeFilled = current;
current += p[IN_FRONT];
}
result[current++] = p;
}
}
第五個測試
這一步猶豫了一下。
首先試試了[4,0],[2,1],[8,0],[5,1]的序列返十，也就是兩個[x,1]不排在一起的情況妥泉。發(fā)現(xiàn)現(xiàn)有的邏輯已經支持。
后面本想增加[x,2]的測試洞坑，但是轉念一想盲链，覺得還是先測試兩人身高相等的情況步子更小一些。
三個人迟杂，兩個高度一樣的人在前面刽沾，最高的一個在最后。
reconstruct_should_be([[3,0],[8,0],[3,1]], [[3,0],[3,1],[8,0]]);
實現(xiàn)代碼
需要讓[3,1]比[3,0]先加入隊列排拷，這樣它預留的空位就會被[3,0]填補侧漓。否則按照代碼邏輯就會變成后面的[8,0]填入[3,1]前面的位置了。
因此修改一開始對數(shù)組排序的比較方法监氢。改為先按高度排序布蔗，如果高度相等按照前面人數(shù)倒序排列浪腐。
let sorted = peoples.sort(compare_in_height_and_reverse_infront);
...
function compare_in_height_and_reverse_infront(p1, p2) {
if (p1[HEIGHT]===p2[HEIGHT]) {
return p2[IN_FRONT] - p1[IN_FRONT];
} else {
return p1[HEIGHT] - p2[HEIGHT];
}
}
第六個測試
增加前面有兩個人的例子。
三個人一隊泽谨，最低的在最后，前面兩人按高低排列特漩。
reconstruct_should_be([[2,2],[8,0],[3,0]], [[3,0],[8,0],[2,2]]);
實現(xiàn)代碼
現(xiàn)在可能要記錄2個預留的位置吧雹，把toBeFilled改為數(shù)組拾稳。
let toBeFilled = [];
for (let p of sorted) {
if (toBeFilled.length > 0 && p[IN_FRONT] === 0) {
let fillIndex = toBeFilled.pop();
result[fillIndex] = p;
} else {
if (toBeFilled.length === 0 && p[IN_FRONT] === 1 ) {
toBeFilled = [current];
current += p[IN_FRONT];
}
if (toBeFilled.length === 0 && p[IN_FRONT] === 2 ) {
toBeFilled = [current+1, current];
current += p[IN_FRONT];
}
result[current++] = p;
}
}
之后進行重構，統(tǒng)一[x,1]和[x,2]兩個分支的代碼访得。
...
} else {
if (toBeFilled.length === 0 && p[IN_FRONT] > 0 ) {
toBeFilled = reverseRange(current, p[IN_FRONT]);
current += p[IN_FRONT];
}
result[current++] = p;
}
其中reverseRange返回以當前index為最后一個元素的倒序數(shù)組龙亲，比如reverseRange(3,1) === [3]，reverseRange(3,2) === [4,3]鳄炉。
之所以要倒序是因為我覺得在填充預留位置時搜骡，從數(shù)組尾部刪除元素開銷要小一些。
這個函數(shù)的實現(xiàn)很簡單就不貼了记靡。
在第七個失敗測試前又增加了一個測試兩個[x,2]連在一起的情況，發(fā)現(xiàn)和前面處理的連續(xù)[x,1]的情況一樣空凸，測試直接成功。
第七個測試
reconstruct_should_be([[2,2],[8,0],[4,2],[3,0],[9,0]],
[[3,0],[8,0],[2,2],[9,0],[4,2]]);
這個測試區(qū)別于前面的特點是紊选，當加入[2,2]時預留了2個空位道逗。null, null, [2,2]
之后[3,0]填充了一個。[3,0],null,[2,2]
下一個是[4,2]卖词，這時除了[2,2]前面剩余的空位之外贰您，還需要再留出一個空位。[3,0],null,[2,2],null,[4,2]
實現(xiàn)代碼
還是先增加特殊情況分支舶替，在加入[x,2]時如果當前預留位置只有1個了杠园，就把當前位置補入預留位置。
if (toBeFilled.length === 0 && p[IN_FRONT] > 0 ) {
... }
if (toBeFilled.length === 1 && p[IN_FRONT] === 2) {
toBeFilled.unshift(current);
current += 1;
}
重構抛蚁，統(tǒng)一兩種加入預留位置的分支。
let skip = p[IN_FRONT] - toBeFilled.length;
if (skip > 0) {
toBeFilled = reverseRange(current, skip).concat(toBeFilled);
current += skip;
}
result[current++] = p;
}
第八個測試
增加有[x,2]又有[x,1]的情況
reconstruct_should_be([[2,2],[8,0],[3,1]], [[8,0],[3,1],[2,2]]);
實現(xiàn)代碼钉跷，先硬編碼處理肚逸，[2,2]預留了1，2個位置時膝晾，[3,1]應該選擇第2個而非第1個位置的邏輯务冕。
if (toBeFilled.length > 0 && p[IN_FRONT] === 0) {
let fillIndex = toBeFilled.pop();
result[fillIndex] = p;
} else if (toBeFilled.length === 2 && p[IN_FRONT] === 1){
let fillIndex = toBeFilled.shift();
result[fillIndex] = p;
} else { ...
重構，統(tǒng)一兩種填充預留位置的分支臊旭。
if (toBeFilled.length > p[IN_FRONT]) {
let skipInFill = -1 - p[IN_FRONT];
let fillIndex = toBeFilled.splice(skipInFill, 1)[0];
result[fillIndex] = p;
} else { ...
重構，簡化程序
我本以為在填充預留位置的時候领跛，也需要像產生預留位置的分支一樣處理更多的情況撤奸。
結果在增加了一些測試后喊括，才確定原來已經完成了。
這時后可以推理府喳，對于任何一個隊列蘑拯，比如
[8,0],[3,1],[2,2]，
我都可以在它后面加一個0高度的元素弯蚜，變成
[8,0],[3,1],[2,2],[0,3]剃法。
那么程序在排列的時候，除了額外增加的最小的[0,3]外收厨，其余元素都走的是填充預留位置的邏輯优构，同樣可以排出正確順序。也就是說else產生預留位置的分支是冗余的拧额。
重構后調整順序函數(shù)變?yōu)?/p>
function reorder(sorted) {
let result = [];
let toBeFilled = range(sorted.length);
for (let p of sorted) {
result[popAt(toBeFilled, p[IN_FRONT])] = p;
}
return result;
}
這個重構會稍稍增加空間復雜度和操作toBeFilled數(shù)組的開銷玉凯。但是比起對程序邏輯的簡化來說是非常值得的漫仆。
與此類似，我也把toBeFilled數(shù)組由倒序改為了正序，性能變化不大祸泪，但是容易理解多了建芙。
后續(xù)還可以做一個重構，把toBeFilled包裝成一個類右蒲。提供popAt(n)函數(shù)赶熟。效果如下映砖。
reserved.popAt(0) //0
reserved.popAt(0) //1
reserved.popAt(2) //4
reserved.popAt(0) //2
reserved.popAt(0) //3
reserved.popAt(0) //5
在類的內部可以不使用數(shù)組，而是一些內部狀態(tài)量來產生對應序列邑退。這樣使用的數(shù)組的性能損失也可以補回來了地技。
不過這個已經和主線關系不大，這次練習就此打住了宪潮。
這次的解法耗時縮短為原來的1／3趣苏。在leetcode上超過了66%的提交，終于屬于比較正常的解了尽棕。
體會
- 盡管實現(xiàn)代碼完全重寫彬伦。第二次練習總結的測試順序，在這次仍然很有幫助回官。
- 硬編碼快速通過雖然看起來很傻搂橙，在思路不太清楚的時候還是有效的。很容易啟發(fā)后續(xù)的重構苔巨。
- 測試順序是否有助于程序演進。其實可以從硬編碼這一步體現(xiàn)出來礁芦。良好的測試步驟悼尾，當前測試對問題的特殊簡化會出現(xiàn)在硬編碼中。
- 比如先處理
[x,1]窄刘，然后[x,2]舷胜。1和2可能就會在硬編碼里直接寫出活翩。雖然之后可能會成為變量，最終一般化沮焕。但是在增加程序邏輯的這個時刻拉宗，單一的硬編碼分支表明影響局部化在程序的一小部分中旦事。這就確保了整個問題可以逐步分解為小的問題解決 - 而對照第一次的失敗的測試過程，雖然從短到長逐一列舉用例看起來也是小步進行的姐浮。但是在處理2人隊列的測試時卖鲤，代碼里并沒出現(xiàn)隊列長度為2的信息。說明這個限制對分解出一個較簡單的子問題并無幫助
- 比如先處理
- 進展良好時還會有個感受集晚，不怕打斷区匣。
大家都覺得心流（Flow）狀態(tài)是非常好的工作狀態(tài)，程序員就應該心無雜念鉆入代碼中一次幾個小時条摸。比如這幅漫畫。
但是換個角度來看切端，其實漫畫中的這段程序的結構是很爛的顷啼，相互耦合嚴重钙蒙，每個點都與其它部分大量的細節(jié)相關。導致這個程序員必須把大量的細節(jié)裝入腦子的“工作內存”中才能開始編碼马昨，這其實是對腦力的浪費扛施。
在第三次練習的過程中，由于空余時間有限匙奴，周期拖的很長妄荔。常常每次做完一步就放下了，要一天或幾天之后才能繼續(xù)哗伯。
每次結束時我都留下一個失敗的測試篷角，下一回根據(jù)錯誤信息來考慮如何繼續(xù)進行。結果發(fā)現(xiàn)伴澄，不需要特別費力就跟上了上次的進度阱缓。說明每一步可以集中在一個點進行荆针，不需要那么大的“工作內存”了颁糟。
而分解不順利的時候則是完全停不下來的心態(tài)喉悴。比如第一次箕肃，我做到一步卡住了很久，當天就放下了勺像。結果第二天怎么也接不上思路了吟宦。就這么在這一步中止了。
可見袁波，如果編寫過程中感覺心急蜗侈，停不下來。可能有必要留意一下是不是解決思路有需要改進的地方了叫倍。
