Разница во временной сложности при адресации массива в 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 раза медленнее, чем предыдущий код. Используется 3-кратный зум 1024x768 img.

прежний код: использованное время: 812 позже код: использованное время: 2140

Так в чем же причина разницы во времени?

Answer 1

У вас есть 8 вычислений Math.floor () / Math.ceil () в более позднем коде вместо 4. Это проблема.

Вычисление намного медленнее, чем выделение места для локальной переменной.

Answer 2

В: Сколько раз вы называете «floor» и «ceil» в первом случае? Второй случай? ;)

В: Мне интересно, будет ли это работать быстрее, чем в первом случае:

    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

Крошечные операции сохранения и поиска локальной переменной бледнеют по сравнению с Math.floor и Math.ceil.Кроме того, вы чаще применяете int во втором фрагменте.

Answer 4

Позднее, вероятно, будет медленнее, потому что он делает больше работы. Установка временной переменной тривиальна, но вычисление пола и потолка может быть на удивление дорогим.

Кстати: когда x положительный, (int) Math.floor(x) совпадает с (int) x, поэтому вам не нужно рассчитывать его дважды.

Также можно предположить, что xc = xf + 1 в этой ситуации и аналогично для y

Answer 5

Во втором вы повторяете вычисления. Захватив это в переменную в первом примере, вы избежите повторения вычислений.

Answer 6

floor и ceil имеют стоимость исполнения.

Ваш второй случай вызывает их вдвое чаще.

Answer 7

Вы можете просто привести double к int вместо использования Math.floor ().Это будет быстрее.

вместо:

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

просто:

inputArray[(int) x]