I have a matrix which represents an image and I need to cycle over each pixel and for each one of those I have to compute the sum of all its neighbors, ie the pixels that belong to a window of radius rad centered on the pixel.
I came up with three alternatives:
The simplest way, the one that recomputes the window for each pixel
The more optimized way that uses a queue to store the sums of the window columns and cycling through the columns of the matrix updates this queue by adding a new element and removing the oldes
The even more optimized way that does not need to recompute the queue for each row but incrementally adjusts a previously saved one
I implemented them in c++ using a queue for the second method and a combination of deques for the third (I need to iterate through their elements without destructing them) and scored their times to see if there was an actual improvement. it appears that the third method is indeed faster.
Then I tried to port the code to Java (and I must admit that I'm not very comfortable with it). I used ArrayDeque for the second method and LinkedLists for the third resulting in the third being inefficient in time.
Here is the simplest method in C++ (I'm not posting the java version since it is almost identical):
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];
}
}
}
}
}
}
}
Here is the second method (the one optimized through columns) in 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;
}
}
}
}
And here is the Java version:
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;
}
}
}
}
I recognize this post will be a wall of text. Here is the third method in 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);
}
}
}
}
And finally its Java version:
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);
}
}
}
}
I guess that most is due to the poor choice of the LinkedList in Java and to the lack of an efficient (not shallow) copy method between two LinkedList.
How can I improve the third Java method? Am I doing some conceptual error? As always, any criticisms is welcome.
UPDATE Even if it does not solve the issue, using ArrayLists, as being suggested, instead of LinkedList improves the third method. The second one performs still better (but when the number of rows and columns of the matrix is lower than 300 and the window radius is small the first unoptimized method is the fastest in Java)
