utilise pour les machines d'état

Question

Dans quels domaines de la programmation utiliserais-je des machines d'état? Pourquoi ? Comment pourrais-je en implémenter un?

EDIT: veuillez donner un exemple concret, si ce n’est pas trop demander.

Answer 1

Dans quels domaines de la programmation, j'utilise une machine à état?

L'utilisation d'une machine d'état pour représenter un réel (ou logique) de l'objet qui peut exister que dans un nombre limité de conditions ("membres") et progresse d'un état à l'autre en fonction d'un ensemble fixe de règles.

Pourquoi voudrais-je utiliser une machine à état?

Un état est souvent une machine très compacte pour représenter un ensemble complexe de règles et de conditions, et pour traiter diverses entrées. Vous verrez des machines d'état dans les systèmes embarqués qui ont une mémoire limitée. Bien mis en œuvre, d'une machine à état est l'auto-documentation, parce que chaque état logique représente une condition physique. Une machine d'état peut être réalisée dans une minuscule quantité de code par rapport à sa procédure équivalente et fonctionne de manière extrêmement efficace. En outre, les règles qui régissent les changements d'état peuvent souvent être stockées en tant que données dans un tableau, fournissant une représentation compacte qui peut être facilement mis à jour.

Comment puis-je mettre en œuvre un?

Exemple Trivial:

enum states {      // Define the states in the state machine.
  NO_PIZZA,        // Exit state machine.
  COUNT_PEOPLE,    // Ask user for # of people.
  COUNT_SLICES,    // Ask user for # slices.
  SERVE_PIZZA,     // Validate and serve.
  EAT_PIZZA        // Task is complete.
} STATE;

STATE state = COUNT_PEOPLE;
int nPeople, nSlices, nSlicesPerPerson;

// Serve slices of pizza to people, so that each person gets
/// the same number of slices.   
while (state != NO_PIZZA)  {
   switch (state)  {
   case COUNT_PEOPLE:  
       if (promptForPeople(&nPeople))  // If input is valid..
           state = COUNT_SLICES;       // .. go to next state..
       break;                          // .. else remain in this state.
   case COUNT_SLICES:  
       if (promptForSlices(&nSlices))
          state = SERVE_PIZZA;
        break;
   case SERVE_PIZZA:
       if (nSlices % nPeople != 0)    // Can't divide the pizza evenly.
       {                             
           getMorePizzaOrFriends();   // Do something about it.
           state = COUNT_PEOPLE;      // Start over.
       }
       else
       {
           nSlicesPerPerson = nSlices/nPeople;
           state = EAT_PIZZA;
       }
       break;
   case EAT_PIZZA:
       // etc...
       state = NO_PIZZA;  // Exit the state machine.
       break;
   } // switch
} // while

Notes:

• L'exemple utilise un switch() explicites case/break états pour des raisons de simplicité. Dans la pratique, un case souvent "de l'automne à travers" à l'état suivant.

• Pour la facilité de l'entretien d'un grand état de la machine, le travail effectué dans chaque case peut être encapsulé dans un "travailleur" de la fonction. Obtenez de l'entrée au haut de l' while(), le passer à la fonction worker, et vérifier la valeur de retour du travailleur à calculer l'état suivant.

• Pour la compacité, l'ensemble de l' switch() peut être remplacé par un tableau de pointeurs de fonction. Chaque état est incarnée par une fonction dont la valeur de retour est un pointeur vers l'état suivant. Avertissement: il peut simplifier la machine de l'etat ou de la rendre totalement désuète, afin d'envisager la mise en œuvre de soin!

• Un dispositif intégré peut être mis en œuvre comme une machine d'état qui sort uniquement sur une erreur catastrophique, après lequel il effectue une réinitialisation matérielle et rentre dans la machine d'état.

Answer 2

