У меня есть матрицу, которая представляет собой изображение, и мне нужно, чтобы цикл над каждого пикселя и для каждого из тех, что я должен вычислить сумму всех своих соседей, т.е. пиксели, относящиеся к окну радиуса rad с центром в пикселе.Java оптимизации кода на матрице оконного вычисляет в больше времени
я придумал три альтернативы:
- Самый простой способ, тот, который пересчитывает окно для каждого пикселя
- Чем больше оптимизирован таким образом, что использует очередь для хранения сумм оконных колонн и езда на велосипеде через столбцы матрицы обновляет эту очередь путем добавления нового элемента и удаления oldes
- еще более оптимизированными так, что не нужно пересчитывать очереди для каждой строки, но постепенно корректирует ранее сохраненного один
Я реализовал их в C++ с использованием очереди для второго способа и сочетанием двусторонних очередей для третьего (мне нужно перебирать их элементы без разрушения их) и набрал их раз, чтобы увидеть, есть ли фактическое улучшение. оказывается, что третий метод действительно быстрее.
Затем я попытался перенести код на 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? Я делаю некоторые концептуальные ошибки? Как всегда, любые критические замечания приветствуются.
UPDATE Даже если это не решает проблему, используя 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);
Кроме того, deque <> не слишком быстр на C++. Используйте vector <> (с .reserve(), чтобы уменьшить выделение памяти при построении.) – Macke
Да, вы, вероятно, правы, но мне больше не нужно оптимизировать код на C++, я просто написал его сначала, а затем портировал на Java который является языком, который я должен использовать – rano