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

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)只返回两个不同的值 - 一个用于偶数的doStuff(0)，另一个用于奇数的doStuff(1)。因此，您每次通过说doStuff(i % 2)重新计算这些值会浪费大量计算时间/功耗。你可以这样改进：

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

是否有这种代码优化术语？

是的，有：

在计算中，记忆化是主要用于通过存储昂贵函数调用的结果，并返回高速缓存的结果以加速的计算机程序的优化技术时相同的输入再次发生。

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

Answer 2

共子表达式消去（CSE）与此有关。这种情况是这种情况的组合，并且提出了循环不变的循环不变计算。

我同意CBroe的观点，你可以称之为这种特定形式的缓存记忆，尤其是你用笨重的alreadyCalculated数组实现它的方式。你可以优化这些，因为你知道哪些调用是新值，哪些调用是重复的。通常你会在被调用的函数中使用一个静态数组来实现memoization，这是为了所有调用者的好处。理想情况下，您可以使用标记值来标记尚未计算结果的条目，而不是为此维护单独的数组。或者对于一组稀疏的输入值，只需使用散列（而不是例如具有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); 
    } 
} 

当然，在这种情况下，我们可以进一步优化。因此我们可以使用它得到一个关于doStuff(0)（偶数项的和）和doStuff(1)（奇数项的和）的封闭形式（非循环）解决方案。所以我们每次只需要两个doStuff()结果，避免了任何需要记忆的情况。