Búsqueda de máximos locales en un rango dinámico

Question

Trabajando en C#, necesito encontrar todos los picos locales en una lista de dobles y devolverlos como otra lista de dobles. Esto parece bastante simple si tengo un número de valores que estoy comparando en una "ventana" de valores dada, pero necesito poder pasar este tamaño de ventana a la función misma. Esto puede ser confuso, pero básicamente necesito algo como esto:

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

donde si 'rangeOfPeaks' fue 5, el valor 'actual' se compararía con 2 valores en cada lado de la misma para determinar si se trataba de una pico o no. Si 'rangeOfPeaks' fuera 11, el valor actual se compararía con 5 valores en cada lado. Creo que este es un algoritmo bastante básico, sin embargo, no he tenido éxito en encontrar ningún buen método para detectar un pico como este. ¿Alguien había echo esto antes? Cualquier ayuda sería apreciada. ¡Gracias por adelantado!

Answer 1

Probablemente hay formas más eficientes, pero LINQ hace que esta bastante sencillo

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

Answer 2

Esta función es O (n). Da resultados a medida que avanza, por lo que también tendrá muy poca carga de memoria.

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

Answer 3

me sugieren algunos cambios en el puesto de Levy ...

1) Código de Levy inició una excepción cuando los valores especificados IList era una línea casi recta.

2) Creo que el índice de los picos en la matriz es el resultado deseado. Considere por ejemplo, ¿qué pasaría si tuviéramos dos picos con dobles idénticos? Ops. Modificado para devolver el índice de picos en IList especificado.

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

Answer 4

Pregunta anterior que ya tiene una respuesta aceptada, pero quería algo mejor que O (n^2). Esta función es O (n * m) donde m es el tamaño de la ventana y tiene la ventaja de que realmente funciona también. El método devuelve tuplas de índices de máximos locales y su valor asociado.

Las llamadas a Enumerable.Repeat() aseguran que también se encuentren los valores máximos al principio y al final del conjunto.

La comparación con la cola after utiliza >= para que se encuentre un máximo local al principio de una meseta de valores. Un efecto secundario es que el valor en el índice 0 se devuelve si todos los valores en el conjunto son iguales, lo que puede o no ser deseable.

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

Answer 5

Utilizando el Interactive Extensions package del equipo de Rx, puede resolver este problema muy claramente. El paquete tiene muchas funciones para hacer con diferentes escenarios de almacenamiento en búfer/ventanas.

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