滑动窗口搜索算法

Question

我需要一种数据存储类型和算法来跟踪我看到的最后N个项目的状态.每个项目的状态为"通过"或"失败",但如果连续的M项失败,则我监视的系统将被视为已失败.一旦认为系统出现故障,我就需要扫描数据历史记录并找到宽度为W的最后一个窗口,其中所有项目都处于"良好"状态.

例如,M = 4且W = 3:

    1 Good
    2 Good
    3 Good
    4 Good
    5 Good |
    6 Good |- Window of size 3 where all are good.
    7 Good |
    8 Bad
    9 Bad
    10 Good
    11 Good
    12 Bad
    13 Good
    14 Bad
    15 Bad
    16 Bad
    17 Bad  <== System is deemed bad at this point  So scan backwards to find "Good" window.

我知道这最终将会出现在正则表达式搜索之类的内容中,并且对Knuth的模糊回忆会浮现出我记忆中的黑暗深处,所以有人能指出我如何做到这一点的简单介绍吗？同样值得一提的是,我将在Windows XP系统上的C#.Net 3.5中实现这一点,看到3GB的Ram(和一个i7处理器 - 嗅探用于拥有Windows 7的机器,它确实有8GB的内存 - 但那是 TDWTF的故事)

最后,我将在该系统的任何给定运行中扫描100,000到数百万的项目数.我不需要跟踪整个运行,只需跟踪所有项目的子集,直到发生系统故障.当发生这种情况时,我可以转储我收集的所有数据并重新开始这个过程.但是对于我跟踪的每个项目,我必须至少保持通过/失败状态和10个字符串.所以我正在寻找有关如何在系统中收集和维护这些数据的建议.虽然我很想说 - "嗯,即使整个过程都以100%通过,它也会适合记忆,所以它可以为你排出阵列!"

Answer 1

我知道这最终会像正则表达式搜索一样
.问题实际上更简单.我们可以利用这样一个事实,即我们正在搜索仅包含不良结果(或仅有良好结果)的子序列.

这样的事情应该有效

// how many consecutive bad results we have at this point
int consecutiveFailures = 0;
// same for good results
int consecutivePasses = 0;
for each result
    if result == 'pass' then
        consecutiveFailures = 0;
        ++consecutivePasses;
    else if result == 'fail' then
        consecutivePasses = 0;
        ++consecutiveFailures;        
    end

    if consecutiveFailures == M
        // M consecutive failures, stop processing
        ...
    end
    if consecutivePasses >= W
        // record last set of W consecutive passes for later use
        ...
    end
end