2

我目前正在测试不同的算法，这些算法确定 Integer 是否是真正的正方形。在我的研究中，我在 SOF 发现了这个问题： Fastest way to determine if an integer's square root is an integer

我对编程场景比较陌生。在测试问题中提出的不同算法时，我发现这个

bool istQuadratSimple(int64 x)
{
    int32 tst = (int32)sqrt(x);
    return tst*tst == x;
}

实际上比 A. Rex 在我发布的问题中提供的更快。我在这个测试中使用了一个 NS-Timer 对象，用一个 NSLog 打印我的结果。

我现在的问题是：如何以专业的方式进行速度测试？如何获得与我上面发布的问题中提供的结果相同的结果？

4

3 回答 3

1

我不确定是否有任何专业的方法来检查速度（如果有的话也告诉我）。对于您在问题中指向的方法，我可能会在 java 中执行此操作。

package Programs;

import java.math.BigDecimal;
import java.math.RoundingMode;

public class SquareRootInteger {

    public static boolean isPerfectSquare(long n) {
        if (n < 0)
            return false;

        long tst = (long) (Math.sqrt(n) + 0.5);
        return tst * tst == n;
    }

    public static void main(String[] args) {
        long iterator = 1;
        int precision = 10;
        long startTime = System.nanoTime(); //Getting systems time before calling the isPerfectSquare method repeatedly 
        while (iterator < 1000000000) {
            isPerfectSquare(iterator);
            iterator++;
        }
        long endTime = System.nanoTime(); // Getting system time after the 1000000000 executions of isPerfectSquare method
        long duration = endTime - startTime;
        BigDecimal dur = new BigDecimal(duration);
        BigDecimal iter = new BigDecimal(iterator);
        System.out.println("Speed "
                + dur.divide(iter, precision, RoundingMode.HALF_UP).toString()
                + " nano secs"); // Getting average time taken for 1 execution of method.

    }
}

您可以以类似的方式检查您的方法，并检查哪一种优于其他方法。

更新：- 由于 OP 可能对 java 不满意，我在代码中添加了注释以更清楚地传递这个想法。对于否决票，如果我能得到建设性的反馈，说明为什么会被否决，我将不胜感激。谢谢！！

于 2013-09-17T17:28:09.560 回答
1

在循环中仅调用此函数的问题是所有内容都将在缓存中（数据和指令）。你不会衡量任何明智的；我不会那样做的。

鉴于这个函数有多小，我会尝试查看这个函数和另一个函数生成的汇编代码，我会尝试根据汇编代码进行推理（例如指令数量和单个指令的成本） .

不幸的是，它只适用于微不足道/近乎微不足道的情况。例如，如果汇编代码相同，那么您就知道没有区别，您不需要测量任何东西。或者，如果一个代码与另一个代码相似，加上附加说明；在这种情况下，您知道执行时间越长执行时间越长。还有一些不太清楚的案例...... :(
（请参阅下面的更新。）

您可以使用-S -emit-llvm来自 clang 的-S标志和来自 gcc 的标志来获取程序集。

希望这有帮助。

更新：在评论中回应Prateek 的问题 “有没有办法确定一种特定算法的速度？”

是的，这是可能的，但它很快就会变得非常复杂。长话短说，忽略现代处理器的复杂性并简单地累积一些与指令相关的预定义成本可能会导致非常非常不准确的结果（由于缓存和管道等原因，估计值会降低 100 倍）。如果您尝试考虑现代处理器、分层缓存、管道等的复杂性，事情就会变得非常困难。参见例如Worst Case Execution Time Prediction。

除非您处于明确的情况（微不足道/接近微不足道的情况），例如生成的汇编代码是相同的，或者一个类似于另一个加上一些指令，否则也很难根据它们生成的汇编来比较算法。

但是，这里显示了两行的简单函数，为此，查看程序集可能会有所帮助。因此我的回答。

于 2013-09-17T17:33:16.703 回答
0
  1. 记录大量计算之前的时间值和之后的值。不同之处在于执行的时间。
  2. 编写一个 shell 脚本，您将在其中运行该程序。并运行 'time ./xxx.sh' 来获取它的运行时间。
于 2013-09-17T17:22:30.387 回答