Finding Local Maxima Over a Dynamic Range

Working in C#, I need to find all local peaks in a List of doubles and return them as another List doubles. This seems simple enough if I have a set number of values I'm comparing in any given 'window' of values, but I need to be able to actually pass this window size into the fun开发者_如何转开发ction itself. That may be confusing, but basically I need something like this:

public List<double> FindPeaks(List<double> values, double rangeOfPeaks)

where if 'rangeOfPeaks' was 5, the 'current' value would be compared to 2 values on each side of it to determine if it was a peak or not. If 'rangeOfPeaks' was 11, the current value would be compared to 5 values on each side. I'd think this was a pretty basic algorithm, however, I've been unsuccessful in finding any good methods for detecting a peak like this. Has anyone ever done this before? Any help at all would be appreciated. Thanks in advance!

---

I suggest a few changes to Levy's post...

1) Levy's code threw an exception when the specified values IList was a nearly straight line.

2) I think the index of the peaks in the array is the desired result. Consider for example what would happen if we had two peaks with identical doubles? Ops. Changed to return index of peaks in specified IList.

    public static IList<int> FindPeaks(IList<double> values, int rangeOfPeaks)
    {
        List<int> peaks = new List<int>();
        double current;
        IEnumerable<double> range;

        int checksOnEachSide = rangeOfPeaks / 2;
        for (int i = 0; i < values.Count; i++)
        {
            current = values[i];
            range = values;

            if (i > checksOnEachSide)
            {
                range = range.Skip(i - checksOnEachSide);
            }

            range = range.Take(rangeOfPeaks);
            if ((range.Count() > 0) && (current == range.Max()))
            {
                peaks.Add(i);
            }
        }

        return peaks;
    }

---

There are probably more efficient ways but LINQ makes this pretty straightforward

    static IList<double> FindPeaks(IList<double> values, int rangeOfPeaks)
    {
        List<double> peaks = new List<double>();

        int checksOnEachSide = rangeOfPeaks / 2;
        for (int i = 0; i < values.Count; i++)
        {
            double current = values[i];
            IEnumerable<double> range = values;
            if( i > checksOnEachSide )
                range = range.Skip(i - checksOnEachSide);
            range = range.Take(rangeOfPeaks);
            if (current == range.Max())
                peaks.Add(current);
        }
        return peaks;
    }

---

Old question that already has an accepted answer, but I wanted something better than O(n^2). This function is O(n*m) where m is the window size, and has the advantage of actually working, too. The method returns tuples of indices of local maxima and their associated value.

The calls to Enumerable.Repeat() ensure maxima at the very beginning and end of the set are found, as well.

The comparison with the after queue uses >= so that a local maximum will be found at the beginning of a plateau of values. A side effect is that the value at index 0 is returned if all values in the set are equal, which may or may not be desirable.

public static IEnumerable<Tuple<int, double>> LocalMaxima( IEnumerable<double> source, int windowSize )
{
    // Round up to nearest odd value
    windowSize = windowSize - windowSize % 2 + 1;
    int halfWindow = windowSize / 2;

    int index = 0;
    var before = new Queue<double>( Enumerable.Repeat( double.NegativeInfinity, halfWindow ) );
    var after = new Queue<double>( source.Take( halfWindow + 1 ) );

    foreach( double d in source.Skip( halfWindow + 1 ).Concat( Enumerable.Repeat( double.NegativeInfinity, halfWindow + 1 ) ) )
    {
        double curVal = after.Dequeue();
        if( before.All( x => curVal > x ) && after.All( x => curVal >= x ) )
        {
            yield return Tuple.Create( index, curVal );
        }

        before.Dequeue();
        before.Enqueue( curVal );
        after.Enqueue( d );
        index++;
    }
}

---

To allow for a window size of 1 without throwing an exception I flipped the before.Enqueue( curVal ); and before.Dequeue(); functions from Jeroen Cranendonk contribution:

public static IEnumerable<Tuple<int, double>> LocalMaxima( IEnumerable<double> source, int windowSize )
{
    // Round up to nearest odd value
    windowSize = windowSize - windowSize % 2 + 1;
    int halfWindow = windowSize / 2;

    int index = 0;
    var before = new Queue<double>( Enumerable.Repeat( double.NegativeInfinity, halfWindow ) );
    var after = new Queue<double>( source.Take( halfWindow + 1 ) );

    foreach( double d in source.Skip( halfWindow + 1 ).Concat( Enumerable.Repeat( double.NegativeInfinity, halfWindow + 1 ) ) )
    {
        double curVal = after.Dequeue();
        if( before.All( x => curVal > x ) && after.All( x => curVal >= x ) )
        {
            yield return Tuple.Create( index, curVal );
        }
        before.Enqueue( curVal );
        before.Dequeue();
        after.Enqueue( d );
        index++;
    }
}

