1-dimensional and 2-dimensional Peak Finding Algorithm

Question

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.

Gareth Rees · Accepted Answer · 2016-05-08 12:48:34Z

Just reviewing peak1d.

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))

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]

Stack Exchange Network

1-dimensional and 2-dimensional Peak Finding Algorithm

1 Answer 1

You must log in to answer this question.

Hot Network Questions

1-dimensional and 2-dimensional Peak Finding Algorithm

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions