如何在PHP中优化指数移动平均算法？

Question

我正在尝试检索大型数据集（15000个值）的最后一个EMA。这是一个非常消耗资源的算法，因为每个值都依赖于前一个值。这是我的代码：

$k = 2/($range+1);
for ($i; $i<$size_data; ++$i) {
    $lastEMA = $lastEMA + $k * ($data[$i]-$lastEMA);
}

我已经做了什么：

1. 隔离$k，因此不会计算10000次
2. 仅保留最新计算的EMA，而不是将所有EMA都保留在一个数组中
3. 使用for（）而不是foreach（）
4. $data[]数组没有键；这是一个基本阵列

这使我能够将15000个值的执行时间从2000ms减少到500ms左右！

什么不起作用：

1. 使用splfixedaray（），执行1000000个值只需约10ms

用C#编写和运行相同的html" target="_blank">算法并运行它超过2,000,000个值只需要13ms！所以很明显，使用编译的低级语言似乎有所帮助；P

我应该从这里去哪里？代码最终将在Ubuntu上运行，那么我应该选择哪种语言呢？PHP能够调用并将如此大的参数传递给脚本吗？

Answer 1

构建自己的扩展肯定会提高性能。这里有一个来自Zend网站的好教程。

一些性能数据：硬件：Ubuntu 14.04、PHP 5.5.9、1核IntelCPU@3.3Ghz、128MB RAM（它是VPS）。

• 之前（仅限PHP，16,000个值）：500ms
• C扩展，16,000个值：0.3ms
• C扩展（100,000个值）：3.7ms
• C扩展（500,000个值）：28.0ms

但是我现在内存有限，使用70MB。我会修复它并相应地更新数字。

Answer 2

很明显，使用扩展实现会给您带来显著的提升。此外，微积分本身也可以改进，您可以选择任何一种语言进行添加。

很容易看出lastEMA可以计算如下：

$lastEMA = 0;
$k = 2/($range+1);
for ($i; $i<$size_data; ++$i) {
    $lastEMA = (1-$k) * $lastEMA + $k * $data[$i];
}

可以按如下方式重写，以便尽可能多地退出循环：

$lastEMA = 0;
$k = 2/($range+1);
$k1m = 1 - $k;
for ($i; $i<$size_data; ++$i) {
    $lastEMA = $k1m * $lastEMA + $data[$i];
}
$lastEMA = $lastEMA * $k;

要解释“$k”的提取，请认为在前面的公式中，所有原始数据都乘以$k，因此实际上可以将最终结果乘以。

请注意，以这种方式重写时，在循环中有2个操作，而不是3个（精确地说，在循环中还有$i增量、$i与$size\U数据的比较和$lastEMA值分配），因此通过这种方式，可以期望在16%到33%的范围内实现额外的加速。

此外，至少在某些情况下，还可以考虑其他改进：

第一个值乘以$k1m=1-$k几次，因此它们的贡献可能很小，甚至低于浮点精度（或可接受的误差）。

如果您可以假设较旧的数据与较新的数据具有相同的数量级，那么这个想法尤其有用，因为如果您只考虑最后的$n值，那么您所犯的错误是

<代码>$错误=$EMA\u of\u discarded\u数据*（1-$k）^$n。

因此，如果数量级大致相同，我们可以看出所做的相对误差为

$rel_err=$err/$lastEMA=$EMA_of_discarded_data*（1-$k）^$n/$lastEMA

这几乎等于（1-$k）^n。

假设“$lastEMA几乎等于$EMA\u丢弃的数据”：

• 假设您可以接受相对错误$rel\u err
  • 您可以安全地只考虑最后的$n值，其中（1-$k）^$n
  • 因此，基本上，在计算超过$n=log（1.1e-16）/log（1-k）的值时，您永远不会有优势
  • 举例说明，如果$范围=2000，则$n=log（1.1e-16）/log（1-2/2001）=36'746。
    • 我想知道额外的计算会在环岛内丢失是很有趣的==
    • 我认为，与您上次的样本数相比，这是一个相当小的数字，因此在这种情况下，加速效果可能很明显（我假设$range=2000对于您的应用程序来说是有意义的或很高的，但我不知道）
    • $rel\u err=1e-3$范围=2000=

    如果不能假设“$lastEMA几乎等于$EMA\u丢弃的数据”，事情就不那么容易了，但由于优势显著，继续下去可能有意义：

    • 我们需要重新考虑完整的公式：$rel\u err=$EMA\u of\u discarded\u data*（1-$k）^$n/$lastEMA
    • 你得找个好主意高估$EMA_of_discarded_data/$lastEMA
    • 一个快速的方法可能是取M=max（data）/min（data）

    计算可以重新编写为一种形式，其中它是独立术语的简单添加：

    $lastEMA = 0;
    $k = 2/($range+1);
    $k1m = 1 - $k;
    for ($i; $i<$size_data; ++$i) {
        $lastEMA += $k1m ^ ($size_data - 1 - $i) *  $data[$i];
    }
    $lastEMA = $lastEMA * $k;
    

    因此，如果实现语言支持并行化，那么数据集可以划分为4个（或8个或n个…基本上是可用的CPU核数）块，并可以并行计算每个块上的项之和，最后将各个结果相加。

    我没有详细说明这一点，因为这个答复已经非常长了，我认为这个概念已经表达出来了。