滑動窗口搜索算法

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. 

我知道，這是要在像一個正則表達式搜索到結束，並具有高德納的模糊回憶浮出來的我記憶中的黑暗痕跡，所以任何人都可以向我簡單介紹一下如何做到這一點？另外值得一提的是，我將在Windows XP系統上的C＃.Net 3.5中實現這個功能，看到3GB Ram（和一個i7處理器 - sniff該機器曾經擁有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