前言
大多数工科学生或者刚刚入门近年来比较火的 "人工智能" 相关算法的同学, 在选择语言的时候, 都会选择 MATLAB,Python,R 等等这些高级语言, 对自己所学的算法进行实现和调试. 这些高级语言中, 包含了实现复杂算法的基础数学算法, 基本统计算法, 基础数据结构的实现, 比如均值 (mean), 方差(std), 向量(Vector) 等等. 借助于这些高级语言的 Built-in Function, 我们的一些想法会在较短时间内实现. 并且, 解释型的编程方式, 也方便了大家去调试代码, 运行代码. 但是使用这些语言和它们的函数, 会带来一些效率降低的问题. 大多数人首先想到的解决方式, 可能是去选择底层语言来实现算法, 比如 C/C++, JAVA 等. 但其实, 我们在运用高级语言进行编码时, 也有大量需要进行优化的内容. 我们应当从 "调包" 和利用 Built-in Function 的习惯中解放出来.
问题
最近在用 C++ 实现 https://en.wikipedia.org/wiki/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 中, 又是如何编码, 对样本梯度进行统计的呢? 这些留给大家去思考和发现.
来源: https://juejin.im/post/5bf021036fb9a049ae077ab4