5
\$\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"

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Why remove Moore's neighbourhood? \$\endgroup\$ – hjpotter92 Jul 23 '18 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\$ – Predicate Jul 23 '18 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 Jul 29 '18 at 1:24
  • 2
    \$\begingroup\$ @C.Harley, performance is expressly in scope on code review, per codereview.stackexchange.com/help/on-topic \$\endgroup\$ – Josiah Jul 29 '18 at 15:40
  • \$\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 Jul 29 '18 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.