代码之家 › 专栏 › 技术社区 › Peter M

滑动窗口搜索算法

search algorithm

0

Peter M · 技术社区 · 16 年前

我需要一个数据存储类型和算法来跟踪我看到的最后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,所以有人能向我简单介绍一下如何做到这一点吗?另外,为了实现这一点,我将在C.NET 3.5中在Windows XP系统上实现,该系统可以看到3GB的RAM(和i7处理器)。- 闻这台机器以前有Windows7,但它有8GB的内存是 TDWTF的故事)

最后,我将在这个系统的任何给定运行中扫描100000到数百万个项目的数量。在系统发生故障之前,我不需要跟踪整个运行,只需要跟踪所有项目的子集。当发生这种情况时,我可以转储所有收集到的数据,然后重新开始整个过程。但是,对于我跟踪的每个项目,我必须至少保留通过/失败状态和10个字符的字符串。所以我也在寻找如何在系统中收集和维护这些数据的建议。尽管我很想说:“嗯,即使整个过程以100%通过,它也能在内存中容纳所有内容,所以它会为您转到一个数组中去!”

1 回复 | 直到 14 年前

1

5

Nikita Rybak 16 年前

我知道这将以类似正则表达式搜索的方式结束
事实上,问题要简单得多。我们可以利用这样一个事实,即我们正在搜索只包含坏结果(或只包含好结果)的子序列。

像这样的东西应该管用

// 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