文章/答案/技术大牛

发布

社区首页 >问答首页 >有效滚动最大和最小窗口

问有效滚动最大和最小窗口
EN

Stack Overflow用户

提问于 2013-02-12 00:49:53

回答 5查看 9.4K关注 0票数 13

我想高效地计算滚动最大值和最小值。这意味着比每次窗口移动时根据所有正在使用的值重新计算最大值/最小值更好。

这里有一个帖子问了同样的问题，有人贴出了一个解决方案，涉及某种堆栈方法，应该是基于其评级的工作。然而，我再也找不到它了。

在寻找解决方案或帖子时，任何帮助都将不胜感激。谢谢大家！

performance

回答 5

Stack Overflow用户

回答已采纳

发布于 2013-02-12 00:59:59

您要使用的算法称为ascending minima (C++ implementation)。

要在C#中实现这一点，您需要获得一个double ended queue类，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<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;
    }
}

票数 7

Stack Overflow用户

发布于 2013-02-12 01:01:52

这里有一种更有效的方法。您仍然必须偶尔计算该值，但是，除了某些退化数据(不断减少的值)之外，在此解决方案中会最小化该值。

我们会将自己限制在最大值以简化事情，但也可以简单地将其扩展到最小值。

你所需要的就是：

窗口本身，初始为空。
当前最大值(max)，初始为任何值。
当前最大值(maxcount)的计数，初始为零。

这个想法是使用max和maxcount作为缓存来保存当前的最大值。在缓存有效的情况下，您只需返回其中的值，这是一个非常快速的恒定时间操作。

如果在您请求最大值时缓存无效，它将填充缓存，然后返回该值。这比上一段中的方法慢，但一旦缓存有效，随后的最大请求将再次使用该更快的方法。

下面是维护窗口和相关数据的方法：

获取下一个值N.

If窗口已满，删除最早的条目

M。如果maxcount大于0并且M等于max，则递减maxcount。一旦maxcount达到0，缓存就无效了，但在用户请求最大值之前，我们不必担心这一点(在此之前，重新填充缓存是没有意义的)。
将N添加到滚动窗口。
如果窗口大小现在是1(该N是唯一的当前条目)，则将max设置为N，并将<代码>D30设置为1，然后返回步骤1。<代码>H231<代码>H132如果<代码>D33大于0并且<代码>D34大于<代码>D35，将max设置为N，将maxcount设置为1，然后返回步骤1。
如果maxcount大于0且N等于max，则将maxcount.
Go递增回到步骤1。

现在，在窗口管理正在进行的任何时候，您都可以请求最大值。这是一个独立的操作，不同于窗口管理本身。这可以按顺序使用以下规则来完成。

如果窗口为空，则没有最大值:引发异常或返回一些合理的标记值。
如果maxcount大于0，则缓存有效:只需返回max.
Otherwise，缓存需要重新填充。浏览整个列表，按照下面的代码片段设置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 (包括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%)。

票数 3

Stack Overflow用户

发布于 2013-02-12 01:03:37

我假设“窗口”指的是从a[start]到a[start + len]的范围，并且start一直在移动。考虑到最小值，最大值是相似的，并且移动到窗口a[start + 1]到a[start + len + 1]。然后，只有当(a) a[start + len + 1] < min (进来的值较小)或(b) a[start] == min (刚刚离开的最小值之一；重新计算最小值)时，窗口的最小值才会改变。

另一种可能更有效的方法是用第一个窗口填充优先级队列，并在每个值进入/离开时进行更新，但我不认为这样做更好(优先级队列不适合于“从中间挑选随机元素”(当窗口前进时需要做的事情)。而且代码会复杂得多。最好坚持简单的解决方案，直到证明性能是不可接受的，并且这段代码负责(大部分)资源消耗。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/14823713

复制

判断浏览器窗口滚动到最底部

overflow scroll 事件

首先是昨天我们说的vue中绑定@scroll事件，别忘了加对应的高度，以及检查overflow-y：

阿超

2022/08/21

9000