每周学点大数据 | No.11亚线性算法
No.11期
亚线性算法
Mr. 王：从今天开始，我们正式讲解大数据算法的内容。首先谈谈关于亚线性算法的问题。
小可：我记得前面提到过亚线性算法，就是复杂度低于输入规模的算法。
Mr. 王：我们给出一个严格的定义，还是设输入规模为n，那么亚线性算法就是指时间、空间、通讯、能量等复杂度为o(n)的算法。
小可若有所思，说：如果输入规模为n，而算法的复杂度还要低于n，这是不是说我们不能保存所有的数据，或者不能访问所有的数据呢？
Mr. 王：是的。只有这样才能实现亚线性的要求。
小可：可是，如果访问不到所有的数据，对于很多问题我们是得不到正确答案的啊。比如有一组规模比较大的数据，我们要求它们的中位数，如果不访问所有的数据，得到的结果就有可能是错误的啊。
Mr. 王：对于这样的答案我们不能简单地称之为正确解和错误解，而是称之为精确解和近似解，在大数据算法中解决问题的重要思路就是近似。由于在规定的时间内和计算条件下，我们得到精确解的时间太久，所以采用近似的方法来得到一个“差不多”的答案。这样的答案的误差在我们可以容忍的范围内，能够满足应用的需求就可以了。在小的数据集合上，我们时常需要的是精确解，而当数据量很大时，得到精确解的开销也会变得大到不能接受。因此，我们求近似解以换取更高的效率。近似是亚线性算法的核心思想。
小可：原来是这样。
Mr. 王：亚线性算法也可以分为空间亚线性算法、时间亚线性计算算法和时间亚线性判定算法。下面我就这几类问题分别举个典型的例子来看看亚线性算法是如何解决问题的。
Mr. 王：首先我们看一个经典问题：水库抽样。这是一个典型的空间亚线性算法。考虑这样一个问题：很多时候我们要在大宗数据中进行一个均匀的抽样，这在实际的生活中是非常常见的，但是在实际情况下，有时候我们要处理的数据量太大，以至于只能让这些数据从我们的面前“流过”一次。这就好比数据从一个生产线或者流水线上源源不断地到来，当来到计算系统中时，我们可以对其进行处理，但是对其进行过处理之后，或者由于能存储这些数据的能力有限，我们不得不将其从内存中清除出去，这样就再也不能访问它了。
水库抽样问题的要求是，每一刻所取到的样本，就是前面已经“流过”的全部数据的均匀抽样。你来根据我们前面提过的分析问题的方法，说一说问题定义。
小可想了想，说：
输入：一组数据，其大小未知。
输出：这组数据的k个均匀抽样。
要求：
a．仅扫描数据一次；
b．空间复杂性为O(k) ；
c．扫描到前n（n>k）个数据时，保存当前已扫描数据的k个均匀抽样。
Mr. 王：说得不错，对于这个问题，我们给出下面的算法：
（1）申请一个长度为k的数组A保存抽样（此处的数组下标以[1,k]表示，对于[0,k-1]的实际操作情况，可以非常容易地进行替换）。
（2）保存首先接收到的k个元素。
（3）当接收到第i新元素t时，生成[1,i]间随机数j，若j≤k，则以t替换A[j]。
算法的关键在于第三步：每当新到来一个元素t时，都生成一个随机数，一旦随机数落在了数组范围之内，就用新元素把它替换掉。
小可：这个算法看起来倒是挺简单的，用一个随机数来决定是不是进行抽样替换，可是它真的能够满足均匀抽样的需求吗？
Mr. 王：嗯，接下来我们就来证明这个算法的正确性。你先说一说，均匀采样应该满足什么条件？
小可：在本题目的条件中，对于任意一个元素i，它被选入样本的概率均为k/n。
Mr. 王：好，那么我们只需要证明该算法满足这个要求就可以了。首先，对于每一个新到来的元素i，它是以k/i的概率被收入抽样集合的，这是因为生成的随机数范围是[1,i]，而当数字小于等于k时，它会被替换进数组A。
当第i+1个元素到来时，i+1被替换进来的概率就是k/i+1，而此时，前一个元素i被从中替换出来的概率是1/k。这两个值的乘积就是当第i+1个元素到来时前面的i被替换出来的概率，其值为1/(i+1)，那么1-1/(i+1)就是i没有在i+1到来时被替换出去的概率。当i+2、i+3等这些元素到来时，其计算过程和i+1是同理的。
如果元素i被选入集合中，并且在后面所有的替换过程中，每一次替换都没有被替换出去时，它就是我们选出来的样本，那么元素i在样本中的概率应该是多少呢？
小可：
Mr. 王：这就是说，对于任意元素i，其被选入样本的概率均为k/n。也就是说，它符合随机抽样。
小可：原来随机决定了替换的结果，还真的能保证抽样的均匀性。
Mr. 王：讨论过算法的正确性，可以确定这个算法的执行结果是正确的，但是我们希望它是一个空间亚线性算法，所以还要分析它的空间复杂度是不是满足亚线性这一要求。你来分析一下，这个算法的空间复杂度如何？
小可：不论“流动”来了多少个数据，我们只需要保存k个数据作为样本就可以了，其余的计算空间都是常数开销，那就应该是O(k)。
Mr. 王：显然，k是小于n的。也就是说，我们的这个算法在正确的前提下，对于输入规模n，做到了o(k)的空间复杂度，而o(k)∈o(n)，也就表明，它是一个空间亚线性算法。
小可：我懂了。
Mr. 王：这里也为我们设计空间亚线性算法提供了一个思路，就是不能去尝试保存全部的数据。我们要进行亚线性的均匀抽样，不能把所有的数据都保存下来，再去做均匀抽样，这样势必会造成O(n)的空间复杂度。我们要考虑，能不能在只保存大数据中的一个小集合的情况下，来达到问题的要求。在水库抽样问题中，虽然我们采用的是空间亚线性算法，但是得到的依然是精确解。
内容来源：灯塔大数据