英文:
Why is running time of the same algorithm different in doubling ratio test?
问题
我正在分析暴力的三数求和算法。假设这个算法的运行时间是 T(N)=aN^3。我正在运行这个 ThreeSum.java 程序，使用 8Kints.txt 的运行时间来计算常数 a。在计算出 a 后，我要猜测 16Kints.txt 的运行时间。以下是我的 ThreeSum.java 文件：
public class ThreeSum {
public static int count(int[] a) {
// 计算和为0的三元组数量。
int N = a.length;
int cnt = 0;
for (int i = 0; i < N; i++)
for (int j = i + 1; j < N; j++)
for (int k = j + 1; k < N; k++)
if (a[i] + a[j] + a[k] == 0)
cnt++;
return cnt;
}
public static void main(String[] args) {
In in = new In(args[0]);
int[] a = in.readAllInts();
Stopwatch timer = new Stopwatch();
int count = count(a);
StdOut.println("elapsed time = " + timer.elapsedTime());
StdOut.println(count);
}
}
当我像这样运行时：
$ java ThreeSum 8Kints.txt
我得到了这个结果：
elapsed time = 165.335
现在，在一个倍增比实验中，我在另一个客户端内部使用相同的方法，并使用多个文件作为参数运行此客户端，想要尝试比较 8Kints.txt 的运行时间与上面的方法，但实际上得到了不同的结果，更快的结果。以下是我的 DoublingRatio.java 客户端：
public class DoublingRatio {
public static double timeTrial(int[] a) {
Stopwatch timer = new Stopwatch();
int cnt = ThreeSum.count(a);
return timer.elapsedTime();
}
public static void main(String[] args) {
In in;
int[][] inputs = new int[args.length][];
for (int i = 0; i < args.length; i++) {
in = new In(args[i]);
inputs[i] = in.readAllInts();
}
double prev = timeTrial(inputs[0]);
for (int i = 1; i < args.length; i++) {
double time = timeTrial(inputs[i]);
StdOut.printf("%6d %7.3f ", inputs[i].length, time);
StdOut.printf("%5.1f\n", time / prev);
prev = time;
}
}
}
当我像这样运行时：
$ java DoublingRatio 1Kints.txt 2Kints.txt 4Kints.txt 8Kints.txt 16Kints.txt 32Kints.txt
我得到了更快的结果，我想知道为什么：
N sec ratio
2000 2.631 7.8
4000 4.467 1.7
8000 34.626 7.8
我知道这与 Java 有关，而不是算法吗？Java 在幕后是否对某些东西进行了优化？
英文:
I am analyzing brute force Three Sum algorithm. Let's say the running time of this algorithm is T(N)=aN^3. What I am doing is that I am running this ThreeSum.java program with 8Kints.txt and using that running time to calculate constant a. After calculating a I am guessing what the running time of 16Kints.txt is. Here is my ThreeSum.java file:
public class ThreeSum {
public static int count(int[] a) {
// Count triples that sum to 0.
int N = a.length;
int cnt = 0;
for (int i = 0; i < N; i++)
for (int j = i + 1; j < N; j++)
for (int k = j + 1; k < N; k++)
if (a[i] + a[j] + a[k] == 0)
cnt++;
return cnt;
}
public static void main(String[] args) {
In in = new In(args[0]);
int[] a = in.readAllInts();
Stopwatch timer = new Stopwatch();
int count = count(a);
StdOut.println("elapsed time = " + timer.elapsedTime());
StdOut.println(count);
}
}
When I run like this:
$ java ThreeSum 8Kints.txt
I get this:
elapsed time = 165.335
And now in doubling ratio experiment where I use the same method inside another client and run this client with multiple files as arguments and wanna try to compare the running time of 8Kints.txt with above method but I get different result actually faster result. Here is my DoublingRatio.java client:
public class DoublingRatio {
public static double timeTrial(int[] a) {
Stopwatch timer = new Stopwatch();
int cnt = ThreeSum.count(a);
return timer.elapsedTime();
}
public static void main(String[] args) {
In in;
int[][] inputs = new int[args.length][];
for (int i = 0; i < args.length; i++) {
in = new In(args[i]);
inputs[i] = in.readAllInts();
}
double prev = timeTrial(inputs[0]);
for (int i = 1; i < args.length; i++) {
double time = timeTrial(inputs[i]);
StdOut.printf("%6d %7.3f ", inputs[i].length, time);
StdOut.printf("%5.1f\n", time / prev);
prev = time;
}
}
}
When I run this like:
$ java DoublingRatio 1Kints.txt 2Kints.txt 4Kints.txt 8Kints.txt 16Kints.txt 32Kints.txt
I get faster reuslt and I wonder why:
N sec ratio
2000 2.631 7.8
4000 4.467 1.7
8000 34.626 7.8
I know it is something that has to do with Java not the algorithm? Does java optimizes some things under the hood.
专注分享java语言的经验与见解，让所有开发者获益！
评论