8
\$\begingroup\$

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
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Why remove Moore's neighbourhood? \$\endgroup\$
    – hjpotter92
    Commented Jul 23, 2018 at 14:37
  • \$\begingroup\$ @hjpotter92 To make the code simpler. The probably somebody will answer. Because they just differ in "remaining_distance". Everything applied to this code can be applied to Moore too. \$\endgroup\$ Commented Jul 23, 2018 at 14:57
  • \$\begingroup\$ I think these questions would belong better on stack overflow and not here. This is about improving code style, not performance. @S.G you can answer most of your questions yourself by learning how to use the profiler. \$\endgroup\$
    – C. Harley
    Commented Jul 29, 2018 at 1:24
  • 3
    \$\begingroup\$ @C.Harley, performance is expressly in scope on code review, per codereview.stackexchange.com/help/on-topic \$\endgroup\$
    – Josiah
    Commented Jul 29, 2018 at 15:40
  • 1
    \$\begingroup\$ @S.G. Could you provide a few example test cases to go with this code? Please also ensure that it runs correctly as written. (e.g. // isn't python comment notation.) \$\endgroup\$
    – Josiah
    Commented Jul 29, 2018 at 15:51

1 Answer 1

2
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.