Algorithme de recherche de fenêtre glissante

Question

J'ai besoin d'un type de stockage de données et d'un algorithme pour suivre l'état des N derniers éléments que j'ai vus. Chaque élément a un statut de réussite ou d'échec, mais le système que je surveille est considéré comme ayant échoué si les éléments M d'une ligne ont échoué. Une fois que le système est considéré comme ayant échoué, j'ai alors besoin de revenir en arrière dans l'historique des données et de trouver la dernière fenêtre de largeur W dans laquelle tous les éléments avaient un "bon" statut.

Par exemple, avec un M = 4 et 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. 

Je sais que cela va finir par quelque chose comme une recherche d'expression régulière et ont de vagues souvenirs de Knuth flotter la sombre recoins de ma mémoire, donc quelqu'un peut-il me diriger vers une introduction simple sur la façon de faire cela? Aussi pour ce que ça vaut, je vais l'implémenter en C# .Net 3.5 sur un système Windows XP en voyant 3 Go de RAM (et un processeur i7 - sniff la machine utilisée pour Windows 7 et il a 8 Go de mémoire - mais que était une histoire pour TDWTF)

Enfin, je vais numériser des nombres d'éléments dans les 100 000 à des millions dans un cycle donné de ce système. Je n'aurai pas besoin de garder une trace de la totalité de l'exécution, seulement le sous-ensemble de tous les éléments jusqu'à ce qu'une panne du système se produise. Quand cela arrive, je peux vider toutes mes données collectées et recommencer le processus. Cependant, pour chaque élément que je suis en train de suivre, je devrai conserver au moins le statut réussite/échec et une chaîne de 10 caractères. Donc, je cherche des suggestions sur la façon de recueillir et de maintenir ces données dans le système. Bien que je sois tenté de dire - "méh, tout ira bien en mémoire même si la course entière passe à 100%, alors c'est parti pour vous!"

Answer 1

Je sais que cela va finir par quelque chose comme une recherche d'expression régulière
Le problème est, en fait, beaucoup plus simple. Nous pouvons profiter du fait que nous recherchons des sous-séquences constituées uniquement de mauvais résultats (ou seulement de bons résultats).

Quelque chose comme cela devrait fonctionner

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