1D peak algorithm (correct implementation)

In summary: 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 10and later changed the variable 'z' to something more descriptive 't' so that it readfor i = 1 to t step 10However, 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 insteadfori=1totstep10 and parsed it as for,i,=
  • #1
Arman777
Insights Author
Gold Member
2,168
192
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 couldn't come up with something clever :(

Thanks
 
Last edited:
Technology news on Phys.org
  • #2
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.
 
  • Like
Likes StoneTemplePython, Wrichik Basu and Arman777
  • #3
jedishrfu said:
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
 
  • #4
jedishrfu said:
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.
 
  • #5
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
 
  • Like
Likes Wrichik Basu and Arman777
  • #6
Wrichik Basu said:
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..

jedishrfu said:
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 ...
Arman777 said:
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 ?
 
  • #7
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:
  • #8
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.
 
  • #9
jedishrfu said:
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 that's a max value of an array, max can be also peak value but not necessarily.
 

Attachments

  • rec02.pdf
    154.6 KB · Views: 212
  • #10
jedishrfu said:
line 5 empty error --> empty array
Thanks !
 
  • #11
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.
 
  • #13
jedishrfu said:
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.
 
  • #14
jedishrfu said:
Great exercise though.
Indeed
 

1. What is the purpose of a 1D peak algorithm?

The purpose of a 1D peak algorithm is to find the highest point or peak in a one-dimensional array of numbers. This can be useful in many applications, such as signal processing, data analysis, and optimization problems.

2. How does a 1D peak algorithm work?

A 1D peak algorithm typically involves iterating through the array and comparing each element to its neighboring elements. If the element is larger than both its neighbors, it is considered a peak. If not, the algorithm will move onto the next element until a peak is found.

3. What are the key components of a correct implementation of a 1D peak algorithm?

The key components of a correct implementation of a 1D peak algorithm include correctly identifying the boundaries of the array, handling edge cases, and ensuring that the algorithm runs in linear time. Additionally, the algorithm should be able to handle arrays with multiple peaks and return all of them if necessary.

4. How can I optimize the performance of my 1D peak algorithm?

One way to optimize the performance of a 1D peak algorithm is to use a divide-and-conquer approach, where the array is divided into smaller subarrays and the algorithm is applied to each of them. This can improve the efficiency of the algorithm, especially for larger arrays.

5. Are there any limitations to the 1D peak algorithm?

One limitation of the 1D peak algorithm is that it only works for arrays of numbers. It cannot be applied to arrays of strings or other data types. Additionally, the algorithm may not be suitable for finding the global maximum in a function or for multidimensional arrays where the peaks may be located in different dimensions.

Similar threads

  • Programming and Computer Science
Replies
18
Views
997
  • Programming and Computer Science
Replies
4
Views
826
  • Programming and Computer Science
Replies
10
Views
696
  • Programming and Computer Science
2
Replies
55
Views
4K
  • Programming and Computer Science
Replies
8
Views
758
Replies
9
Views
941
  • Programming and Computer Science
Replies
29
Views
1K
  • Programming and Computer Science
Replies
4
Views
941
  • Programming and Computer Science
Replies
2
Views
868
  • Programming and Computer Science
Replies
2
Views
855
Back
Top