1.5 快速找出故障机器_编程之美-QQ阅读男生历史网

上QQ阅读APP看本书，新人免费读10天

设备和账号都新为新人

1.5 快速找出故障机器

关心数据挖掘和搜索引擎的程序员都知道，我们需要很多的计算机来存储和处理海量数据。然而，计算机难免出现硬件故障而导致网络联系失败或死机。为了保证搜索引擎的服务质量，我们需要保证每份数据都有多个备份。

简单起见，我们假设一个机器仅储存一个标号为ID的记录（假设ID是小于10亿的整数），假设每份数据保存两个备份，这样就有两个机器储存了同样的数据。

1．在某个时间，如果得到一个数据文件ID的列表，是否能够快速地找出这个表中仅出现一次的ID？

2．如果已经知道只有一台机器死机（也就是说只有一个备份丢失）呢？如果有两台机器死机呢（假设同一个数据的两个备份不会同时丢失）？

分析与解法

解法一

这个问题可以转化成：有很多的ID，其中只有一个ID出现的次数小于2，其他正常ID出现的次数都等于2，问如何找到这个次数为1的ID。

为了达到这个目的，最简单的办法就是直接遍历列表，利用一个数组记下每个ID出现的次数，遍历完毕之后，出现次数小于2的ID就是我们想要的结果。假设有N个ID，且ID的取值在0～（N-1）之间，这个解法占用的时间复杂度为O（N），空间复杂度为O（N）。

时间复杂度已经相当理想，但是空间复杂度仍觉不够理想。如果ID的数量多达几GB甚至几十GB，这样的空间复杂度在实际的运算中就会带来效率问题。那么，是否有办法进一步地减少空间复杂度呢？

解法二

仔细思考一下，哪些数据是不必存储的呢？大部分的机器ID出现次数都等于2，这些ID的信息有必要吗？我们可以利用这样一个特性：ID出现次数等于2的机器肯定不是故障的机器，可以不予考虑。因此，可以把解法1数组中等于2的元素清空，然后用来存储下一个机器ID的出现次数，这样就可以减少需要的空间。

具体方法如下：遍历列表，利用哈希表记下每个ID出现的次数，每次遇见一个ID，就向哈希表中增加一个元素；如果这个ID出现的次数为2，那么就从哈希表中删除这个ID，最后剩下的ID就是我们想要的结果。这个算法空间复杂度在最好情况下可以达到O（1），在最坏情况下仍然是O（N）。

解法三

前面的两个算法的时间复杂度已经达到了O（N），并且空间复杂度也已经有了一定的突破，那么是否有可能进一步提高算法的性能呢？

分别从时间复杂度，空间复杂度方面考虑，时间复杂度上面很难有太大的突破。因为，已经降到了O（N）这个规模了。那么，空间复杂度呢？

如果想继续降低空间复杂度，就要摒弃遍历列表计数这种方法了，考虑采用完全不同的模式来计算。

如果空间复杂度仍然在N这个级别，其实也没有降多少。是否可以降到常数级别呢？更加极端一点，是否可能使得空间复杂度降为O（1），也就是说只利用一个变量来记录遍历列表的结果。

如果这样，我们可以把这个变量写成：x(i)=f(list[0], list[1], …, list[i])，也就是说这个变量是已经遍历过的列表元素的函数。这个函数需要满足的条件就是：x(N)=ID_Lost。也就说遍历完整个列表后，这个变量的值应该等于丢失备份的ID。

我们需要做的就是寻找合适的f。

显然，f的形式不只一种。那么，我们可以先考虑找出一种可行的函数。对于第一问，我们已经知道，列表中仅有一个ID出现了一次。那么，可以考虑使用异或关系来帮忙找到结果。

因为X⊕X=0且X⊕0=X，因此，可以把这个关系应用到构造这个函数上面。因为，正确的机器都会有两个ID，不正确的机器只有一个ID。所以所有ID的异或值就等于这个仅出现一次的ID（因为异或运算满足交换律和结合律，其他出现两次的ID异或完都为0）。这样我们只使用一次遍历运算就得到了只有一台故障机器情况下故障机器的ID。

