gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:43:58 25 4
gpt4 key购买 nike

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

    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 倍。使用的测试用例是 1024x768 img 的 3 倍缩放。

原代码:使用时间:812后来的代码:使用时间:2140

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

最佳答案

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

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

关于java - Java中数组寻址的时间复杂度差异,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7653537/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com