3
\$\begingroup\$

I have the following code for a peak finding algorithm in Python 3.4.3. A peak is an element that is not smaller than its neighbors.

def peak1d(array):
    '''This function recursively finds the peak in an array
       by dividing the array into 2 repeatedly and choosning
       sides.

       Complexity: O(log n)'''

    mid = len(array)//2

    if mid > 0 and array[mid] < array[mid-1]:
        return peak1d(array[:mid])

    elif mid < len(array)-1 and array[mid] < array[mid+1]:
        return peak1d(array[mid:])

    else:
        return array[mid]

def peak2d(array):
    '''This function finds the peak in a 2D array by the
       recursive method.

       Complexity: O(n log m)'''

    n = len(array)
    m = len(array[0])

    j = m//2

    row = [i[j] for i in array]

    i = row.index(max(row))

    print(i, j)

    if j > 0 and array[i][j] < array[i][j-1]:
        return peak2d([row[:j] for row in array])

    elif j < m - 1 and array[i][j] < array[i][j+1]:
        return peak2d([row[j:] for row in array])

    else:
        return array[i][j]

I think that I could utilize the first function in 2D peak finding but I don't know if it's upto the best practices. Also, can you suggest any methods to make my program faster and better.

Just another thought, I believe it doesn't matter if we transpose the array. The peak will remain the same. So should I transpose the array to reduce the complexity at times.

\$\endgroup\$
1
\$\begingroup\$

Just reviewing peak1d.

  1. It's not clear from the docstring what kind of object array is. If it might be a list, then the complexity is actually \$O(n)\$, because slicing a list makes a copy.

    The copy in array[:mid] or array[mid:] can be avoided by maintaining search bounds instead:

    def peak1d(array):
        """Return a peak in array."""
        def peak(start, stop):
            mid = (start + stop) // 2
            if mid > 0 and array[mid] < array[mid-1]:
                return peak(start, mid)
            elif mid < len(array) - 1 and array[mid] < array[mid+1]:
                return peak(mid, stop)
            else:
                return array[mid]
        return peak(0, len(array))
    
  2. Python doesn't do tail recursion elimination, so the function would be a bit faster if you eliminated the recursion:

    def peak1d(array):
        """Return a peak in array."""
        start, stop = 0, len(array)
        while True:
            mid = (start + stop) // 2
            if mid > 0 and array[mid] < array[mid-1]:
                stop = mid
            elif mid < len(array) - 1 and array[mid] < array[mid+1]:
                start = mid
            else:
                return array[mid]
    
\$\endgroup\$

Your Answer

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

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