因此，就可以使用x(i)=list[0]⊕list[1]⊕…⊕list[i]来作为结果值。

在这样的情况下，时间复杂度为O（N），由于只需要保存一个运算结果，因此空间复杂度为O（1）。

对于第二问，由于有两个ID仅出现了一次，设它们为A和B，那么所有ID的异或值为A⊕B（道理同上面分析的一样）。但还是无法确定A和B的值。

可以进行分类讨论：如果A=B，则A⊕B为0，也就是说丢失的是同一份数据的两个拷贝，我们可以通过求和的方法得到A和B（A=B=(所有ID之和-所有正常工作机器ID之和)/2）。如果A⊕B不等于0，那么这个异或值的二进制中某一位为1。显然，A和B中有且仅有一个数的相同位上也为1。

我们就把所有ID分成两类，一类在这位上为1，另一类这位上为0。那么对于这两类ID，每一类分别含有A和B中的一个。那么我们使用两个变量，在遍历列表时，分别计算这两类ID的异或和，即可得到A和B的值。

解法四

解法三的空间复杂度只有O（1），时间复杂度为O（N），在计算复杂度上已经做到了最优。但对于第二问两台机器死机的情况，只能解决两台故障机器ID不同的情况，如果ID相同则无法解决。

那如果需要考虑死机的两台机器ID相同的情况，还有没有办法解决呢？让我们再回头仔细分析一下，这个问题可以抽象为：在一个事先预定的整数（ID）集合当中，怎么样找出其中丢失的一个数（ID）或者两个数（ID）？

让我们回忆一下以前数学中的“不变量”的概念，就会发现所有机器ID的求和是一个固定的值，也就是我们所说的“不变量”。或许这个“不变量”可以用来解决我们当前的问题。如果只有一台机器死机，相当于我们这个ID集合里面少了一个ID，也就是说我们把剩下的ID求和，和所有ID的求和（“不变量”）的差就是当前缺少的ID的数值！

可以得到如下算法：预先计算并保存好所有ID的求和（“不变量”），顺序列举当前所有剩下的ID，对它们求和，然后用所有ID的求和（“不变量”）减去当前剩下所有ID的和，结果就是死机的机器ID的值。由于所有ID的求和（“不变量”）可以预先算好，而且在所有的检测中只算一次，当前算法的时间复杂度为O（N），空间复杂度为O（1），和解法三一样是计算复杂度最优的算法。

对于第二问，我们考虑所有的情况，即两个ID可以不同也可以相同。这时候就相当于在ID的集合里面丢失了两个ID。用上面的同样方法我们只能得到这两个ID的和，假设丢失的两个ID分别是x和y，我们只能知道x+y的值，写成x+y=a，并不能分辨x和y的值。显然我们需要更多的信息来确定x和y的值。让我们回忆一下初中数学的二元方程，两个变量需要两个方程才能求出解，我们现在只有一个，如果我们还能再构造出一个关于x和y的方程，就能求出x和y的值。可能读到这里，聪明的读者已经能构造出第二个方程了。

第二个方程有很多种构造方法，这里提供一种供大家参考：我们再用一个所有ID乘积的不变量，预先计算并保存好所有ID的乘积（“不变量”），顺序列举当前所有剩下的ID，把他们乘起来得到乘积，然后用所有ID的乘积（“不变量”）除以当前剩下所有ID的乘积，结果就是两台死机的机器ID的乘积，也就是xy的值，写成xy=b。这样我们通过联立上面两个方程x+y=a和xy=b，就可以计算出x和y的值。计算时间复杂度为O（N），空间复杂度为O（1）。

当然这里说的是一种理想的情况，聪明的读者可能会发现这里有一个问题。因为ID通常是一个比较大的整数，而机器ID的数量通常又比较多，产生的问题就是很多整数相乘结果可能会溢出。这点涉及实现的问题，我们就不多加讨论了，其实也是有办法可以避免的，比如不采用乘积的形式构造第二个方程，而采用平方和的形式构造第二个方程。

扩展问题

如果所有的机器都有3个备份，也就是说同一ID的机器有3台，而且同时又有3台机器死机，还能用上面解法四的思路解决吗？如果有N个备份，而且同时又有N台机器死机，是否还能解决？