---

Adding a threshold for peaks, also remove the peaks from the first and last positions if that's what you need. You can remove the (i!=xxx) conditions if you need all peaks.

private static IList<int> FindPeaks(IList<double> values, int rangeOfPeaks, double threshold)
    {
        List<int> peaks = new List<int>();
        double current;
        IEnumerable<double> range;

        int checksOnEachSide = rangeOfPeaks / 2;
        for (int i = 0; i < values.Count; i++)
        {
            current = values[i];
            range = values;

            if (i > checksOnEachSide)
            {
                range = range.Skip(i - checksOnEachSide);
            }

            range = range.Take(rangeOfPeaks);
            if ((range.Count() > 0) && (current == range.Max()) && (i != 0) && (i != values.Count - 1) && ((range.Max() - range.Min()) > threshold))
            {
                peaks.Add(i);
            }
        }

        return peaks;
    }

---

This function is O(n). It yields the results as it goes so it will also have very low memory overhead.

    public static IEnumerable<double> FindPeaks(IEnumerable<double> values, int rangeOfPeaks)
    {
        double peak = 0;
        int decay = 0;

        foreach (var value in values)
        {
            if (value > peak || decay > rangeOfPeaks / 2)
            {
                peak = value;
                decay = 0;
            }
            else
            {
                decay++;
            }

            if (decay == rangeOfPeaks / 2)
                yield return peak;
        }
    }

---

Using the Interactive Extensions package from the Rx team, you can solve this problem quite neatly. The package has a lot of functions to do with different buffering/windowing scenarios.

IEnumerable<double> FindPeaks(IEnumerable<double> numbers, int windowSize)
{
    // Pad numbers to the left of <numbers> so that the first window of <windowSize> is centred on the first item in <numbers>
    // Eg if numbers = { 1, 2, 3, 4 }, windowSize = 3, the first window should be { MinValue, 1, 2 }, not { 1, 2, 3 }
    var paddedNumbers = Enumerable.Repeat(double.MinValue, windowSize / 2)
                                  .Concat(numbers);

    // Take buffers of size <windowSize>, stepping forward by one element each time
    var peaks = paddedNumbers.Buffer(windowSize, 1)
                             .Select(range => range.Max())
                             .DistinctUntilChanged();

    return peaks;
}

---

Here is my version. It uses a Queue to hold the last windowSize elements, while enumerating the source. Unfortunately I had to use the inefficient ElementAt Linq method to find the tested element in the Queue, because the Queue implementation does not expose its GetElement method (it is internal). For small window sizes this should not be a problem.

public static IEnumerable<(int, TSource)> LocalMaxima<TSource>(
    this IEnumerable<TSource> source, int windowSize)
{
    var comparer = Comparer<TSource>.Default;
    var queue = new Queue<TSource>();
    var testedQueueIndex = (windowSize - 1) / 2;
    var index = testedQueueIndex;
    foreach (var item in source)
    {
        queue.Enqueue(item);
        if (queue.Count >= windowSize)
        {
            var testedItem = queue.ElementAt(testedQueueIndex);
            var queueIndex = 0;
            foreach (var queuedItem in queue)
            {
                if (queueIndex != testedQueueIndex
                    && comparer.Compare(queuedItem, testedItem) > 0) goto next;
                queueIndex++;
            }
            yield return (index, testedItem);
        next:
            queue.Dequeue();
            index++;
        }
    }
}

Usage example:

var source = "abbacdbbcac".ToCharArray();
var indexes = Enumerable.Range(0, source.Length);
var result = source.LocalMaxima(5);
Console.WriteLine($"Source:  {String.Join(", ", source)}");
Console.WriteLine($"Indexes: {String.Join("  ", indexes)}");
Console.WriteLine($"Result:  {String.Join(", ", result)}");

Output:

Source:  a, b, b, a, c, d, b, b, c, a, c
Indexes: 0  1  2  3  4  5  6  7  8  9  10
Result:  (5, d), (8, c)