在Java中如何证明一种算法比另一种算法更快

问题描述 投票：5回答：10

Java中是否有任何东西可以让我采用代码片段，并让我确切地看到要执行多少次“滴答”。我想证明我编写的算法比另一个算法更快。

java performance-testing
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));
    }
}
0
投票

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

3
投票

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

  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，则对于所有n > n0 c*f(n) >= n。大欧米伽是相同的东西，除了上限，大Theta f(n)仅表示它的大Oh f(n)和大Omega f(n)。这不是两个难题。

嗯，它变得更加复杂，因为我们可以讨论不同类型的运行时间，即“平均情况”，最佳情况和最坏情况。例如，在最坏的情况下，normall quicksort为O(n^2)，而对于随机列表，则为O(n log n)。

所以我跳过了T(n)的意思。基本上是“滴答声”的数量。一些机器指令（例如从内存中读取）比其他机器指令（例如添加）要花费更长的时间。但是，只要它们彼此之间只是一个恒定的因子，就大的目的而言，我们可以将它们视为相同，因为这只会改变c的值。

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

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

在此示例中，我们每个都有一条指令：初始化和，初始化i和返回值。循环发生n次，每次我们进行比较，加法和增量。因此，我们使用2的O(square(n)) = O(3 + 3n)和4的n0来获得c，我们可以轻松证明这是在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)

尽管您经常可以使用主定理，这是一种数学工具，可以节省您在此类问题上的时间。如果选中wikipedia，则可以找到主定理，如果您插入并播放上面的示例，则将得到相同的答案。

[有关更多信息，请查阅算法教科书，例如Levitin的“算法的设计与分析”

2
投票

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

long start = System.currentTimeMillis();

// your code

long end = System.currentTimeMillis();
System.out.println( "time: " + (end - start) );
1
投票

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

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

1
投票

我必须在今年的“数据结构”课程中主要进行这种算法效率证明。

[首先，我像他们提到上面一样测量时间。然后我通过每次平方增加该方法的输入数（10,100,1000，...）最后，我将时间测量值放在Excel文件中并绘制这些时间值的图形。

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

1
投票

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

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

Java Performance Testing

0
投票

我对Java框架不太熟悉，但是我可以通过以下方式做到：

  1. 定义一组可以用于两种算法的测试用例（主要是示例数据）>
  2. 采用计时方法来测量特定功能所花费的时间
  3. 创建一个for循环并执行方法A（例如，对整个测试数据重复执行1000次）。测量循环的时序，而不是单个函数的总和，因为时序函数在调用很多时会偏向于您的结果）
  4. 对方法B进行相同操作
  5. 比较您的结果并选择获胜者
0
投票

我会：

0
投票

如果两种算法对宏级别“滴答”的定义相同（例如，在树中行走一个节点），并且您的目标是证明您的算法在实现这些目标时所用的宏级别滴答声少于另外，到目前为止，最好的方法是仅对每个实现进行检测以计数那些滴答声。该方法是理想的，因为它不会奖励使代码执行速度更快但与算法无关的低级实现技巧。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.