1D peak algorithm (correct implementation)

  • Thread starter Arman777
  • Start date
1,550
122
Python:
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 couldnt come up with something clever :(

Thanks
 
Last edited:
10,811
4,349
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.
 
1,550
122
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

Insights Author
Gold Member
2018 Award
1,103
960
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.
 
10,811
4,349
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
 
1,550
122
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 shouldnt 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 thats 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 ?
 
1,550
122
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)
 
Last edited:
10,811
4,349
line 5 empty error --> empty array

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

Python:
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.
 
1,550
122
line 5 empty error --> empty array

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

Python:
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 thats a max value of an array, max can be also peak value but not necessarily.
 

Attachments

10,811
4,349
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.
 
1,550
122
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 definitly 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.
 

Want to reply to this thread?

"1D peak algorithm (correct implementation)" You must log in or register to reply here.

Related Threads for: 1D peak algorithm (correct implementation)

Replies
0
Views
2K
Replies
0
Views
2K
Replies
5
Views
2K
  • Posted
Replies
21
Views
4K
  • Posted
Replies
1
Views
329
Replies
4
Views
5K
Replies
2
Views
2K
  • Posted
Replies
4
Views
3K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top