6

Java中是否有任何东西可以让我获取代码片段并让我准确查看执行需要多少“滴答”。我想证明我写的一个算法比另一个更快。

4

10 回答 10

6

“蜱虫”？不，我建议您每次运行几次并比较平均结果：

public class AlgorithmDriver {
    public static void main(String [] args) {
        int numTries = 1000000;
        long begTime = System.currentTimeMillis();
        for (int i = 0; i < numTries; ++i) {
            Algorithm.someMethodCall();
        }
        long endTime = System.currentTimeMillis();
        System.out.printf("Total time for %10d tries: %d ms\n", numTries, (endTime-begTime));
    }
}
于 2011-08-02T23:26:27.413 回答
4

您可能会问两个不同的问题：

  1. 如何测量 java 实现的运行时间（基准测试）
  2. 如何证明算法的渐近运行时间

对于其中的第一个，我不会使用此处发布的解决方案。他们大多不完全正确。Forst，它可能System.nanoTime比System.currentTimeMillis. 其次，您需要使用 try catch 块。第三，统计你的代码在指标之外多次运行的运行时间，这样你就可以有一个更完整的画面。多次运行看起来像这样的代码：

long totalTime = 0;
long startTime = System.nanoTime();
try{
   //method to test
} finally {
   totalTime = System.nanoTime() - startTime;
}

正确进行基准测试很难。例如，在测试之前，您必须让代码“预热”几分钟。尽早并经常进行基准测试，但不要过分相信您的基准。特别是小型微型基准几乎总是以这样或那样的方式存在。

解释您的问题的第二种方法是关于渐近运行时间。事实是这几乎与 Java 无关，它是一般的计算机科学。这里我们要问的问题是：哪些曲线根据输入大小来描述我们算法的运行时间行为。

首先是理解 Big-Oh 符号。我会尽力而为，但 SO 不支持数学符号。 O(f(n))表示一组算法，使得n无穷大的极限f(n)在算法运行时间上限的常数因子内。形式上，当且T(n)仅O(f(n))当存在一些常数n0和一些常数c时，对于 all n > n0 c*f(n) >= n。Big Omega 是同样的东西，除了上限，而 big Thetaf(n)只是意味着它的 big Ohf(n)和 big Omega f(n)。这不是两个难的。

好吧，它变得有点复杂，因为我们可以讨论不同类型的运行时间，即“平均情况”、最佳情况和最坏情况。例如，normall 快速排序是O(n^2)最坏的情况，但O(n log n)适用于随机列表。

所以我跳过了什么T(n)意思。基本上它是“滴答声”的数量。一些机器指令（比如从内存中读取）比其他机器指令（比如添加）花费的时间要长得多。但是，只要它们只是彼此分开的常数因子，我们就可以将它们都视为 big Oh 的目的，因为它只会改变 的值c。

证明渐近界并不难。对于简单的结构化编程问题，您只需数数

public int square(int n){
   int sum = 0
   for(int i = 0, i < n, i++){
     sum += n
   }
   return sum
}

在这个例子中，我们各有一条指令：初始化 sum、初始化 i 和返回值。n每次我们进行比较、加法和增量时，循环都会发生几次。所以我们O(square(n)) = O(3 + 3n)使用n02 和c4 我们可以很容易地证明这是在O(n). 您始终可以通过删除多余的常数项并除以常数倍数来安全地简化大 Oh 表达式。

当您遇到递归函数时，您必须解决递归关系。如果你有一个功能，T(n) = 2*T(n/2) + O(1)你想找到一个封闭的形式解决方案。有时您必须手动或使用计算机代数系统来完成。T(1) = O(1), T(2) = O(3), T(4) = O(7), T(8) = (15)对于这个例子，使用前向替换，我们可以看到看起来很像的模式（在滥用符号中）O(2n - 1)，以证明这是正确的值：

 T(n) = 2*T(n/2) + 1
 T(n) = 2*(2(n/2) - 1) + 1
 T(n) = 2*(n-1) + 1
 T(n) = 2n - 2 + 1
 T(n) = 2n - 1

正如我们之前看到的，您可以简化O(2n -1)为O(n)

