Developing an algorithm question -- should be easy....

[AtlantaBob]

Hi guys,

A very general question here. I'm trying to write an algorithm using matrices in Python/Numpy where I'm manipulating the values of cells surrounding a given cell (sorta similar to the Game of Life). My question is, is it better to create a single algorithm to deal with the values of surrounding cells and catch index out of range exceptions, or should I code a specific algorithm for each corner, and for the various sides of the matrix?

I understand that catching exceptions is "expensive" as far as computer time goes, but do you think it would matter in this type of instance? We're talking about matrices ranging from 90 x 140 to maybe 300 x 300.

My guess is that you'll say I should just create the general algorithm, but I'd just like the confirmation.

Thanks from the programing newbie....

 

[PhatoseAlpha]

How important is performance versus maintainability?



At any rate, 300x300 is still about 1% border cells. Depending on how severe the exception handling cost is, you might still be better off generalizing the algorithm, but having it check a cell actually exists before trying to access it. It's a lot of comparisons, sure, but I'm not even close to certain that 360,000 simple evaluations is more costly then 1200 exceptions.

 

[Ken g6]

May I suggest a third alternative? If you have enough memory, you can try creating a buffer zone of cells around the sides of the matrix. This is similar to a sentinel value, except it doesn't stop any loops.

For example, in Conway's Game of Life, if you create a one-cell border around the entire matrix, and set all those cells to 0, it is equivalent to "not counting" the cells outside the matrix.

 

[AtlantaBob]

Ah, thanks, guys! Ken g6, I'm not sure why I didn't think of the border cell thing myself -- nice and elegant. Thankfully, memory still is cheap.

As it is, I went ahead and just wrote an algorithm that handles the inner body and then the outer rows and columns, and corner squares specifically. Oh well, live and learn. I may go ahead and try to re-implement it with border cells just for kicks.

Anyhow, thanks very much for the good advice!

 

[AtlantaBob]

Well, that was definitely easier once I added in the border cells! The code, for anyone who's interested.

Granted, there's still some debug-esque print statements in there, and I defined some variables borderMaxRow and borderMaxCol that weren't strictly necessary, but in general... I don't think it's horrible.

 

[IHateMyJob2004]

Why not use references/pointers to the neighboring cells and make them intelegent? Use model view controller pattern. When one cell gets updated, the neighboring cells get an event from teh model telling them so. In teh end you would have a recursive solution to whatever it is you are doing.

Works great for suduku sovlers!

 

[AtlantaBob]

IHMJ -

Sadly, that's beyond my ability -- I'm just programing this to hold some of my own data and determine how things are changing over data sets -- the data's not time sensitive, so I'm ok if it takes a second or two to run.

Just out of curiosity, aren't pointers a C sort-of-thing?

 

[IHateMyJob2004]

Pointers are C, yes. My bad, I didn't notice that you said Python.

 

[AtlantaBob]

No worries -- just wanted to make sure I wasn't crazy. Someday (I hope) I'll have time to learn such things, but I think that for the foreseeable future I'm going to be stuck with basic boring algorithms...

 

[IHateMyJob2004]

Don't worry. As a newbie to programming, the best thing you can do is learn proper design and understand when to use certain algorithms.

These days, I more or less need to know what a linked list is and how to use it. Not how to code it.

Optimization is secondary in the real world. You only optimize if things are sluggish on your target device. For example, we wrote code to display "data". Thousands of little things were on the screen at once. We were rendering at 1/4 frames per second (panning and zooming operations). This was an issue. The thing is, our code worked perfectly otherwise. We figured out why things were so slow and fixed it. I forget what kind of frame rates we are geting now but I think it is somewhere around 8 fps.