arrays - Python - comparing elements of list with 'neighbour' elements -

this may more of 'approach' or conceptual question.

basically, have python multi-dimensional list so:

my_list = [[0,1,1,1,0,1], [1,1,1,0,0,1], [1,1,0,0,0,1], [1,1,1,1,1,1]] 

what have iterate through array , compare each element directly surrounding though list layed out matrix.

for instance, given first element of first row, my_list[0][0], need know know value of my_list[0][1], my_list[1][0] , my_list[1][1]. value of 'surrounding' elements determine how current element should operated on. of course element in heart of array, 8 comparisons necessary.

now know iterate through array , compare indexed values, above. curious whether there more efficient way limited amount of iteration required? should iterate through array is, or iterate , compare values either side , transpose array , run again. this, ignore values diagonal. , should store results of element lookups, don't keep determining value of same element multiple times?

i suspect may have fundamental approach in computer science, , eager feedback on best approach using python opposed looking specific answer problem.

any appreciated.

you may faster, , possibly simpler, code using numpy, or other alternatives (see below details). theoretical point of view, in terms of algorithmic complexity, best can o(n*m), , can design (if understand correctly). example:

def neighbors(matrix, row, col):     in row-1, row, row+1:         if < 0 or == len(matrix): continue         j in col-1, col, col+1:             if j < 0 or j == len(matrix[i]): continue             if == row , j == col: continue             yield matrix[i][j]  matrix = [[0,1,1,1,0,1], [1,1,1,0,0,1], [1,1,0,0,0,1], [1,1,1,1,1,1]]  i, row in enumerate(matrix):     j, cell in enumerate(cell):         neighbor in neighbors(matrix, i, j):             do_stuff(cell, neighbor) 

this has takes n * m * 8 steps (actually, bit less that, because many cells have fewer 8 neighbors). , algorithmically, there's no way can better o(n * m). so, you're done.

---

(in cases, can make things simpler—with no significant change either way in performance—by thinking in terms of iterator transformations. example, can create grouper on adjacent triplets list a zipping a, a[1:], , a[2:], , can extend adjacent 2-dimensional nonets. think in case, make code more complicated writing explicit neighbors iterator , explicit for loops on matrix.)

---

however, practically, can whole lot faster, in various ways. example:

• using numpy, may order of magnitude or faster. when you're iterating tight loop , doing simple arithmetic, that's 1 of things python particularly slow at, , numpy can in c (or fortran) instead.
• using favorite gpgpu library, can explicitly vectorize operations.
• using multiprocessing, can break matrix pieces , perform multiple pieces in parallel on separate cores (or separate machines).

of course single 4x6 matrix, none of these worth doing… except possibly numpy, may make code simpler faster, long can express operations naturally in matrix/broadcast terms.

in fact, if can't express things way, using numpy store matrix may make things little simpler (and save memory, if matters). example, numpy can let access single column matrix naturally, while in pure python, need write [row[col] row in matrix].

---

so, how tackle numpy?

first, should read on numpy.matrix , ufunc (or, better, higher-level tutorial, don't have 1 recommend) before going further.

anyway, depends on you're doing each set of neighbors, there 3 basic ideas.

first, if can convert operation simple matrix math, that's easiest.

if not, can create 8 "neighbor matrices" shifting matrix in each direction, perform simple operations against each neighbor. cases, may easier start n+2 x n+2 matrix suitable "empty" values (usually 0 or nan) in outer rim. alternatively, can shift matrix on , fill in empty values. or, operations, don't need identical-sized matrix, can crop matrix create neighbor. depends on operations want do.

for example, taking input fixed 6x4 board game of life:

def neighbors(matrix):     in -1, 0, 1:         j in -1, 0, 1:             if == 0 , j == 0: continue             yield np.roll(np.roll(matrix, i, 0), j, 1)  matrix = np.matrix([[0,0,0,0,0,0,0,0],                     [0,0,1,1,1,0,1,0],                     [0,1,1,1,0,0,1,0],                     [0,1,1,0,0,0,1,0],                     [0,1,1,1,1,1,1,0],                     [0,0,0,0,0,0,0,0]]) while true:     livecount = sum(neighbors(matrix))     matrix = (matrix & (livecount==2)) | (livecount==3) 

(note isn't best way solve problem, think it's relatively easy understand, , illuminate whatever actual problem is.)