如何通过常数优化数组乘法？

Question

给定以下代码，其中 a、b、c、d 等是常量：

Data[] dataArray;
Intermediate[] interArray;
Output[] outputArray;

for (int i = 0; i < length; i++)
{
  interArray[i] = (c * dataArray[i]) + (a * dataArray[i+1]);
  interArray[i] -= (b * interArray[i - 1]) + (d * interArray[i - 2]);
  outputArray[i] = interArray[i];
}

for (int i = ln-1; i > 0; i--)
{
  interArray[i - 1] = (e * dataArray[i]) + (f * dataArray[i-1]);
  interArray[i - 1] -= (g * interArray[i]) + (h * interArray[i+1]);
  outputArray[i] += interArray[i]; 
}

我该如何优化它？

我只想遍历数组一次。不幸的是，我依赖于这样一个事实，即第二个循环需要第一个循环填充 interArray。

我之所以要这样做是因为这个过程占用了我总运行时间的20%，我正在努力优化它。数组可以很大，类型通常很大PODs。我假设我正在进入缓存垃圾领域，这就是为什么我试图减少遍历数组的次数。没有 * 运算符，它只是标准乘法。

注意：我知道数组的上下边界由于越界而在这里崩溃和燃烧。我会手动处理这些。

如有任何建议，我们将不胜感激！可能我做不到更快，但我想至少尝试一下！

Answer 1

我不确定这是否会为您节省大量时间，但我认为您可以通过扩展项一次性完成计算。与 8 次乘法相比，这可以减少到 6 次乘法和累加。此外，您不需要中间数组。它看起来像这样（请仔细检查它的扩展）

Data[] dataArray;
Output[] outputArray;
auto DMinus2 = -c * d;
auto DMinus1 = -a - b*c;
auto D = c - a * b + f;
...

for (int i = 0; i < length; i++)
{
    outputArray[i] = DMinus2 * dataArray[i-2] + 
        DMinus1[i-1] * dataArray[i-1] +
        D * dataArray[i] + ....
        DPlus3 + dataArray[i+3];
}

编辑：

首先，抱歉，我的第一个回答并不完全正确。但是，我非常有信心可以简化循环。

比如在第一个循环中

interArray[i] = (c * dataArray[i]) + (a * dataArray[i+1]);
interArray[i] -= (b * interArray[i - 1]) + (d * interArray[i - 2]);
outputArray[i] = interArray[i];

可以简化为

interArray[i] = (c * dataArray[i]) + (a * dataArray[i+1]) -
    (b * interArray[i - 1]) + (d * interArray[i - 2]);
outputArray[i] = interArray[i];

我假设范围外的值为 0 考虑 i = 0 那么我们有

outputArray[0] = (c * dataArray[0]) + (a * dataArray[1]);

i = 1 给出

outputArray[1] = (c * dataArray[1]) + (a * dataArray[2]) - 
    b * outputArray[0];

i = 2 给出

outputArray[2] = (c * dataArray[2]) + (a * dataArray[3]) - 
    b * outputArray[1] - d * outputArray[0];

所以，我认为我们可以概括第一个循环以删除中间数组

outputArray[i] = (c * dataArray[i]) + (a * dataArray[i+1]) - 
    b * outputArray[i-1] - d * outputArray[i-2];

第二个循环也应该如此。再次复习我的数学，我不完全确定是否有可能将这两个循环结合起来。我会继续考虑这个问题，因为可能有办法做到这一点。希望删除中间存储应该有所帮助。

如何通过常数优化数组乘法？

How can I optimise array multiplication by constant?

c++

arrays

optimization