Hacker News Reader

Comment by no_protocol | Hacker News Reader

> it only performed 256 loop iterations, one for each point along the edge

alarm bells

There are only 252 points along the edge. This code will act on each corner twice. If you were performing an operation like `+= 1` on each edge element, this code would be wrong. When you copy and paste it later and change all the `= 0` to something else, you might end up with an unfortunate surprise.

Once I saw this mistake in the 2nd code example, I guessed it would also appear in the 3rd one. Sure enough, it does. This is just as unsavory to me as the original code.

I'm not sure if the author is here or not, but if you are, can you see the fix?

View on HN

The way I'd do it if I didn't want to use ifs is to loop n times, and for each row fill the first cell and the last one. So now I have the left and right side at O(n). Then i'd loop n-1 times starting at the second column and for each column fill the first and last cell again. O(n) all in all without repeating yourself, and no tests.

Another way to look at this problem altogether would be to change the data structure, so instead of using a classical 2d array the problem becomes trivial if you use a spiral array. Filling the edge in this case is just a matter of filling the first 4*(n-1) cells. Obviously this solution's acceptability depends entirely on what you're gonna do with your data afterwards.

Here's my fix:

  for (i = 0; i < GRID_SIZE - 1; ++i) { // Note the "-1"...
  
      // Top Edge
      grid[0][i] = 0;
  
      // Bottom Edge
      grid[GRID_SIZE - 1][GRID_SIZE - i - 1] = 0; // Reverse the order: from left to right
  
      // Left Edge
      grid[GRID_SIZE - i - 1][0] = 0; // Reverse the order: from bottom to top
  
      // Right Edge
      grid[i][GRID_SIZE - 1] = 0;
  }

This way, for every row/column, the loop acts on all but the last cell, which is actually the first cell of some other column/row.

I feel like for the each side you could actually handle two items per iteration, one forwards _and_ one backwards. That way your iteration count could be halved.

And what do you do with odd grid sizes?

Honestly the whole second half seemed damned weird. Give the requirement to zero the edges of a two dimensional array, it's so astonishingly obvious to just hard code the 0 and width-1/height-1 that do do anything else suggests a special effort to make a sub-optimal solution simply for arguments sake.

That doesn't reduce the number of cells touched, and would make the algorithm more complicated. It would also probably hurt cache locality. Going backwards is also pointless complication, you could just as easily cut into two sections and go forward in both.

And furthermore why split in two? Why not split the range into three sections, or four, or N and completely unroll the loop?

Probably not a good-tasting construct at all.

Yes. Another issue is that his grid is a square. It's hard to know whether this was sensible - author hasn't described the domain.

You could address both issues by having two for loops, one following the other. The first loop changes the top and bottom rows. The second loop changes the sides but not for the top and bottom cells. A comment could highlight that you're not updating the corners.

Here is which seems to be idiomatic in digital photo processing (e.g. darktable):

  for (int r = 0; r < GRID_SIZE; r++) {
    for (int c = 0; c < GRID_SIZE; c++) {
      if (i == 1 && j >= 1 && j < GRID_SIZE - 1)
	i = GRID_SIZE - 1;
      grid[i][j] = 0;
    }
  }

Of course, this one has a conditional, and many would frown on mucking with the loop counter outside of the for statement.

A source for this style may be dcraw, e.g. see from border_interpolate():

  for (row=0; row < height; row++)
    for (col=0; col < width; col++) {
      if (col==border && row >= border && row < height-border)
	col = width-border;
  // etc.

The dcraw code is so tightly written that I assume Dave Coffin has good reason for this choice, but I've never tested variants for performance.

Noticed the same thing, but only in the third, cleanest version. No better way to illustrate its merits relative to the initial two versions.

Spoiler alert: flipping that single bit from i=0 to i=1 might deserve a little comment of the "why" category.

Reply on news.ycombinator.com