题目：给你一台计算机能力有限的计算机，它无法同时计算海量的数据，如何用它计算出海量数据的精确的标准差（这些数据无法同时放入计算机内存中计算）？
1、题目中要求精确的标准差，意味着我们无法通过抽样的方法进行估算，所有数据必须经过计算机处理； 2、而计算机无法同时处理所有数据，那思路很简单，意味着只能将海量的数据进行分批处理； 3、只要将海量的数据分割为计算机能处理的大小范围，就可以求出每一批数据的样本大小、平均数、标准差，然后每次计算只需要将已经过计算数据的标准差与本次计算的数据的标准差进行合并成新的已经过计算数据的标准差即可； 4、那么问题则变成一个简单的数学问题：已知两组数据的样本大小、平均数、标准差，合并后的样本大小和平均数很好计算，但是如何计算合并后的数据的标准差呢？
正面从两组数据的样本大小、平均数、标准差去推理合并后的数据的标准差的计算公式未免有些难，我们不妨从标准差的计算公式倒着推。标准差计算方法： S = ∑ i = 1 n ( x i − x ˉ ) 2 n − 1 S =\sqrt{\frac{\sum_{i=1}^n (x_i-\bar x)^2}{n-1}} S=n−1∑i=1n(xi−xˉ)2 假设两组数据的样本大小分别为 n 1 ， n 2 n_1 ，n_2 n1，n2 那么有： ( n − 1 ) S 2 = ∑ i = 1 n ( x i − x ˉ ) 2 = ∑ i n 1 ( x 1 i − x ˉ ) 2 + ∑ i n 2 ( x 2 i − x ˉ ) 2 = ∑ i n 1 ( x 1 i 2 − 2 x ˉ x 1 i + x ˉ 2 ) + ∑ i n 2 ( x 2 i 2 − 2 x ˉ x 2 i + x ˉ 2 ) = ∑ i n 1 x 1 i 2 + ∑ i n 2 x 2 i 2 − 2 x ˉ ∑ i n x + ( n 1 + n 2 ) x ˉ 2 = ∑ i n 1 x 1 i 2 + ∑ i n 2 x 2 i 2 − ( n 1 + n 2 ) x ˉ 2 ∵ 标 准 差 计 算 的 变 形 公 式 ： S 2 = ∑ x 2 − ( ∑ x 1 ) 2 n 1 n − 1 ∴ ∑ x 2 = ( n − 1 ) S 2 + ( ∑ x ) 2 n ∴ ∑ x 1 i 2 = ( n 1 − 1 ) S 1 2 + ( ∑ x 1 ) 2 n 1 ∑ x 2 i 2 = ( n 2 − 1 ) S 2 2 + ( ∑ x 2 ) 2 n 2 ( n − 1 ) S 2 = ( n 1 − 1 ) S 1 2 + ( ∑ x 1 ) 2 n 1 + ( n 2 − 1 ) S 2 2 + ( ∑ x 2 ) 2 n 2 − ( n 1 + n 2 ) x ˉ 2 又 ∵ ∑ x 1 = n 1 x 1 ˉ ， ∑ x 2 = n 2 x 2 ˉ x ˉ = n 1 x 1 ˉ + n 2 x 2 ˉ n 1 + n 2 ∴ ( n − 1 ) S 2 = ( n 1 − 1 ) S 1 2 + ( n 2 − 1 ) S 2 2 + ( n 1 x 1 ˉ ) 2 n 1 + ( n 2 x 2 ˉ ) 2 n 2 − ( n 1 x 1 ˉ + n 2 x 2 ˉ ) 2 n 1 + n 2 = ( n 1 − 1 ) S 1 2 + ( n 2 − 1 ) S 2 2 + n 1 n 2 n 1 + n 2 ( x 1 ˉ − x 2 ˉ ) 2 即 S = ( n 1 − 1 ) S 1 2 + ( n 2 − 1 ) S 2 2 + n 1 n 2 n 1 + n 2 ( x 1 ˉ − x 2 ˉ ) 2 n 1 + n 2 − 1 \begin{aligned} (n-1)S^2 &= \sum_{i=1}^n (x_i-\bar x)^2 \\ &= \sum_i^{n_1}(x_{1i}-\bar x)^2 + \sum_i^{n_2}(x_{2i}-\bar x)^2 \\ &= \sum_i^{n_1}(x_{1i}^2-2\bar xx_{1i}+\bar x^2) + \sum_i^{n_2}(x_{2i}^2-2\bar xx_{2i}+\bar x^2) \\ &= \sum_i^{n_1}x_{1i}^2+\sum_i^{n_2}x_{2i}^2-2\bar x\sum_i^nx+(n_1+n_2)\bar x^2 \\ &= \sum_i^{n_1}x_{1i}^2+\sum_i^{n_2}x_{2i}^2-(n_1+n_2)\bar x^2 \end{aligned} \\ \because标准差计算的变形公式： S^2 = \frac{\sum x^2 - \frac{(\sum x_1)^2}{n_1}}{n-1} \\ \therefore \sum x^2 = (n-1)S^2 + \frac {(\sum x)^2}{n} \\ \therefore \sum x_{1i}^2 = (n_1-1)S_1^2 + \frac {(\sum x_1)^2}{n_1} \\ \sum x_{2i}^2 = (n_2-1)S_2^2 + \frac {(\sum x_2)^2}{n_2} \\ \begin{aligned} (n-1)S^2 &= (n_1-1)S_1^2+\frac {(\sum x_1)^2}{n_1}+ (n_2-1)S_2^2+\frac {(\sum x_2)^2}{n_2}-(n_1+n_2)\bar x^2 \\ \end{aligned} \\ 又\because \sum x_1 = n_1\bar {x_1}，\sum x_2 = n_2\bar {x_2} \\ \bar x = \frac {n_1\bar {x_1}+n_2\bar {x_2}}{n_1+n_2} \\ \therefore \begin{aligned} (n-1)S^2 &= (n_1-1)S_1^2+ (n_2-1)S_2^2+\frac {(n_1\bar {x_1})^2}{n_1}+\frac {(n_2\bar {x_2})^2}{n_2}-\frac{(n_1\bar {x_1}+n_2\bar {x_2})^2}{n_1+n_2} \\ &= (n_1-1)S_1^2+ (n_2-1)S_2^2+\frac {n_1n_2}{n_1+n_2}(\bar {x_1} - \bar {x_2})^2 \\ \end{aligned} \\ 即 S= \sqrt{\frac {(n_1-1)S_1^2+ (n_2-1)S_2^2+\frac {n_1n_2}{n_1+n_2}(\bar {x_1} - \bar {x_2})^2}{n_1+n_2-1} }\\ (n−1)S2=i=1∑n(xi−xˉ)2=i∑n1(x1i−xˉ)2+i∑n2(x2i−xˉ)2=i∑n1(x1i2−2xˉx1i+xˉ2)+i∑n2(x2i2−2xˉx2i+xˉ2)=i∑n1x1i2+i∑n2x2i2−2xˉi∑nx+(n1+n2)xˉ2=i∑n1x1i2+i∑n2x2i2−(n1+n2)xˉ2∵标准差计算的变形公式：S2=n−1∑x2−n1(∑x1)2∴∑x2=(n−1)S2+n(∑x)2∴∑x1i2=(n1−1)S12+n1(∑x1)2∑x2i2=(n2−1)S22+n2(∑x2)2(n−1)S2=(n1−1)S12+n1(∑x1)2+(n2−1)S22+n2(∑x2)2−(n1+n2)xˉ2又∵∑x1=n1x1ˉ，∑x2=n2x2ˉxˉ=n1+n2n1x1ˉ+n2x2ˉ∴(n−1)S2=(n1−1)S12+(n2−1)S22+n1(n1x1ˉ)2+n2(n2x2ˉ)2−n1+n2(n1x1ˉ+n2x2ˉ)2=(n1−1)S12+(n2−1)S22+n1+n2n1n2(x1ˉ−x2ˉ)2即S=n1+n2−1(n1−1)S12+(n2−1)S22+n1+n2n1n2(x1ˉ−x2ˉ)2
到这里我们可以发现合并数据的标准差可以由两组数据的样本大小、平均数、标准差来计算，这时意味这当我们计算海量的数据时，只需要保存已计算数据的样本大小、平均数、标准差三个值即可，后面通过分批计算不断对这三个值进行修正，最终算完这些海量数据得到的标准差就是整体的标准差了。
起初对这道题的第一反应是Map/Reduce，后来仔细想想发现这个方法也有问题，因为如果在数据足够大的情况下，映射之后的数据也可能很大，而且进行分布式计算好像也不太符合题目的要求，以上的方法则更多类似一种迭代的思想，通过缩小问题规模再循环迭代，每次计算都接近目标一步，等全部数据算完就得到了精确的结果了。
