本文是[TDD磕算法] 我为什么尝试用TDD解算法题系列的一篇。
前情提要见
题目
考虑到可能有人没看前两篇，这里把题目再描述一次。
假定一队人排成一列
每个人向前看，如果看到前面有1个比自己高、或者和自己同样高的人。就举个牌子报数1。同理如果有3个，就报3。
如果把每个人的身高和报数列出来，就形成一个二元组的队列，比如：
[(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上的题目不但会测试功能是否正确，还会特意准备几个比较大的测试数据来测试性能。虽然不算是非常严谨的性能检验，但足以说明时间复杂度上的级别。
前一篇虽然解出了题目，但是那段程序的性能是很差的。差到什么程度呢？
在所有的JavaScrip提交中，击败了0%。也就是说没有比它更慢的解法了。我很惊讶竟然没有被判超时。
简单分析一下慢在哪里。
这个解用文字来描述的话，就是把这些人按照前面更高人的个数排列。先从前面有0个人的开始，加入新队列，然后是前面有1个的，然后前面2个人的，以此类推……
每次加人的时候，从头开始数队列里不低于他的人数，直到比他应有的前面人数大，然后在数到的这个人前面加入。
下面用[ (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)的复杂度。我算法基础不好，如果算错了还望指正。
- 重排之后的队列长度其实是已知的，但是这段程序不知道。不断插入新元素会造成数组容量调整，以及插入点之后所有已有元素更新位置。
有一个显而易见的优化，找插入点时不需要数到[x,n]的n+1位置，只要能保证插入的顺序，数够n个人就可以了。
经过验证，这个改变可以提高一些性能，但仍然慢于大部分的解。因为它只是让每次遍历查找变快了一些，但是遍历的次数没变，还是原来的时间复杂度。
要想有更好的性能，需要另起炉灶实现这个调整顺序的过程。
优化解求解过程
根据前面的分析，要让整个过程更快，需要避免每次遍历队列中的人。此外，最好一次就把人加入最终的位置，不要每次加人都要调整很多人的位置。
根据这两点和前两次尝试的经验。大体思路如下：
- 首先，按照高度从低往高逐个加入。这样就可以保证已经加入队列的人比将要加入的人低。
- 其次，根据被加入者前面更高的人的个数，调整加入队列的位置，要空出几个位置给后面更高的人。
具体怎么做到还没有想的非常清楚，准备在做的过程中逐步搞清楚。
打磨
实现全过程见：http://cyber-dojo.org/review/show/8922CE128B?avatar=toucan&was_tag=1&now_tag=1
第一个和第二个测试与上次练习一致。单个人以及两人低的在前。这里略过。
第三个测试
由上次的经验可知，关键的区别是排在前面更高的人数。而队列总人数不是最重要的。
因此这个测试选择：三个人，最低的排在中间。引入有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]的情况，顺序加入新的数组即可。
如果碰到[x,1]的时候，就加入当前位置的下一个位置，并记下有1个位置需要后面的人填进去。即代码中的else分支。
在加入下一个人的时候，如果发现有空位需要补充，就把他加入前面空出的位置。即if分支。
第四个测试
三个人，最高的在前，后面两人按高低排序。
reconstruct_should_be([[3,1],[8,0],[2,1]], [[8,0],[2,1],[3,1]]);
运行测试，[2,1]空出一个位置，但是后面的[3,1]错误的补充到了第一个位置。所以if分支需要补充。
实现代码
这时候忽然发现并不很容易通过测试，又一次感觉到了第一次失败尝试时代码结构与测试方向不匹配的感觉。
仔细思考了一下，发现是前一段重构时写了过多的代码。当时的测试只有[x,1]的例子，也就是说每次最多有一个位置需要留在后面补充。而代码里用了一个整数toBeFilled去记录需要补填的个数，因为猜想要处理多个位置需要补填的情况。而这个逻辑是没有经过测试检验的。
因此，通过重构改为用一个变量记录这一个预留的位置。去掉多个位置的逻辑。
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]不排在一起的情况。发现现有的逻辑已经支持。
后面本想增加[x,2]的测试，但是转念一想，觉得还是先测试两人身高相等的情况步子更小一些。
三个人，两个高度一样的人在前面，最高的一个在最后。
reconstruct_should_be([[3,0],[8,0],[3,1]], [[3,0],[3,1],[8,0]]);
实现代码
需要让[3,1]比[3,0]先加入队列，这样它预留的空位就会被[3,0]填补。否则按照代码逻辑就会变成后面的[8,0]填入[3,1]前面的位置了。
因此修改一开始对数组排序的比较方法。改为先按高度排序，如果高度相等按照前面人数倒序排列。
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]]);
实现代码
现在可能要记录2个预留的位置，把toBeFilled改为数组。
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;
}
}
之后进行重构，统一[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为最后一个元素的倒序数组，比如reverseRange(3,1) === [3]，reverseRange(3,2) === [4,3]。
之所以要倒序是因为我觉得在填充预留位置时，从数组尾部删除元素开销要小一些。
这个函数的实现很简单就不贴了。
在第七个失败测试前又增加了一个测试两个[x,2]连在一起的情况，发现和前面处理的连续[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]]);
这个测试区别于前面的特点是，当加入[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]
实现代码
还是先增加特殊情况分支，在加入[x,2]时如果当前预留位置只有1个了，就把当前位置补入预留位置。
if (toBeFilled.length === 0 && p[IN_FRONT] > 0 ) {
... }
if (toBeFilled.length === 1 && p[IN_FRONT] === 2) {
toBeFilled.unshift(current);
current += 1;
}
重构，统一两种加入预留位置的分支。
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]]);
实现代码，先硬编码处理，[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 { ...
重构，统一两种填充预留位置的分支。
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产生预留位置的分支是冗余的。
重构后调整顺序函数变为
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数组的开销。但是比起对程序逻辑的简化来说是非常值得的。
与此类似，我也把toBeFilled数组由倒序改为了正序，性能变化不大，但是容易理解多了。
后续还可以做一个重构，把toBeFilled包装成一个类。提供popAt(n)函数。效果如下。
reserved.popAt(0) //0
reserved.popAt(0) //1
reserved.popAt(2) //4
reserved.popAt(0) //2
reserved.popAt(0) //3
reserved.popAt(0) //5
在类的内部可以不使用数组，而是一些内部状态量来产生对应序列。这样使用的数组的性能损失也可以补回来了。
不过这个已经和主线关系不大，这次练习就此打住了。
这次的解法耗时缩短为原来的1／3。在leetcode上超过了66%的提交，终于属于比较正常的解了。
体会
- 尽管实现代码完全重写。第二次练习总结的测试顺序，在这次仍然很有帮助。
- 硬编码快速通过虽然看起来很傻，在思路不太清楚的时候还是有效的。很容易启发后续的重构。
- 测试顺序是否有助于程序演进。其实可以从硬编码这一步体现出来。良好的测试步骤，当前测试对问题的特殊简化会出现在硬编码中。
- 比如先处理
[x,1]，然后[x,2]。1和2可能就会在硬编码里直接写出。虽然之后可能会成为变量，最终一般化。但是在增加程序逻辑的这个时刻，单一的硬编码分支表明影响局部化在程序的一小部分中。这就确保了整个问题可以逐步分解为小的问题解决 - 而对照第一次的失败的测试过程，虽然从短到长逐一列举用例看起来也是小步进行的。但是在处理2人队列的测试时，代码里并没出现队列长度为2的信息。说明这个限制对分解出一个较简单的子问题并无帮助
- 比如先处理
- 进展良好时还会有个感受，不怕打断。
大家都觉得心流（Flow）状态是非常好的工作状态，程序员就应该心无杂念钻入代码中一次几个小时。比如这幅漫画。
为什么不要打断工作中的程序员
但是换个角度来看，其实漫画中的这段程序的结构是很烂的，相互耦合严重，每个点都与其它部分大量的细节相关。导致这个程序员必须把大量的细节装入脑子的“工作内存”中才能开始编码，这其实是对脑力的浪费。
在第三次练习的过程中，由于空余时间有限，周期拖的很长。常常每次做完一步就放下了，要一天或几天之后才能继续。
每次结束时我都留下一个失败的测试，下一回根据错误信息来考虑如何继续进行。结果发现，不需要特别费力就跟上了上次的进度。说明每一步可以集中在一个点进行，不需要那么大的“工作内存”了。
而分解不顺利的时候则是完全停不下来的心态。比如第一次，我做到一步卡住了很久，当天就放下了。结果第二天怎么也接不上思路了。就这么在这一步中止了。
可见，如果编写过程中感觉心急，停不下来。可能有必要留意一下是不是解决思路有需要改进的地方了。
网友评论