Блог

Итак, у меня возник случайный вопрос при кодировании функции обработки изображений, которая связана с временной сложностью. Ниже приведен мой оригинальный фрагмент кода:

     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 временные переменные для значений floor и ceiling, а вместо этого вычислять их непосредственно при индексации массива. Поэтому я изменил его таким образом:

     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-кратное увеличение изображения 1024×768.

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

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

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

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

Вопрос: Сколько раз вы вызываете «этаж» и «потолок» в первом случае? Второй случай? 😉

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

     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);
  

floor и ceil имеют затраты на производительность.

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

Во втором вы повторяете вычисления. Фиксируя это в переменной в первом примере, вы избегаете повторения вычислений.

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

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

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

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

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

вместо:

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

просто:

 inputArray[(int) x]