Поиск локальных максимумов в динамическом диапазоне

Ответ 1

Есть, вероятно, более эффективные способы, но LINQ делает это довольно простым

    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;
    }

Ответ 2

Я предлагаю несколько изменений в сообщении Леви...

1) Код Levy выдал исключение, когда указанные значения IList были почти прямой.

2) Я считаю, что индекс пиков в массиве является желаемым результатом. Рассмотрим, например, что произойдет, если бы у нас было два пика с одинаковыми удвоениями? Ops. Изменено для возврата индекса пиков в указанный 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;
    }

Ответ 3

Старый вопрос, который уже имеет принятый ответ, но мне нужно что-то лучше, чем O (n ^ 2). Эта функция O (n * m), где m - размер окна, и имеет то преимущество, что она действительно работает. Метод возвращает кортежи индексов локальных максимумов и их значение.

Вызов Enumerable.Repeat() обеспечивает максимальные максимумы в самом начале и конце набора.

Сравнение с очередью after использует >=, так что локальный максимум будет найден в начале плато значений. Побочным эффектом является то, что значение в индексе 0 возвращается, если все значения в наборе равны, что может быть или не быть желательным.

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++;
    }
}

Ответ 4

Эта функция O (n). Он дает результаты по мере того, как он идет, поэтому он также будет иметь очень низкую накладную память.

    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;
        }
    }

Ответ 5

Используя пакет интерактивных расширений из команды Rx, вы можете решить эту проблему довольно аккуратно. Пакет имеет множество функций, связанных с различными сценариями буферизации/окон.

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;
}

Ответ 6

Вот моя версия. Он использует Queue для хранения последних элементов windowSize при перечислении источника. К сожалению, мне пришлось использовать неэффективный метод ElementAt Linq, чтобы найти проверенный элемент в Queue, потому что реализация Queue не раскрывает свой метод GetElement (он является внутренним). Для небольших размеров окон это не должно быть проблемой.

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++;
        }
    }
}

Пример использования:

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)}");

Выход:

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)