6
\$\begingroup\$

Let's say you want to increment the cells around the position (x,y) in a square matrix m of size T.

I've written the same code in a few languages. Here's the JS syntax version :

if (x>0) {
    if (y>0) m[x-1][y-1]++;
    m[x-1][y]++;
    if (y<T-1) m[x-1][y+1]++;
}
if (y>0) m[x][y-1]++;
if (y<T-1) m[x][y+1]++;
if (x<T-1) {
    if (y>0) m[x+1][y-1]++;
    m[x+1][y]++;
    if (y<T-1) m[x+1][y+1]++;
}

I don't like this kind of code, those tests look redundant. What bothers me is less the clarity of the code than the fact it has to do so many times the same checks.

But I don't see anything better. Am I just missing an obvious solution or is there nothing better with the branching toolset we have ? A slower code isn't acceptable as an answer, performance is the essence of the question.

\$\endgroup\$
6
\$\begingroup\$

Like Simon I would store the directions into a data structure, though I would probably hard code it

//Array Index Constants
var X = 0 , Y = 1; 
//All 8 neighbours ( vectors )
var vectors = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];

The fun thing about JavaScript is that there is no ArrayIndexOutOfBoundsException in JavaScript, requesting a value out of bounds returns undefined.

So, now, you can go for

for( int i = 0 ; i < vectors.length ; i++ ){
  var vector = vectors[i];
  if( m[x+vector[X]] && m[x+vector[X]][y+vector[Y]] !== undefined )
    m[x+vector[X]][y+vector[Y]]++;  
}

I did use for m[x+vector[X]] a falsey comparison, if the row X was defined it would pass the falsey evaluation ( it would be an Array ). For m[x+vector[X]][y+vector[Y]] I compared to undefined, since 0 is a realistic, acceptable value which would evaluate as false.

If I had to do a lot of matrix magic, then I would have a dedicated function to check whether a point is part of the matrix. And a dedicated function to add a vector to a point.

|improve this answer|||||
\$\endgroup\$
  • 2
    \$\begingroup\$ I'm apparently way too used to Java, I didn't even think about undefined! \$\endgroup\$ – Simon Forsberg Apr 29 '14 at 11:55
3
\$\begingroup\$

Create an array of the offsets you want to change in your code.

var offsets = new Array();
for (var x = -1; x <= 1; x++) {
    for (var y = -1; y <= 1; y++) {
        if ((x != 0) || (y != 0)) {
            offsets.push({ x: x, y: y });
        }
    }
}

(There are probably better ways to do this, you could hard-code the values into the array for example, but I was lazy. It is very possible that this code needs to be reviewed itself)

Now, loop through your offsets and check if your x + offset.x is within the 0 to T - 1 range, and the same for y.

Once you have the offsets array setup, you can loop through it like this and perform your ++ operation for the matrix:

for (var index in offsets) {
    var offset = offsets[index];
    var newX = x + offset.x;
    var newY = y + offset.y;

    if ((newX >= 0) && (newX < T) && (newY >= 0) && (newY < T))
        m[newX][newY]++;
}
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ This is a little cleaner but it adds a loop, some operations and it does much more checks in the end. \$\endgroup\$ – Denys Séguret Apr 26 '14 at 16:03
  • \$\begingroup\$ @dystroy The loop is just a replacement for your code duplication, it won't have much of an impact on performance. The overall runtime complexity remains the same (constant time, O(8) --> O(1)) \$\endgroup\$ – Simon Forsberg Apr 26 '14 at 16:10
  • \$\begingroup\$ You do 5 tests for each of the 8 neighbors (counting the loop one), while I was doing only one. \$\endgroup\$ – Denys Séguret Apr 26 '14 at 16:53
  • 1
    \$\begingroup\$ @dystroy That is a price I am willing to pay for cleaner code. \$\endgroup\$ – Simon Forsberg Apr 26 '14 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.