Codewars: N-dimensional Von Neumann Neighborhood in a matrix

Question

Task:

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 isCenter is just a token that helps to NOT INCLUDE the cell itself to the neighbourhood. There is also remaining_distance that 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.

Questions:

• What I am curious about. Is .append inefficient? I heard list comprehensions are better than append.
• Would not (0 <= dimensions_coordinate < len(arr)) changed to len(arr) <= dimensions_coordinate or dimensions_coordinate < 0) boost the code?
• Are there performance differences between == and is?
• Is 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"

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

Answer 1

As far as lo <= x < hi expressions go, my advice is to keep them as-is. The meaning is clear, and "optimizing" such an expression can at best bring only minimal gains.

(With the cPython interpreter, the only place I tend to deviate from such advice is turning an expression like x in [a, b, c] into x in (a, b, c), since the bytecode treats that triple as a constant rather than as a dynamically allocated data structure.)

---

tiny nit: PEP-8 asks that you spell it is_center. Whatever.

---

In the code

        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

please elide the final return, since we're just falling off the end of the function there.

---

LGTM. Ship it!