Оптимизация Java-кода при матричном оконном вычислении выполняется быстрее

Question

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

Я придумал три варианта:

• Самый простой способ, тот, который пересчитывает окно для каждого пикселя
• Более оптимизированный способ, использующий очередь для хранения сумм столбцов окна и циклический переход по столбцам матрицы, обновляет эту очередь, добавляя новый элемент и удаляя старые элементы
• Еще более оптимизированный способ, при котором не нужно пересчитывать очередь для каждой строки, но постепенно корректировать ранее сохраненную

Я реализовал их в c ++ , используя очередь для второго метода и комбинацию deques для третьего (мне нужно перебирать их элементы без уничтожить их) и забил их время, чтобы увидеть, было ли реальное улучшение. похоже, что третий способ действительно быстрее.

Затем я попытался перенести код на Java (и должен признать, что мне это не очень удобно). Я использовал ArrayDeque для второго метода и LinkedLists для третьего, в результате чего третий неэффективен во времени.

Вот самый простой метод в C ++ (я не публикую java-версию, поскольку она почти идентична):

void normalWindowing(int  mat[][MAX], int cols, int rows, int rad){
    int i, j;
    int h = 0;
    for (i = 0; i < rows; ++i)
    {
        for (j = 0; j < cols; j++) 
        {
            h = 0;
            for (int ry =- rad; ry <= rad; ry++) 
            {
                int y = i + ry;
                if (y >= 0 && y < rows) 
                {
                    for (int rx =- rad; rx <= rad; rx++) 
                    {
                        int x = j + rx;
                        if (x >= 0 && x < cols) 
                        {
                            h += mat[y][x];
                        }
                    }
                }
            }
        }
    }   
}

Вот второй метод (оптимизированный через столбцы) в C ++:

 void opt1Windowing(int  mat[][MAX], int cols, int rows, int rad){
    int i, j, h, y, col;
    queue<int>* q = NULL;
    for (i = 0; i < rows; ++i)
    {
        if (q != NULL)
            delete(q);
        q = new queue<int>();
        h = 0;
        for (int rx = 0; rx <= rad; rx++) 
        {
            if (rx < cols) 
            {
                int mem = 0;
                for (int ry =- rad; ry <= rad; ry++)
                {
                    y = i + ry;
                    if (y >= 0 && y < rows)
                    {
                        mem += mat[y][rx];
                    } 
                }
                q->push(mem);
                h += mem;
            }
        }
        for (j = 1; j < cols; j++) 
        {
            col = j + rad;
            if (j - rad > 0)
            {
                h -= q->front();
                q->pop();
            }
            if (j + rad < cols)
            {
                int mem = 0;
                for (int ry =- rad; ry <= rad; ry++)
                {
                    y = i + ry;
                    if (y >= 0 && y < rows)
                    {
                        mem += mat[y][col];
                    } 
                }
                q->push(mem);
                h += mem;
            }
        }
    }
}

А вот версия Java:

public static void opt1Windowing(int [][] mat, int rad){
    int i, j = 0, h, y, col;
    int cols = mat[0].length;
    int rows = mat.length;
    ArrayDeque<Integer> q = null;
    for (i = 0; i < rows; ++i)
    {
        q = new ArrayDeque<Integer>();
        h = 0;
        for (int rx = 0; rx <= rad; rx++)
        {
            if (rx < cols)
            {
                int mem = 0;
                for (int ry =- rad; ry <= rad; ry++)
                {
                    y = i + ry;
                    if (y >= 0 && y < rows)
                    {
                        mem += mat[y][rx];
                    }
                }
                q.addLast(mem);
                h += mem;
            }
        }
        j = 0;
        for (j = 1; j < cols; j++)
        {
            col = j + rad;
            if (j - rad > 0)
            {
                h -= q.peekFirst();
                q.pop();
            }
            if (j + rad < cols)
            {
                int mem = 0;
                for (int ry =- rad; ry <= rad; ry++)
                {
                    y = i + ry;
                    if (y >= 0 && y < rows)
                    {
                        mem += mat[y][col];
                    }
                }
                q.addLast(mem);
                h += mem;
            }
        }
    }
}

Я понимаю, что этот пост будет стеной текста. Вот третий метод в C ++:

