Peak Finding in C# and Python

Wouldn`t it be nice

Do you have a list of data, from which peak values need to be extracted? Whether it`s finding mountain peaks, peak performance days/points in your daily performance(workouts, running, amount of stuff done), building an app to do that, or just playing with algorithms, this article may be of use to you.

What is a Peak

Peak is the point/value that is higher than its surroundings. Therefore we can assume that in [1, 6, 1], the 6 is the peak.

Our definition is going to be exactly this, however we are not looking for the one ultimate peak, but all the peaks we can find. Anything that is higher than its neighbors will be a peak for us.

That way we will often find multiple values, as long as they are peaks. In [4,9,2,7,6,3], 9 and 7 are the peaks.

The Code

To find the peaks in larger arrays, we`re going to need a heavier caliber than our mind and eyes. There are limits to how much and how fast we can screen an array. We surely cannot process an array consisting of 10 000 numbers in any reasonable time.

For that, we have machines and code. I coded up one simple C# app and one Python app that I would like to share. In C# we will have something like this:

                    using System;
                    using System.Collections.Generic;
                    using System.Diagnostics;
                    
                    namespace AlgosC
                    {
                        class LinearPeaks
                        {
                            static void Main(string[] args)
                            {
                                List<int> numbersList = new List<int>();
                                Console.Write("Length: ");
                                int length = Int32.Parse(Console.ReadLine());
                    
                                Random rnd = new Random();
                                for (int i = 0; i < length; i++)
                                {
                                    numbersList.Add(rnd.Next(10));
                                }
                               Console.WriteLine("The list contains " + numbersList.Count + " numbers.");
                    
                                
                               //STOPWATCH
                                Stopwatch sw = new Stopwatch();
                    
                                //MOST IMPORTANT PART, HERE IS WHERE THE MAGIC HAPPENS
                                List<int> findPeaks(List<int> numbers)
                                {
                                    sw.Start();
                                    List<int> peaks = new List<int>();
                                    for (int i = 0; i < numbers.Count; i++)
                                    {
                                        if (i == 0)
                                        {
                                            if (numbers[i] >= numbers[i + 1])
                                            {
                                                peaks.Add(numbers[i]);
                                            }
                                        }
                    
                                        if (i > 0 && i < (numbersList.Count - 1))
                                        {
                                            if (numbers[i] >= numbers[i + 1] && numbers[i] >= numbers[i - 1])
                                            {
                                                peaks.Add(numbers[i]);
                                            }
                                        }
                    
                                        if (i >= (numbersList.Count - 1))
                                        {
                                            if (numbers[i] >= numbers[i - 1])
                                            {
                                                peaks.Add(numbers[i]);
                                            }
                                        }
                                    }
                                    sw.Stop();
                                    return peaks;
                                }
                                //WRITE OUT THE OUTPUT
                                Console.WriteLine("\n There are " + findPeaks(numbersList).Count + " peaks.");
                                Console.WriteLine("\n It took " + sw.Elapsed + " to find the peaks in " + numbersList.Count + " numbers.");
                                Console.ReadKey();
                                
                            }
                        }
                    }
                

To demonstrate how fast we can find all peaks in an array/or list, I made this app as a console app, asking you to input the length of an array/list we want to check. Once you input the X amount in length, and press enter, a list of X random numbers 1-10 will be generated and searched for peaks. After the process is done, you`ll also see how long it took in seconds. Of course you can adjust the code to your needs and play around with it however you see fit.

Same app in Python:

                    import random
                    import sys
                    import time
                    
                    numbers_list = []
                    length = int(input("Enter the number: "))
                    
                    for x in range(0, length):
                    	numbers_list.append(random.randrange(1, 10))
                    
                    print("The list contains ", len(numbers_list), " numbers.")
                    
                    def find_peaks(numbers):
                    	start_time = time.time() #start stopwatch
                    	peaks = [];
                    	for x in range(0, len(numbers)):
                    		if x == 0:
                    			if numbers[x] >= numbers[x + 1]:
                    				peaks.append(numbers[x])
                    		elif ((x > 0) and (x < (len(numbers_list) - 1))):
                    			if ((numbers[x] >= numbers[x - 1]) and (numbers[x] >= numbers[x + 1])):
                    				peaks.append(numbers[x])
                    		elif x >= len(numbers_list):
                    			if numbers[x] >= numbers[x - 1]:
                    				peaks.append(numbers[x])
                    	elapsed_time = time.time() - start_time
                    	return peaks, elapsed_time
                    
                    peaks, elapsed_time = find_peaks(numbers_list)
                    print("There are ", len(peaks), " peaks.")
                    print("It took ", elapsed_time, " s to find peaks for ", len(numbers_list), " numbers.")
                

Python is doing the exact same thing, but it takes less code and more time, as expected.

If speed is your issue, choose C#, or even better C++/C. If you want to get an app up and running fast, choose Python. And of course, if you`re a Trainspotting fan, choose life!

02/10/2017