高效滚动最大和最小窗口
我想有效地计算滚动的最大值和最小值。 比每次窗口移动时重新计算所有使用值中的最大值/最小值更好。
这里有一篇文章提出了同样的问题，并且有人发布了一个涉及某种堆栈方法的解决方案，据说根据其评级工作。 但是，对于我的生活，我再也找不到它。
在寻找解决方案或post时，我们将不胜感激。 谢谢你们！
您要使用的算法称为升序最小值 （C ++实现） 。
要在C＃中执行此操作，您将需要获得双端队列类，并且在NuGet上以名称Nito.Deque存在一个好的队列类。
我已经使用Nito.Deque编写了一个快速的C＃实现，但我只是简单地检查了它，并且从头开始做了所以它可能是错的！
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(); 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; } } 这是一种更有效地实现这一目标的方法。 您仍然需要偶尔计算该值，但除了某些退化数据（不断减少的值）之外，在此解决方案中最小化。
我们将自己限制在最大限度以简化事情，但也很容易扩展到最小。
您所需要的只是以下内容：
- 窗口本身，最初是空的。
- 当前最大值（
max），最初是任何值。 - 当前最大值（
maxcount）的计数，最初为零。
我们的想法是使用max和maxcount作为缓存来保持当前最大值。 在缓存有效的情况下，您只需要返回其中的值，即非常快速的恒定时间操作。
如果在请求最大值时缓存无效，则会填充缓存，然后返回该值。 这比前一段中的方法慢，但是一旦缓存有效，后续的最大请求将使用更快的方法。
以下是维护窗口和相关数据的操作：
-
获得下一个值
N -
如果窗口已满，请删除最早的条目
M如果maxcount大于0且M等于max，则减小maxcount。 一旦maxcount达到0，缓存就无效了，但是在用户请求最大值之前我们不需要担心（在此之前没有重新填充缓存的点）。 -
将
N添加到滚动窗口。 -
如果窗口大小现在为1（
N是唯一的当前条目），则将max设置为N并将maxcount为1，然后返回步骤1。 -
如果
maxcount大于0且N大于max，则将max设置为N，将maxcount为1，然后返回步骤1。 -
如果
maxcount大于0且N等于max，则增加maxcount。 -
回到第1步。
现在，在窗口管理进行的任何时候，您都可以请求最大值。 这是一个单独的操作，与窗口管理本身不同。 这可以按顺序使用以下规则来完成。
-
如果窗口为空，则没有最大值：引发exception或返回一些合理的标记值。
-
如果
maxcount大于0，则缓存有效：只返回max。 -
否则，需要重新填充缓存。 浏览整个列表，根据下面的代码段设置
max和maxcount。
set max to window[0], maxcount to 0 for each x in window[]: if x > max: set max to x, maxcount to 1 else: if x == max: increment maxcount
事实上，您主要维护最大值的缓存并且仅在需要时重新计算，这使得这比仅在添加条目时盲目地重新计算更有效。
对于一些明确的统计数据，我创建了以下Python程序。 它使用大小为25的滑动窗口并使用0到999之间的随机数（您可以使用这些属性来查看它们如何影响结果）。
首先是一些初始化代码。 注意stat变量，它们将用于计算缓存命中和未命中：
import random window = [] max = 0 maxcount = 0 maxwin = 25 statCache = 0 statNonCache = 0
然后根据我上面的描述向窗口添加一个数字的函数：
def addNum(n): global window global max global maxcount if len(window) == maxwin: m = window[0] window = window[1:] if maxcount > 0 and m == max: maxcount = maxcount - 1 window.append(n) if len(window) == 1: max = n maxcount = 1 return if maxcount > 0 and n > max: max = n maxcount = 1 return if maxcount > 0 and n == max: maxcount = maxcount + 1
接下来，从窗口返回最大值的代码：
def getMax(): global max global maxcount global statCache global statNonCache if len(window) == 0: return None if maxcount > 0: statCache = statCache + 1 return max max = window[0] maxcount = 0 for val in window: if val > max: max = val maxcount = 1 else: if val == max: maxcount = maxcount + 1 statNonCache = statNonCache + 1 return max
最后，测试工具：
random.seed() for i in range(1000000): val = int(1000 * random.random()) addNum(val) newmax = getMax() print("%d cached, %d non-cached"%(statCache,statNonCache))
请注意， 每次向窗口添加数字时，测试工具都会尝试获取最大值。 在实践中，可能不需要这样做。 换句话说，这是生成的随机数据的最坏情况。
出于伪统计目的运行该程序几次，我们得到（格式化和分析用于报告目的）：
960579 cached, 39421 non-cached 960373 cached, 39627 non-cached 960395 cached, 39605 non-cached 960348 cached, 39652 non-cached 960441 cached, 39559 non-cached 960602 cached, 39398 non-cached 960561 cached, 39439 non-cached 960463 cached, 39537 non-cached 960409 cached, 39591 non-cached 960798 cached, 39202 non-cached ======= ====== 9604969 395031
因此，您可以看到，对于随机数据，平均只有约3.95％的案例导致计算命中（缓存未命中）。 绝大多数人使用缓存的值。 这应该比每次插入窗口时重新计算最大值要好得多。
一些会影响该百分比的事情将是：
- 窗口大小。 较大的大小意味着缓存命中的可能性更大，从而提高了百分比。 例如，窗口大小加倍几乎使缓存未命中减半（达到1.95％）。
- 可能值的范围。 此处较少的选择意味着窗口中的缓存命中更有可能。 例如，将范围从
0..999到0..9可以大大减少缓存未命中率（0.85％）。
我假设通过“窗口”你的意思是a[start]到a[start + len] ，并且该start移动。 考虑最小值，最大值是相似的，并且移动到窗口a[start + 1]到a[start + len + 1] 。 那么只有当（a） a[start + len + 1] < min （较小的值进入）或（b） a[start] == min （ a[start] == min之一）时，窗口的最小值才会改变离开;重新计算最小值）。
另一种可能更有效的方法是使用第一个窗口填充优先级队列，并使用每个值进入/离开进行更新，但我认为这不是更好（优先级队列不适合“选择”从中间的随机元素“（在推进窗口时你需要做什么）。代码会更复杂。更好地坚持简单的解决方案，直到certificate性能不可接受，并且这段代码是负责任的（大部分）资源消耗。
我昨天写了自己的算法，并要求改进，我在这里被提到。 确实这个算法更优雅。 我不确定它是否提供恒定速度计算，无论窗口大小如何，但无论如何，我测试了性能与我自己的缓存算法（相当简单，并且可能使用与其他人提出的相同的想法）。 缓存速度提高了8-15倍（使用5,50,300,1000的滚动窗口测试我不需要更多）。 以下是具有秒表和结果validation的替代方案。
static class Program { static Random r = new Random(); static int Window = 50; //(small to facilitate visual functional test). eventually could be 100 1000, but not more than 5000. const int FullDataSize =1000; static double[] InputArr = new double[FullDataSize]; //array prefilled with the random input data. //====================== Caching algo variables static double Low = 0; static int LowLocation = 0; static int CurrentLocation = 0; static double[] Result1 = new double[FullDataSize]; //contains the caching mimimum result static int i1; //incrementor, just to store the result back to the array. In real life, the result is not even stored back to array. //====================== Ascending Minima algo variables static double[] Result2 = new double[FullDataSize]; //contains ascending miminum result. static double[] RollWinArray = new double[Window]; //array for the caching algo static Deque RollWinDeque = new Deque (); //Niro.Deque nuget. static int i2; //used by the struct of the Deque (not just for result storage) //====================================== my initialy proposed caching algo static void CalcCachingMin(double currentNum) { RollWinArray[CurrentLocation] = currentNum; if (currentNum <= Low) { LowLocation = CurrentLocation; Low = currentNum; } else if (CurrentLocation == LowLocation) ReFindHighest(); CurrentLocation++; if (CurrentLocation == Window) CurrentLocation = 0; //this is faster //CurrentLocation = CurrentLocation % Window; //this is slower, still over 10 fold faster than ascending minima Result1[i1++] = Low; } //full iteration run each time lowest is overwritten. static void ReFindHighest() { Low = RollWinArray[0]; LowLocation = 0; //bug fix. missing from initial version. for (int i = 1; i < Window; i++) if (RollWinArray[i] < Low) { Low = RollWinArray[i]; LowLocation = i; } } //======================================= Ascending Minima algo based on http://stackoverflow.com/a/14823809/2381899 private struct MinimaValue { public int RemoveIndex { get; set; } public double Value { get; set; } } public static void CalcAscendingMinima (double newNum) { //same algo as the extension method below, but used on external arrays, and fed with 1 data point at a time like in the projected real time app. while (RollWinDeque.Count > 0 && i2 >= RollWinDeque[0].RemoveIndex) RollWinDeque.RemoveFromFront(); while (RollWinDeque.Count > 0 && RollWinDeque[RollWinDeque.Count - 1].Value >= newNum) RollWinDeque.RemoveFromBack(); RollWinDeque.AddToBack(new MinimaValue { RemoveIndex = i2 + Window, Value = newNum }); Result2[i2++] = RollWinDeque[0].Value; } public static double[] GetMin(this double[] input, int window) { //this is the initial method extesion for ascending mimima //taken from http://stackoverflow.com/a/14823809/2381899 var queue = new Deque (); 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; } //============================================ Test program. static void Main(string[] args) { //this it the test program. //it runs several attempts of both algos on the same data. for (int j = 0; j < 10; j++) { Low = 12000; for (int i = 0; i < Window; i++) RollWinArray[i] = 10000000; //Fill the data + functional test - generate 100 numbers and check them in as you go: InputArr[0] = 12000; for (int i = 1; i < FullDataSize; i++) //fill the Input array with random data. //InputArr[i] = r.Next(100) + 11000;//simple data. InputArr[i] = InputArr[i - 1] + r.NextDouble() - 0.5; //brownian motion data. Stopwatch stopwatch = new Stopwatch(); stopwatch.Start(); for (int i = 0; i < FullDataSize; i++) //run the Caching algo. CalcCachingMin(InputArr[i]); stopwatch.Stop(); Console.WriteLine("Caching : " + stopwatch.ElapsedTicks + " mS: " + stopwatch.ElapsedMilliseconds); stopwatch.Reset(); stopwatch.Start(); for (int i = 0; i < FullDataSize; i++) //run the Ascending Minima algo CalcAscendingMinima(InputArr[i]); stopwatch.Stop(); Console.WriteLine("AscMimima: " + stopwatch.ElapsedTicks + " mS: " + stopwatch.ElapsedMilliseconds); stopwatch.Reset(); i1 = 0; i2 = 0; RollWinDeque.Clear(); } for (int i = 0; i < FullDataSize; i++) //test the results. if (Result2[i] != Result1[i]) //this is a test that algos are valid. Errors (mismatches) are printed. Console.WriteLine("Current:" + InputArr[i].ToString("#.00") + "\tLowest of " + Window + "last is " + Result1[i].ToString("#.00") + " " + Result2[i].ToString("#.00") + "\t" + (Result1[i] == Result2[i])); //for validation purposes only. Console.ReadLine(); } }