Алгоритм поиска в скользящем окне

Question

Мне нужен тип хранения данных и алгоритм для отслеживания состояния последних N элементов, которые я видел.Каждый элемент имеет статус «Пройдено» или «Не пройдено», но система, которую я отслеживаю, будет считаться неработоспособной, если М элементов подряд вышли из строя.Если система считается неисправной, мне нужно отсканировать историю данных и найти последнее окно ширины 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.

Я знаю, что это закончится чем-то вроде поиска по регулярному выражению, и смутные воспоминания о Кнуте всплывают из темной ниши моей памяти, так что могКто-нибудь указывает мне на простое введение о том, как это сделать?Кроме того, чего бы это ни стоило, я буду реализовывать это в C # .Net 3.5 в системе Windows XP, видя 3 ГБ оперативной памяти (и процессор i7 - снифф машина, на которой раньше была Windows 7, и она действительно имеет 8 ГБпамяти - но это было историей для TDWTF)

Наконец, я буду сканировать количество элементов в сотнях тысяч до миллионов в любом заданном запуске этой системы.Мне не нужно будет отслеживать весь прогон, только подмножество всех элементов, пока не произойдет системный сбой.Когда это произойдет, я могу сбросить все свои собранные данные и начать процесс заново.Однако для каждого элемента, который я отслеживаю, мне нужно сохранить как минимум статус «пройден / не пройден» и строку из 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