在动态范围内查找局部最大值

在C＃中工作，我需要在双精度列表中找到所有本地峰值，并将它们作为另一个列表双精度返回。 这看起来很简单，如果我在任何给定的“窗口”值中有一组我正在比较的值，但我需要能够将这个窗口大小实际传递给函数本身。 这可能令人困惑，但基本上我需要这样的东西：

public List FindPeaks(List values, double rangeOfPeaks) 

如果’rangeOfPeaks’为5，则将’current’值与其每一侧的2个值进行比较，以确定它是否为峰值。 如果’rangeOfPeaks’为11，则将当前值与每侧的5个值进行比较。 我认为这是一个非常基本的算法，但是，我找不到像这样检测峰值的任何好方法都没有成功。 有没有人曾经这样做过？ 任何帮助都将不胜感激。 提前致谢！

Answer 1

可能有更有效的方法，但LINQ使这非常简单

  static IList FindPeaks(IList values, int rangeOfPeaks) { List peaks = new List(); int checksOnEachSide = rangeOfPeaks / 2; for (int i = 0; i < values.Count; i++) { double current = values[i]; IEnumerable 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

我建议对Levy的post进行一些修改……

1）当指定值IList几乎是直线时，Levy的代码抛出exception。

2）我认为数组中峰的索引是期望的结果。 例如，如果我们有两个具有相同双精度的峰值会发生什么？ 行动。 更改为返回指定IList中峰值的索引。

  public static IList FindPeaks(IList values, int rangeOfPeaks) { List peaks = new List(); double current; IEnumerable 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 3

已经有一个已接受的答案的旧问题，但我想要比O（n ^ 2）更好的东西。 这个函数是O（n * m），其中m是窗口大小，并且具有实际工作的优点。 该方法返回局部最大值的索引及其相关值的元组。

调用Enumerable.Repeat()确保在集合的开头和结尾都找到最大值。

与after队列的比较使用>=以便在值的平台开始时找到局部最大值。 副作用是如果集合中的所有值相等，则返回索引0处的值，这可能是也可能不是所希望的。

 public static IEnumerable> LocalMaxima( IEnumerable 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( Enumerable.Repeat( double.NegativeInfinity, halfWindow ) ); var after = new Queue( 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 4

该函数是O（n）。 它产生结果，因此它也将具有非常低的内存开销。

  public static IEnumerable FindPeaks(IEnumerable 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 5

使用Rx团队的Interactive Extensions包 ，您可以非常巧妙地解决这个问题。 该软件包具有许多与不同缓冲/窗口方案相关的function。

 IEnumerable FindPeaks(IEnumerable numbers, int windowSize) { // Pad numbers to the left of  so that the first window of  is centred on the first item in  // 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 , stepping forward by one element each time var peaks = paddedNumbers.Buffer(windowSize, 1) .Select(range => range.Max()) .DistinctUntilChanged(); return peaks; }