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

Question

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

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

我已经做了什么：
隔离$k因此不计算10000次以上
只保留最新计算的EMA，而不是将它们全部保存在一个数组中
使用for()而不是foreach()
$data[]数组没有键；它是一个基本数组
这使我可以将执行时间从2000毫秒减少到大约500毫秒，值为15000！
什么不起作用：
使用SplFixedArray（），执行1000000个值的时间只缩短了~10ms
使用PHP_Trader extension，这将返回一个包含所有ema而不是最新ema的数组，并且速度较慢
用C语言编写和运行相同的算法，运行超过2000000个值只需13ms显然，使用编译的低级语言似乎有帮助；P
我应该从这里去哪里？这段代码最终会在ubuntu上运行，所以我应该选择哪种语言？PHP是否能够调用并向脚本传递如此大的参数？

Answer 1

显然，使用扩展实现会给您带来显著的提升。
此外，微积分本身也可以改进，你可以用任何你选择的语言添加它。
很容易看出，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 increment，$i与$size_data和$lastema value assignation进行比较），这样您就可以在16%到33%的范围内实现额外的加速。
此外，至少在某些情况下，还可以考虑其他改进：
只考虑最后的值
第一个值乘以$k1m = 1 - $k几倍，因此它们的贡献可能很小，甚至低于浮点精度（或可接受的误差）。
如果您可以假设较旧的数据与较新的数据具有相同的数量级，那么这个想法特别有用，因为如果您只考虑最后的$n值，那么您所犯的错误是
$err = $EMA_of_discarded_data * (1-$k) ^ $n。
因此，如果数量级大致相同，我们可以看出相对误差是
$rel_err = $err / $lastEMA = $EMA_of_discarded_data * (1-$k) ^ $n / $lastEMA
这几乎等于简单的(1-$k) ^ $n。
假设“$lastEMA几乎等于$EMA_of_discarded_data”：
假设您可以接受一个相对错误$rel\u err
在（1-$k）^$n<$rel_err的情况下，您可以安全地只考虑最后的$n值。
意味着您可以预先计算（在循环之前）$n=log（$rel_err）/log（1-$k）并仅考虑最后的$n值来计算所有值。
如果数据集非常大，这可以给出一个合理的加速。
考虑到对于64位浮点数，相对精度（与尾数相关）为2^-53（大约为1.1e-16，对于32位浮点数，相对精度仅为2^-24=5.96e-8），因此无法获得比此相对误差更好的结果
所以基本上，在计算超过$n=log（1.1e-16）/log（1-$k）的值时，您不应该有任何优势。
举例来说，如果$range=2000，那么$n=log（1.1e-16）/log（1-2/2001）=36'746。
我想知道额外的计算会在循环中丢失是很有意思的，这是无用的，最好不要这样做。
现在举一个例子，如果可以接受大于浮点精度的相对误差$rel_err=1ppm=1e-6=0.00001%=6个有效的十进制数字，则$n=log（1.1e-16）/log（1-2/2001）=13'815
我认为这是一个相当小的数字与您的上一个样本数字相比，因此在这种情况下，加速可能是明显的（我假设$range=2000对您的应用程序是有意义的或高的，但我不知道）。
只是其他几个数字，因为我不知道你的典型数字是什么：
$rel_err=1e-3；$range=2000=>$n=6'907
$rel_err=1e-3；$range=200=>$n=691
$rel_err=1e-3；$range=20=>$n=69
$rel_err=1e-6；$range=2000=>$n=13815
$rel_err=1e-6；$range=200=>$n=1381
$rel_err=1e-6；$range=20=>$n=138
如果不能假设“$lastema几乎等于$ema_of_discarded_data”的话，事情就不那么容易了，但既然优势是显著的，那么继续下去是有意义的：
我们需要重新考虑完整的公式：$rel_err=$EMA_of_discarded_data*（1-$k）^$n/$lastEMA
所以$n=log（$rel_err*$lastema/$ema戋u discarded戋data）/log（1-$k）=（log（$rel戋err）+log（$lastema/$ema戋u discarded戋data））/log（1-$k）
中心点是计算$lastema/$ema_of_discarded_data（当然不实际计算$lastema或$ema_of_discarded_data）
一种情况是当我们事先知道例如$ema_of_discarded_data/$lastema在这种情况下，$n<（log（$rel_err/m））/log（1-$k）
如果你不能给出任何M号
你必须找到一个好主意来高估$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核数）块，并且可以计算每个块上的项的总和，并行地求出最后的单个结果的总和。
我不详细说明这个问题，因为这个答复已经很长了，我认为这个概念已经表达出来了。