对于一项作业，我目前正在尝试测量矩阵链问题的迭代解决方案与递归解决方案之间的性能（空间/时间）差异。
问题的要点和我用于迭代版本的解决方案可以在这里找到：http://www.geeksforgeeks.org/dynamic-programming-set-8-matrix-chain-multiplication/ http://www.geeksforgeeks.org/dynamic-programming-set-8-matrix-chain-multiplication/
我通过两个函数运行给定输入 10 次，测量每个函数的空间和时间性能。非常有趣的是，虽然递归解决方案在第一次调用时比迭代解决方案运行得慢得多，但在连续调用时它的性能要好得多，而且速度要快得多。除了用于计算内存使用量之外，这些函数不使用任何类全局变量。为什么会出现这种情况？这是编译器正在做的事情还是我错过了一些明显的事情？
注意：我知道我测量内存的方法是错误的，计划改变它。
Main：初始化数组并将其传递给运行函数
public static void main(String[] args) {
int s[] = new int[] {30,35,15,5,10,100,25,56,78,55,23};
runFunctions(s, 15);
}
runFunctions：运行两个函数 2 * n 次，测量空间和时间并在最后打印结果
private static void runFunctions(int[]arr , int n){
final Runtime rt = Runtime.getRuntime();
long iterativeTime[] = new long [n],
iterativeSpace[] = new long [n],
recursiveSpace[] = new long [n],
recursiveTime[] = new long [n];
long startTime, stopTime, elapsedTime, res1, res2;
for (int i = 0; i <n; i++){
System.out.println("Measuring Running Time");
//measure running time of iterative
startTime = System.nanoTime();
res1 = solveIterative(arr, false);
stopTime = System.nanoTime();
elapsedTime = stopTime - startTime;
iterativeTime[i] = elapsedTime;
//measure running time of recursive
startTime = System.nanoTime();
res2 = solveRecursive(arr, false);
stopTime = System.nanoTime();
elapsedTime = stopTime - startTime;
recursiveTime[i] = elapsedTime;
System.out.println("Measuring Space");
//measure space usage of iterative
rt.gc();
res1 = solveIterative(arr, true);
iterativeSpace[i] = memoryUsage;
//measure space usage of recursive
rt.gc();
res2 = solveRecursive(arr, true);
recursiveSpace[i] = memoryUsage;
rt.gc();
if (res1 != res2){
System.out.println("Error! Results do not match! Iterative Result: " + res1 + " Recursive Result: " + res2);
}
}
System.out.println("Time Iterative: " + Arrays.toString(iterativeTime));
System.out.println("Time Recursive: " + Arrays.toString(recursiveTime));
System.out.println("Space Iterative: " + Arrays.toString(iterativeSpace));
System.out.println("Space Recursive: " + Arrays.toString(recursiveSpace));
}
solveRecursive：doRecursion 的引导程序
private static int solveRecursive(int[] s, boolean measureMemory){
memoryUsage = 0;
maxMemory = 0;
int n = s.length - 1;
int[][] m = new int[n][n];
int result;
if (measureMemory){
memoryUsage += MemoryUtil.deepMemoryUsageOf(n);
memoryUsage += MemoryUtil.deepMemoryUsageOf(s);
memoryUsage += MemoryUtil.deepMemoryUsageOf(m);
result = doRecursion(0, n - 1, m, s);
memoryUsage += MemoryUtil.deepMemoryUsageOf(result);
System.out.println("Memory Used: " + memoryUsage);
}
else
{
result = doRecursion(0, n - 1, m, s);
}
return result;
}
doRecursion：递归地求解函数
private static int doRecursion(int i, int j, int[][] m, int s[]){
if (m[i][j] != 0){
return m[i][j];
}
if (i == j){
return 0;
}
else
{
m[i][j] = Integer.MAX_VALUE / 3;
for (int k = i; k <= j - 1; k++){
int q = doRecursion(i, k, m, s) + doRecursion(k + 1, j, m, s) + (s[i] * s[k + 1] * s[j + 1]);
if (q < m[i][j]){
m[i][j] = q;
}
}
}
return m[i][j];
}
solveIterative：迭代解决问题
private static int solveIterative(int[] s, boolean measureMemory) {
memoryUsage = 0;
maxMemory = 0;
int n = s.length - 1;
int i = 0, j = 0, k= 0, v = 0;
int[][] m = new int[n][n];
for (int len = 2; len <= n; len++) {
for (i = 0; i + len <= n; i++) {
j = i + len - 1;
m[i][j] = Integer.MAX_VALUE;
for (k = i; k < j; k++) {
v = m[i][k] + m[k + 1][j] + s[i] * s[k + 1] * s[j + 1];
if (m[i][j] > v) {
m[i][j] = v;
}
}
}
}
if (measureMemory){
memoryUsage += MemoryUtil.deepMemoryUsageOf(n);
memoryUsage += MemoryUtil.deepMemoryUsageOf(m);
memoryUsage += MemoryUtil.deepMemoryUsageOf(i);
memoryUsage += MemoryUtil.deepMemoryUsageOf(j);
memoryUsage += MemoryUtil.deepMemoryUsageOf(k);
memoryUsage += MemoryUtil.deepMemoryUsageOf(v);
memoryUsage += MemoryUtil.deepMemoryUsageOf(s);
System.out.println("Memory Used: " + memoryUsage);
}
return m[0][n - 1];
}
Output:
Time Iterative: [35605, 12039, 20492, 17674, 17674, 12295, 11782, 19467, 16906, 18442, 21004, 19980, 18955, 12039, 13832]
Time Recursive: [79918, 4611, 8453, 6916, 6660, 6660, 4354, 6916, 18699, 7428, 13576, 5635, 4867, 3330, 3586]
Space Iterative: [760, 760, 760, 760, 760, 760, 760, 760, 760, 760, 760, 760, 760, 760, 760]
Space Recursive: [712, 712, 712, 712, 712, 712, 712, 712, 712, 712, 712, 712, 712, 712, 712]