Quelques grandes réponses déjà. Pour une perspective légèrement différente, envisager la recherche d'un texte dans une chaîne plus longue. Quelqu'un l'a déjà mentionné expressions régulières, et c'est vraiment un cas particulier, certes important.

Considérons la suite de l'appel de la méthode:

very_long_text = "Bereshit bara Elohim et hashamayim ve'et ha'arets." …
word = "Elohim"
position = find_in_string(very_long_text, word)

Comment voulez-vous mettre en oeuvre find_in_string? L'approche facile serait d'utiliser une boucle imbriquée, quelque chose comme ceci:

for i in 0 … length(very_long_text) - length(word):
    found = true
    for j in 0 … length(word):
        if (very_long_text[i] != word[j]):
            found = false
            break
    if found: return i
return -1

Outre le fait que c'est inefficace, il constitue un état de la machine! Les membres ici sont un peu cachés; permettez-moi de réécrire le code légèrement pour les rendre plus visibles:

state = 0
for i in 0 … length(very_long_text) - length(word):
    if very_long_text[i] == word[state]:
        state += 1
        if state == length(word) + 1: return i
    else:
        state = 0
return -1

Les différents membres représentent toutes les différentes positions dans le mot que nous rechercher. Il y a deux transitions pour chaque nœud dans le graphe: si les lettres de match, aller à l'état suivant; pour tous les autres intrants (c'est à dire tous les autres de la lettre à la position actuelle), revenir à zéro.

Cette légère reformulation a un énorme avantage: il peut maintenant être modifié afin d'obtenir de meilleurs performances à l'aide de certaines techniques de base. En fait, à chaque avancée de la chaîne algorithme de recherche (actualisation de l'indice des structures de données pour le moment) s'appuie sur le dessus de cet état de la machine et améliore certains aspects.

Answer 3

Ce genre de tâches?

N'importe quelle tâche, mais de ce que j'ai vu, l'Analyse de toute sorte est fréquemment mis en œuvre comme une machine d'état.

Pourquoi?

L'analyse d'une grammaire n'est généralement pas une tâche facile. Au cours de la phase de conception, il est assez courant qu'un diagramme d'état est établi pour tester l'algorithme d'analyse. La traduction que pour une machine d'état de la mise en œuvre est une tâche relativement simple.

Comment?

Eh bien, vous êtes seulement limité par votre imagination.

Je l'ai vu faire avec les cas des boucles et des instructions.

Je l'ai vu faire avec des étiquettes et des goto états

J'ai même vu faire avec les structures de pointeurs de fonction qui représentent l'état actuel. Lorsque les modifications de l'état, une ou plusieurs de pointeur de fonction est mis à jour.

Je l'ai vu faire dans le code, où un changement d'état signifie simplement que vous vous trouvez dans une autre section de code. (pas de variables d'état, et redundent code si nécessaire. Cela peut être démontré comme très simplement, ce qui est utile pour les très petits ensembles de données.

int a[10] = {some unsorted integers};

not_sorted_state:;
    z = -1;
    while (z < (sizeof(a) / sizeof(a[0]) - 1)
    {
        z = z + 1
        if (a[z] > a[z + 1])
        {
            // ASSERT The array is not in order
            swap(a[z], a[z + 1];        // make the array more sorted
            goto not_sorted_state;      // change state to sort the array
        }
    }
    // ASSERT the array is in order

Il n'existe pas de variables d'état, mais le code lui-même représente l'état

Answer 4

Le modèle de conception d' état est une manière orientée objet de représenter l'état d'un objet au moyen d'une machine à états finis. Cela permet généralement de réduire la complexité logique de l'implémentation de cet objet (imbriqués si, nombreux indicateurs, etc.).

Answer 5

La plupart des workflows peuvent être implémentés en tant que machines d'état. Par exemple, traiter des demandes de congé ou des commandes.

Si vous utilisez .NET, essayez Windows Workflow Foundation. Vous pouvez rapidement implémenter un workflow de machine à états.