保存计算值而不是重新计算多次的术语是什么？

Question

当你有这样的代码时（用 java 编写，但适用于任何类似的语言）：

public static void main(String[] args) {
    int total = 0;
    for (int i = 0; i < 50; i++)
        total += i * doStuff(i % 2); // multiplies i times doStuff(remainder of i / 2)
}

public static int doStuff(int i) {
    // Lots of complicated calculations
}

您可以看到还有改进的余地。 doStuff(i % 2) 只有 returns 两个不同的值 - 一个用于 doStuff(0) 偶数，一个用于 doStuff(1) 奇数。因此，您每次都通过说 doStuff(i % 2) 来重新计算这些值，从而浪费了大量计算 time/power。你可以这样改进：

public static void main(String[] args) {
    int total = 0;
    boolean[] alreadyCalculated = new boolean[2];
    int[] results = new int[2];
    for (int i = 0; i < 50; i++) {
        if (!alreadyCalculated[i % 2]) {
            results[i % 2] = doStuff(i % 2);
            alreadyCalculated[i % 2] = true;
        }
        total += i * results[i % 2];
    }
}

现在它访问存储的值而不是每次都重新计算。像这样保留数组似乎很愚蠢，但是对于从 i = 0, i < 500 循环并且每次都检查 i % 32 之类的情况，数组是一种优雅的方法。

这种代码优化有专门的术语吗？我想阅读更多关于它的不同形式和约定的信息，但我缺乏简洁的描述。

Answer 1

Is there a term for this kind of code optimization?

是的，有：

In computing, memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

https://en.wikipedia.org/wiki/Memoization

Answer 2

公共子表达式消除（CSE）与此有关。这种情况是将循环不变计算提升到循环之外的组合。

我同意 CBroe 的观点，您可以将这种特定形式的缓存记忆化称为缓存记忆化，尤其是您使用笨重的 alreadyCalculated 数组实现它的方式。您可以优化它，因为您知道哪些调用将是新值，哪些将重复。通常，为了所有调用者的利益，您会在被调用函数内使用静态数组实现记忆。理想情况下，有一个标记值可用于标记尚未计算结果的条目，而不是为此维护一个单独的数组。或者对于一组稀疏的输入值，只需使用散列（而不是例如具有 2^32 个条目的数组）。

你也可以避免主循环中的if。

public class Optim
{
  public static int doStuff(int i) { return (i+5) << 1; }
  public static void main(String[] args)
  {

    int total = 0;
    int results[] = new int[2];

    // more interesting if we pretend the loop count isn't known to be > 1, so avoiding calling doStuff(1) for n=1 is useful.
    // otherwise you'd just do int[] results = { doStuff(0), doStuff(1) };

    int n = 50;

    for (int i = 0 ; i < Math.min(n, 2) ; i++) {
        results[i] = doStuff(i);
        total += i * results[i];
    }
    for (int i = 2; i < n; i++) { // runs zero times if n < 2
        total += i * results[i % 2];
    }
    System.out.print(total);
  }
}

当然，在这种情况下我们可以进一步优化很多。 sum(0..n) = n * (n+1) / 2，所以我们可以用它来根据 doStuff(0)（偶数项之和）和 doStuff(1)（奇数项之和）得到一个封闭形式（非循环）的解决方案).所以我们只需要两个 doStuff() 结果各一次，避免任何记忆的需要。

保存计算值而不是重新计算多次的术语是什么？

What's the term for saving values of calculations instead of recalculating multiple times?

optimization

terminology

temporary-objects