拒绝调包侠，不需要高级算法和数据结构技巧

大多数工科学生或者刚刚入门近年来比较火的“人工智能”相关算法的同学，在选择语言的时候，都会选择MATLAB、 Python 、R等等这些高级语言，对自己所学的算法进行实现和调试。这些高级语言中，包含了实现复杂算法的基础数学算法、基本统计算法、基础数据结构的实现，比如均值（mean）、方差（std）、向量（Vector）等等。借助于这些高级语言的Built-in Function，我们的一些想法会在较短时间内实现。并且，解释型的编程方式，也方便了大家去调试代码、运行代码。但是使用这些语言和它们的函数，会带来一些效率降低的问题。大多数人首先想到的解决方式，可能是去选择底层语言来实现算法，比如C/C++, JAVA等。但其实，我们在运用高级语言进行编码时，也有大量需要进行优化的内容。我们应当从“调包”和利用Built-in Function的习惯中解放出来。

问题

最近在用C++实现CUSUM时，我参考该算法的MATLAB的代码直接翻译成了C++的代码。本想到算法应该会非常迅速，但是它的表现的确让我大失所望。在优化掉输出（ ostream ）带来的时间损耗后，算法的速度依然没有达到期望的要求。于是，观察代码细节时发现，在迭代过程中，我们对一段随迭代次数其长度线性增长的数组片段（ slice ）求取均值、方差时，使用了 mean() 和 std() 函数。

那么，每一次新的数据添加进一个数组（Array或者Vector），就去调用上述这类函数，真的有必要嘛？我们是不是引入了太多的重复计算？

解决方案

我们先来看一下CUSUM算法的MATLAB实现的一个片段：

%% Global Loop
% w = waitbar(0,'Calculating Cumulative Sums, please wait...');
while k < length(x)
  % current sample
  k = k+1; 
  % mean and variance estimation (from initial to current sample)
  m(k) = mean(x(k0:k));
  v(k) = var(x(k0:k));
复制代码

上述代码片段里，在 while 循环中，我们调用了 length(x) 次函数 mean 和 std ，这其中包含了大量的重复计算，带来了大量的计算开销（计算均值，肯定有大量的加和操作）。假设我们已经计算了实数数组 的均值，记为 。当一个新的数据 被采样到，并加入 中，形成 。在计算均值 时，可以利用以下公式：

同理，我们可以得到计算新方差的公式：

新的编码方案就变成：

// Global Loop
while (k < len - 1) {
  k++;
  prev_delta = X[k] - m[k - 1];     // online average
  m.emplace_back(m[k - 1] + prev_delta / (k - k0 + 1));
  post_delta = X[k] - m[k];         // online s.t.d
  v.emplace_back(std::sqrt(v[k - 1]*v[k - 1] + prev_delta*post_delta));
复制代码

这样计算速度就快很多了。

思考

如上所述的这种从左至右计算统计量的过程，在很多算法中出现过，比如著名的 决策树 算法。决策树在某个节点确定分裂特征和分裂点的计算过程中，是如何进行计算统计量的呢？著名的决策树开源框架，如XGBoost中，又是如何编码，对样本梯度进行统计的呢？这些留给大家去思考和发现。