void opt2Windowing(int  mat[][MAX], int cols, int rows, int rad){
    int i = 0;
    int j = 0;
    int h = 0;
    int hh = 0;
    deque< deque<int> *> * M = new deque< deque<int> *>();
    for (int ry = 0; ry <= rad; ry++)
    {
        if (ry < rows)
        {
            deque<int> * q = new deque<int>();
            M->push_back(q);
            for (int rx = 0; rx <= rad; rx++) 
            {
                if (rx < cols) 
                {
                    int val = mat[ry][rx];
                    q->push_back(val);
                    h += val;
                }
            }
        } 
    }
    deque<int> * C = new deque<int>(M->front()->size());
    deque<int> * Q = new deque<int>(M->front()->size());
    deque<int> * R = new deque<int>(M->size());

    deque< deque<int> *>::iterator mit;
    deque< deque<int> *>::iterator mstart = M->begin();
    deque< deque<int> *>::iterator mend = M->end();

    deque<int>::iterator rit;
    deque<int>::iterator rstart = R->begin();
    deque<int>::iterator rend = R->end();

    deque<int>::iterator cit;
    deque<int>::iterator cstart = C->begin();
    deque<int>::iterator cend = C->end();

    for (mit = mstart, rit = rstart; mit != mend, rit != rend; ++mit, ++rit)
    {
        deque<int>::iterator pit;
        deque<int>::iterator pstart = (* mit)->begin();
        deque<int>::iterator pend = (* mit)->end();
        for(cit = cstart, pit = pstart; cit != cend && pit != pend; ++cit, ++pit)
        {
            (* cit) += (* pit);
            (* rit) += (* pit);
        }
    }

    for (i = 0; i < rows; ++i)
    {        
        j = 0;
        if (i - rad > 0)
        {
            deque<int>::iterator cit;
            deque<int>::iterator cstart = C->begin();
            deque<int>::iterator cend = C->end();

            deque<int>::iterator pit;
            deque<int>::iterator pstart = (M->front())->begin();
            deque<int>::iterator pend = (M->front())->end();

            for(cit = cstart, pit = pstart; cit != cend; ++cit, ++pit)
            {
                (* cit) -= (* pit);
            }
            deque<int> * k = M->front();
            M->pop_front();
            delete k;
            h -= R->front();
            R->pop_front();
        }
        int row = i + rad;
        if (row < rows && i > 0)
        {
            deque<int> * newQ = new deque<int>();
            M->push_back(newQ);

            deque<int>::iterator cit;
            deque<int>::iterator cstart = C->begin();
            deque<int>::iterator cend = C->end();
            int rx;
            int tot = 0;
            for (rx = 0, cit = cstart; rx <= rad; rx++, ++cit) 
            {
                if (rx < cols) 
                {
                    int val = mat[row][rx];
                    newQ->push_back(val);  
                    (* cit) += val;
                    tot += val;
                }
            }
            R->push_back(tot);
            h += tot;
        }        
        hh = h;
        copy(C->begin(), C->end(), Q->begin());

        for (j = 1; j < cols; j++) 
        {
            int col = j + rad;
            if (j - rad > 0)
            {
                hh -= Q->front();
                Q->pop_front();
            }
            if (j + rad < cols)
            {
                int val = 0;
                for (int ry =- rad; ry <= rad; ry++)
                {
                    int y = i + ry;
                    if (y >= 0 && y < rows)
                    {
                        val += mat[y][col];
                    } 
                }
                hh += val;
                Q->push_back(val);   
            }
        }
    }
}

И, наконец, его Java-версия:

public static void opt2Windowing(int [][] mat, int rad){
    int cols = mat[0].length;
    int rows = mat.length;
    int i = 0;
    int j = 0;
    int h = 0;
    int hh = 0;
    LinkedList<LinkedList<Integer>> M = new LinkedList<LinkedList<Integer>>();
    for (int ry = 0; ry <= rad; ry++)
    {
        if (ry < rows)
        {
            LinkedList<Integer> q = new LinkedList<Integer>();
            M.addLast(q);
            for (int rx = 0; rx <= rad; rx++)
            {
                if (rx < cols)
                {
                    int val = mat[ry][rx];
                    q.addLast(val);
                    h += val;
                }
            }
        }
    }
    int firstSize = M.getFirst().size();
    int mSize = M.size();
    LinkedList<Integer> C = new LinkedList<Integer>();
    LinkedList<Integer> Q = null;
    LinkedList<Integer> R = new LinkedList<Integer>();
    for (int k = 0; k < firstSize; k++)
    {
        C.add(0);
    }
    for (int k = 0; k < mSize; k++)
    {
        R.add(0);
    }

    ListIterator<LinkedList<Integer>> mit;
    ListIterator<Integer> rit;
    ListIterator<Integer> cit;
    ListIterator<Integer> pit;
    for (mit = M.listIterator(), rit = R.listIterator(); mit.hasNext();)
    {
        Integer r = rit.next();
        int rsum = 0;
        for (cit = C.listIterator(), pit = (mit.next()).listIterator();
            cit.hasNext();)
        {
            Integer c = cit.next();
            Integer p = pit.next();
            rsum += p;
            cit.set(c + p);

        }
        rit.set(r + rsum);
    }

    for (i = 0; i < rows; ++i)
    {
        j = 0;
        if (i - rad > 0)
        {
            for(cit = C.listIterator(), pit = M.getFirst().listIterator();
               cit.hasNext();)
            {
                Integer c = cit.next();
                Integer p = pit.next();
                cit.set(c - p);
            }
            M.removeFirst();
            h -= R.getFirst();
            R.removeFirst();
        }
        int row = i + rad;
        if (row < rows && i > 0)
        {
            LinkedList<Integer> newQ = new LinkedList<Integer>();
            M.addLast(newQ);
            int rx;
            int tot = 0;
            for (rx = 0, cit = C.listIterator(); rx <= rad; rx++)
            {
                if (rx < cols)
                {
                    Integer c = cit.next();
                    int val = mat[row][rx];
                    newQ.addLast(val);
                    cit.set(c + val);
                    tot += val;
                }
            }
            R.addLast(tot);
            h += tot;
        }
        hh = h;
        Q = new LinkedList<Integer>();
        Q.addAll(C);

        for (j = 1; j < cols; j++)
        {
            int col = j + rad;
            if (j - rad > 0)
            {
                hh -= Q.getFirst();
                Q.pop();
            }
            if (j + rad < cols)
            {
                int val = 0;
                for (int ry =- rad; ry <= rad; ry++)
                {
                    int y = i + ry;
                    if (y >= 0 && y < rows)
                    {
                        val += mat[y][col];
                    }
                }
                hh += val;
                Q.addLast(val);
            }
        }
    }
}

