Java中数组寻址的时间复杂度差异

Question

所以在编码涉及时间复杂度的图像处理函数时，我有一个随机的问题。以下是我的原始代码片段:

    long start = System.currentTimeMillis();
    for (int i = 0; i < newWidth; i++) {
        for (int j = 0; j < newHeight; j++) {
            double x = i * scaleX;
            double y = j * scaleY;
            double xdiff = x - (int) x;
            double ydiff = y - (int) y;
            int xf = (int) Math.floor(x);
            int xc = (int) Math.ceil(x);
            int yf = (int) Math.floor(y);
            int yc = (int) Math.ceil(y);
            double out = inputArray[xf][yf] * (1 - xdiff) * (1 - ydiff)
                    + inputArray[xc][yf] * xdiff * (1 - ydiff)
                    + inputArray[xf][yc] * (1 - xdiff) * ydiff
                    + inputArray[xc][yc] * xdiff * ydiff;
            outputArray[i][j] = (int) out;
        }
    }
    long elapsed = System.currentTimeMillis() - start;
    System.out.println("Time used: " + elapsed);

与该代码出来后，我想知道它是否会更快，而不是创建4个临时变量的地板和天花板值，而是，直接在数组索引中计算它们。所以我这样修改:

    long start = System.currentTimeMillis();
    for (int i = 0; i < newWidth; i++) {
        for (int j = 0; j < newHeight; j++) {
            double x = i * scaleX;
            double y = j * scaleY;
            double xdiff = x - (int) x;
            double ydiff = y - (int) y;
            double out = inputArray[(int) Math.floor(x)][(int) Math.floor(y)] * (1 - xdiff) * (1 - ydiff)
                    + inputArray[(int) Math.ceil(x)][(int) Math.floor(y)] * xdiff * (1 - ydiff)
                    + inputArray[(int) Math.floor(x)][(int) Math.ceil(y)] * (1 - xdiff) * ydiff
                    + inputArray[(int) Math.ceil(x)][(int) Math.ceil(y)] * xdiff * ydiff;
            outputArray[i][j] = (int) out;
        }
    }
    long elapsed = System.currentTimeMillis() - start;
    System.out.println("Time used: " + elapsed);

我期望后者更快(因为你不必写一个临时变量，然后访问它)，但事实证明，后者至少比前者慢2.5倍。使用的测试用例是1024x768img的3倍缩放。

前代码:使用时间:812使用时间:2140

那么造成时差的原因是什么呢?

Answer 1

在后面的代码中有8个Math.floor()/Math.ceil()计算而不是4个。

计算比为局部变量分配空间慢得多。

Answer 2

问:在第一种情况下，你调用了几次"floor"one_answers" ceeil " ?第二种情况呢?;)

Q:我想知道这是否会比第一种情况运行得更快:

    long start = System.currentTimeMillis();
    for (int i = 0; i < newWidth; i++) {
        double x = i * scaleX;
        double xdiff = x - (int) x;
        int xf = (int) Math.floor(x);
        int xc = (int) Math.ceil(x);
        for (int j = 0; j < newHeight; j++) {
            double y = j * scaleY;
            double ydiff = y - (int) y;
            int yf = (int) Math.floor(y);
            int yc = (int) Math.ceil(y);
            double out = inputArray[xf][yf] * (1 - xdiff) * (1 - ydiff)
                    + inputArray[xc][yf] * xdiff * (1 - ydiff)
                    + inputArray[xf][yc] * (1 - xdiff) * ydiff
                    + inputArray[xc][yc] * xdiff * ydiff;
            outputArray[i][j] = (int) out;
        }
    }
    long elapsed = System.currentTimeMillis() - start;
    System.out.println("Time used: " + elapsed);

Answer 3

floor和ceil具有性能成本

第二个案例调用它们的次数是原来的两倍。

Answer 4

第二个是重复计算。在第一个示例中，通过在变量中捕获这一点，可以避免重复计算。

Answer 5

后者可能比较慢，因为它做的工作更多。设置一个临时变量是微不足道的，但是计算floor和ceil可能会非常昂贵。

BTW:当x为正时，(int) Math.floor(x)与(int) x相同，因此您不需要计算两次。

同样，您可以假设在这种情况下xc = xf + 1和y

Answer 6

与Math相比，保存和查找局部变量的微小操作显得微不足道。地板和数学。天花板。此外，在第二个代码片段中，您将更频繁地强制转换为int。

Answer 7

您可以简单地将double转换为int，而不是使用Math.floor()。这样会更快。

代替:

inputArray[(int) Math.floor(x)]

:

inputArray[(int) x]