1D peak algorithm (correct implementation)

[Arman777]

array_values = [[0], [0,0], [1,2], [3,1,2], [1,2,3], [4,6,2,1], [8,9,0,2,1]]

def peakfinder(xarray):
    if len(xarray) == 0:
        print("You entered an empty error !")
        raise ValueError
    if len(xarray) == 1:
        return xarray[0]
    if len(xarray) == 2:
        return max(xarray)
    mid_element_index = len(xarray) // 2
    mid_element = xarray[mid_element_index]
    if mid_element >= xarray[mid_element_index + 1] and mid_element >= xarray[mid_element_index - 1] :
        return mid_element
    elif mid_element < xarray[mid_element_index + 1]:
        return xarray[mid_element_index + 1:]
    else:
        return xarray[ :mid_element_index]

for xarray in array_values:
    while type(xarray) != int:   
        xarray = peakfinder(xarray)
    print("The peak value is", xarray)

Is this a "good" 1D peak finder code ? Also I have another problem. In the peak finder case do we have to find all the peak values or just one peak value ?

Also in my code I didnt like `while type(array) != int:`, but I couldn't come up with something clever :(

Thanks

 

[jedishrfu]

I don't know any clever way but did notice the variable name 'array'. The best practices guide will tell you programmers shy away from valid english words when selecting variable names.

The reasoning is that it can introduce some pretty strange behavior in your code if it happens to be a keyword in the language.

There was a recent cautionary story of a guy who got the license plate ‘null’ for his car thinking that plate readers won't be able to track him instead he now got all the ticket infractions for all unreadable plates ie they were assigned the value of null too and so by association he now owned those tickets.

xarray or array1 would be better choices.

 

[Arman777]

I don't know any clever way but did notice the variable name 'array'. The best practices guide will tell you programmers shy away from valid english words when selecting variable names.

The reasoning is that it can introduce some pretty strange behavior in your code if it happens to be a keyword in the language.

There was a recent cautionary story of a guy who got the license plate ‘null’ for his car thinking that plate readers won't be able to track him instead he now got all the ticket infractions for all unreadable plates ie they were assigned the value of null too and so by association he now owned those tickets.

xarray or array1 would be better choices.

Thanks I ll be more careful

 

[Wrichik Basu]

I don't know any clever way but did notice the variable name 'array'. The best practices guide will tell you programmers shy away from valid english words when selecting variable names.

The reasoning is that it can introduce some pretty strange behavior in your code if it happens to be a keyword in the language.

There was a recent cautionary story of a guy who got the license plate ‘null’ for his car thinking that plate readers won't be able to track him instead he now got all the ticket infractions for all unreadable plates ie they were assigned the value of null too and so by association he now owned those tickets.

xarray or array1 would be better choices.

This became a major problem when I started with Python. In java, for example, I used str for string, which is a keyword in Python. I have several other standard variable names, which turned out to be functions in Python.

 

[jedishrfu]

My experience was a weird one. Early mainframe Basic interpreters had a function called tst() which I think tested the string values for numeric data (can't remember and can't find via google).

I coded a loop:

for i = 1 to z step 10

and later changed the variable 'z' to something more descriptive 't' so that it read

for i = 1 to t step 10

However, to my great surprise, I got an error saying: "Invalid use of the tst() function expecting '('. "

Apparently, the interpreter removed the spaces during parsing and saw this line instead

fori=1totstep10 and parsed it as for,i,=,1,to,tst ...stop...error...expecting a parenthesis

 

[Arman777]

This became a major problem when I started with Python. In java, for example, I used str for string, which is a keyword in Python. I have several other standard variable names, which turned out to be functions in Python.

str is a big problem. I think array is generally not a problem, however as @jedishrfu said I shouldn't use it. I was using "sum" in the loops but it was a keyword so that was a problem for me..

My experience was a weird one. Early mainframe Basic interpreters had a function called tst() which I think tested the string values for numeric data (can't remember and can't find via google).

I coded a loop:

for i = 1 to z step 10

and later changed the variable 'z' to something more descriptive 't' so that it read

for i = 1 to t step 10

However, to my great surprise, I got an error saying: "Invalid use of the tst() function expecting '('. "

Apparently, the interpreter removed the spaces during parsing and saw this line instead

fori=1totstep10 and parsed it as for,i,=,1,to,tst ...stop...error...expecting a parenthesis

I guess that's C right ? Its intersting ...

Also I have another problem. In the peak finder case do we have to find all the peak values or just one peak value ?

So what about this ? any ideas ?

 

[Arman777]

[CODE lang="python" title="Real recursive version"]array_values = [[0], [0,0], [1,2], [3,1,2], [1,2,3], [4,6,2,1], [8,9,0,2,1]]

def peakfinder(xarray):
if len(xarray) == 0:
print("Error! You entered an empty array ")
raise ValueError
if len(xarray) == 1:
return xarray[0]
if len(xarray) == 2:
return max(xarray)
mid_element_index = len(xarray) // 2
mid_element = xarray[mid_element_index]
if mid_element >= xarray[mid_element_index + 1] and mid_element >= xarray[mid_element_index - 1] :
return mid_element
elif mid_element < xarray[mid_element_index + 1]:
return peakfinder(xarray[mid_element_index + 1:])
else:
return peakfinder(xarray[ :mid_element_index])

for xarray in array_values:
xarray = peakfinder(xarray)
print("The peak value is", xarray)[/CODE]

 

[jedishrfu]

line 5 empty error --> empty array

If you're looking for the peak value and where its located:

def findnmax(xarray):
    maxvalue=0
    maxindex=0
    for i in range(len(xarray)):
       if xarray[i]>maxvalue:
          maxvalue=xarray[i]
          maxindex=i

    return (maxindex,maxvalue)

then this code might work.

 

[Arman777]

line 5 empty error --> empty array

If you're looking for the peak value and where its located:

def findnmax(xarray):
    maxvalue=0
    maxindex=0
    for i in range(len(xarray)):
       if xarray[i]>maxvalue:
          maxvalue=xarray[i]
          maxindex=i

    return (maxindex,maxvalue)

then this code might work.

I think that's a max value of an array, max can be also peak value but not necessarily.

 

[Arman777]

line 5 empty error --> empty array

Thanks !

 

[jedishrfu]

Okay I got it. Perhaps you can amend the loop in my code to find the case where the value is greater than the maxvalue and the values surrounding it are less and then adding the index of that value to a new array.

My code finds the highest value and thus by the definitions of the project its > the surrounding values.

But what you really want is a list of all values on the hills of the curve.

 

[jedishrfu]

Great exercise though.

 

[Arman777]

But what you really want is a list of all values on the hills of the curve.

I guess in peak find algorithm, finding all the peaks are optional. I mean the algorithm that I use has a O(logN) runtime and definately finds a peak value. We can check each number to find peak points but that would have O(n) time complexity.

The important point is minimize the time complexity. However "if we wanted to find more than one peak or all the peaks" then is it better to use faster version of the algorithm and do some tricks on the array to keep searching or using brute force.

 

[Arman777]

Great exercise though.

Indeed