Полагаю, что большинство из-за плохого выбора LinkedList в Java и отсутствия эффективного (не мелкого) метода копирования между двумя LinkedList.

Как я могу улучшить третий метод Java? Я делаю какую-то концептуальную ошибку? Как всегда, любая критика приветствуется.

ОБНОВЛЕНИЕ Даже если это не решит проблему, использование ArrayLists, как предлагается, вместо LinkedList улучшает третий метод. Второй работает еще лучше (но когда число строк и столбцов матрицы меньше 300 и радиус окна мал, первый неоптимизированный метод является самым быстрым в Java)

UPDATE2 Какой инструмент я могу использовать для профилирования своего кода и более глубокого понимания того, какая инструкция занимает больше всего времени? Я нахожусь на Mac OS X, и использование NetBeans Profiler просто показывает мне, что три метода заканчиваются с разным временем (кажется, я не могу охватить каждый метод)

UPDATE3 Я оцениваю время в java, используя System.nanoTime() Может ли это привести к неточным оценкам?:

    long start, end;

    start = System.nanoTime();
    simpleWindowing(mat, rad);
    end = System.nanoTime();
    System.out.println(end-start);

    start = System.nanoTime();
    opt1Windowing(mat, rad);
    end = System.nanoTime();
    System.out.println(end-start);

    start = System.nanoTime();
    opt2Windowing(mat, rad);
    end = System.nanoTime();
    System.out.println(end-start);

Answer 1

LinkedList - очень плохой выбор для списка, где вы делаете произвольный доступ. Для каждого get(int) просматривает список, пока не будет достигнут индекс запроса.
get(1) довольно быстро, но get(100) в 100 раз медленнее, а get(1000) в 1000 раз медленнее, чем get (1)

Вы должны изменить это, чтобы использовать вместо него ArrayList и инициализировать ArrayList с ожидаемым размером, чтобы избежать ненужного изменения размера внутреннего массива.

Редактировать
Хотя мои комментарии о get () и LinkedList верны, они не применимы в этом контексте. Я как-то упустил из виду, что нет случайного доступа к списку.

Answer 2

Используйте int[] вместо List.

Lists store. Объекты, требующие преобразования из int в Integer и обратно.

Answer 3

О синхронизации вашего кода: System.nanoTime () в порядке (я не думаю, что вы можете поправиться, поскольку он использует таймеры ОС, насколько я знаю), , но :

• не пытайтесь измерить слишком короткое задание, тогда точность не настолько хороша. Я думаю, что всего несколько миллисекунд доставят вам потенциальные проблемы. Рекомендации, кто-нибудь?

• измерьте несколько раз и возьмите медиану измерений. Внешние эффекты могут сильно замедлить выполнение, делая вашу оценку бесполезной. Взятие среднего значения не очень хорошо работает, потому что оно чувствительно к таким выбросам.

• у многих JVM есть JIT-компилятор, вы можете захотеть выполнить свой код несколько раз, прежде чем измерять, чтобы компилятор не включился где-то в середине вашего измерения, и половина ваших измерений вдруг в 10 раз быстрее остальные. Лучше измерить после того, как ваша ВМ "прогрелась".

Answer 4

Я действительно реализовал две оптимизированные версии для этой процедуры:

• первый, как предложил User216237, использует массив int в качестве очереди для кэширования суммированных значений столбцов, поскольку алгоритм сканирует изображение по столбцам
• другой реализует Таблицу суммированных областей для вычисления каждой прямоугольной области сумм путем доступа к этой таблице только четыре раза (она не зависит от радиуса окна).

Один метод может быть произвольно быстрее другого в зависимости от конкретной области, в которой он реализован. В моем случае таблицу суммированных площадей приходилось вычислять несколько раз, поэтому получилось медленнее, чем в первом методе, для значения радиуса менее 20 пикселей.