更常见的是，您可以使用主定理，它是一种数学工具，可以节省您解决此类问题的时间。如果您查看维基百科，您可以找到主定理，如果您即插即用上面的示例，您会得到相同的答案。

有关更多信息，请查看 Levitin 的“算法设计与分析”等算法教科书

于 2011-08-03T00:21:57.950 回答
2

您可以System.currentTimeMillis()用来获取开始和结束时间。

long start = System.currentTimeMillis();

// your code

long end = System.currentTimeMillis();
System.out.println( "time: " + (end - start) );
于 2011-08-02T23:22:44.030 回答
1

您可以使用 System.currentTimeMillis() 或 System.nanoTime() （它们具有不同的特性）来测量挂壁时间。这相对容易，因为您只需在最后打印出差异。

如果您需要计算特定操作（这在算法中很常见），最简单的方法是在操作完成时简单地增加一个计数器，然后在完成时打印它。 long非常适合这个。对于多个操作，请使用多个计数器。

于 2011-08-02T23:28:30.300 回答
1

我必须在今年的数据结构课上主要做这个算法效率证明。

首先，我像上面提到的那样测量时间。然后我每次都增加方法的输入数（10,100,1000,...） 最后，我将时间测量值放入 Excel 文件并为这些时间值绘制图形。

通过这种方式，您可以稍微检查一种算法是否比其他算法快。

于 2011-08-02T23:36:46.610 回答
1

我会：

  • 为当前算法提出几个数据集：一个表现良好的数据集，一个表现良好的数据集，以及一个表现不佳的数据集。您想证明您的新算法在每种情况下都优于当前算法。
  • 多次运行并测量每个算法的性能，以增加三个数据集的每一个的输入大小，然后取平均值、标准差等。标准差将显示算法性能一致性的粗略衡量标准。
  • 最后查看数字并根据您的情况确定重要的是：哪种算法的性能更适合您大部分时间将拥有的输入类型，以及当输入不是最佳时它如何降低。

算法的计时不一定是一切——内存占用也很重要吗？一种算法在计算上可能更好，但它可能会在运行时创建更多对象......等等。只是想指出除了纯粹的时间安排之外，还有更多需要考虑的事情！

于 2011-08-02T23:58:22.277 回答
1

我不会像其他一些人建议的那样以毫秒为单位使用当前时间。ThreadMXBeans 提供的方法更准确（我不敢说 100% 准确）。

它们实际上测量的是线程占用的 cpu 时间，而不是经过的系统时间，这可能由于底层操作系统执行的上下文切换而出现偏差。

Java 性能测试

于 2012-09-24T18:45:42.390 回答
0

我对 Java 框架不太熟悉，但我会这样做：

  1. 定义一组可用于两种算法的测试用例（主要是示例数据）
  2. 实施计时方法来测量特定功能所花费的时间量
  3. 创建一个 for 循环并执行方法 A（重复，例如对整个测试数据执行 1000 次）。测量循环的时间，而不是单个函数的总和，因为时间函数会在大量调用时使您的结果产生偏差）
  4. 对方法 B 执行相同操作
  5. 比较您的结果并选择获胜者
于 2011-08-02T23:25:03.547 回答
0

如果两种算法都对宏观级别的“滴答”有相同的定义（例如，在树中遍历一个节点），并且您的目标是证明您的算法以比另一种更少的宏观级别滴答数来实现其目标，那么到目前为止，最好的方法是只检测每个实现来计算这些滴答声。这种方法是理想的，因为它不会奖励可以使代码执行得更快但与算法无关的低级实现技巧。

如果您没有那么奢侈，但您试图计算哪种方法使用最少的 CPU 资源解决问题，与此处列出的涉及 System.currentTimeMillis 等的方法相反，我将使用外部方法：linux 时间命令将是理想的。您让每个程序在同一组（大）输入上运行，最好花费几分钟或几小时的时间来处理，然后只运行time java algo1vs time java algo2.

于 2011-08-03T00:02:16.437 回答
0

如果您的目的是比较两段代码之间的性能，最好的方法是使用 JMH。您可以通过 maven 导入，现在在 openjdk 12 中是官方的。

https://openjdk.java.net/projects/code-tools/jmh/

于 2020-04-27T13:45:51.550 回答