高效滚动最大和最小窗口 [英] Efficient Rolling Max and Min Window
问题描述
我想有效地计算滚动最大值和最小值.这意味着比每次窗口移动时从所有使用的值中重新计算最大值/最小值更好.
I want to calculate a rolling maximum and minimum value efficiently. Meaning anything better than recalculating the maximum/minimum from all the values in use every time the window moves.
这里有一篇帖子提出了同样的问题,有人发布了一个涉及某种堆栈方法的解决方案,该方法据称根据其评级有效.但是我这辈子都找不到它了.
There was a post on here that asked the same thing and someone posted a solution involving some kind of stack approach that supposedly worked based on its rating. However I can't find it again for the life of me.
在找到解决方案或帖子方面的任何帮助将不胜感激.谢谢大家!
Any help would be appreciated in finding a solution or the post. Thank you all!
推荐答案
您要使用的算法称为升序最小值 (C++ 实现).
The algorithm you want to use is called the ascending minima (C++ implementation).
要在 C# 中执行此操作,您需要获得一个 双端队列 类,并且NuGet 上有一个不错的应用,名为 Nito.Deque.
To do this in C#, you will want to get a double ended queue class, and a good one exists on NuGet under the name Nito.Deque.
我已经使用 Nito.Deque 编写了一个快速的 C# 实现,但我只是简单地检查了它,并且是从我的脑海中完成的,所以它可能是错误的!
I have written a quick C# implementation using Nito.Deque, but I have only briefly checked it, and did it from my head so it may be wrong!
public static class AscendingMinima
{
private struct MinimaValue
{
public int RemoveIndex { get; set; }
public double Value { get; set; }
}
public static double[] GetMin(this double[] input, int window)
{
var queue = new Deque<MinimaValue>();
var result = new double[input.Length];
for (int i = 0; i < input.Length; i++)
{
var val = input[i];
// Note: in Nito.Deque, queue[0] is the front
while (queue.Count > 0 && i >= queue[0].RemoveIndex)
queue.RemoveFromFront();
while (queue.Count > 0 && queue[queue.Count - 1].Value >= val)
queue.RemoveFromBack();
queue.AddToBack(new MinimaValue{RemoveIndex = i + window, Value = val });
result[i] = queue[0].Value;
}
return result;
}
}
这篇关于高效滚动最大和最小窗口的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!