For creating this challenge on Codewars I need a very performant function that calculates Von Neumann Neighborhood in a N-dimensional array. This function will be called about 2000 times
The basic recursive approach:
- calculate the index span influenced by the distance
- if the index is in the range of the matrix go one step deeper into the next dimension
- if max dimension is reached - append the value to the global neigh list
isCenteris just a token that helps to NOT INCLUDE the cell itself to the neighbourhood. There is also
remaining_distancethat reduce the span.
You probably do not need to understand the process of this deep math so good. But maybe someone python experienced can point me to some basic performance upgrade potential the code has.
- What I am curious about. Is
.appendinefficient? I heard list comprehensions are better than append.
not (0 <= dimensions_coordinate < len(arr))changed to
len(arr) <= dimensions_coordinate or dimensions_coordinate < 0)boost the code?
- Are there performance differences between
dimensions = len(coordinates)... if curr_dim == dimensions:...slower than
if curr_dim == len(coordinates)?
- if you understood the math do you see a way to do it iterative? Because I heard recursions are slower in python and theoretical informatics says "Everything recursive can be iterative"
I would be very thankful if you can answer me at least some of the questions or point to lacks that I don't see.
The whole code:
- matrix is a N-dimensional matrix.
- coordinates of the cell is a N-length tuple.
- distance is the reach of the neighbourhood
def get_neighbourhood(matrix, coordinates, distance=1): dimensions = len(coordinates) neigh =  app = neigh.append def recc_von_neumann(arr, curr_dim=0, remaining_distance=distance, isCenter=True): #the breaking statement of the recursion if curr_dim == dimensions: if not isCenter: app(arr) return dimensions_coordinate = coordinates[curr_dim] if not (0 <= dimensions_coordinate < len(arr)): return dimesion_span = range(dimensions_coordinate - remaining_distance, dimensions_coordinate + remaining_distance + 1) for c in dimesion_span: if 0 <= c < len(arr): recc_von_neumann(arr[c], curr_dim + 1, remaining_distance - abs(dimensions_coordinate - c), isCenter and dimensions_coordinate == c) return recc_von_neumann(matrix) return neigh