状態マシンの使用[終了]

https://stackoverflow.com/questions/255797

state-machine

05-07-2019
|

質問

ステートマシンはプログラミングのどの領域で使用しますか？どうして？どうすれば実装できますか？

編集：実際に例を挙げてください。質問が多すぎない場合。

解決

プログラミングのどの領域でステートマシンを使用しますか

状態マシンを使用して、限られた数の条件（＆quot; states ＆quot;）に存在し、ある状態から次の状態に進む（実または論理）オブジェクトを表します。ルールのセットを修正しました。

ステートマシンを使用する理由

ステートマシンは、多くの場合、複雑なルールと条件のセットを表し、さまざまな入力を処理するための非常にコンパクトな方法です。メモリが限られている組み込みデバイスにステートマシンが表示されます。適切に実装された状態マシンは、各論理状態が物理的な状態を表すため、自己文書化されます。ステートマシンは、手続き型と比較して tiny 量のコードで具体化でき、非常に効率的に実行されます。さらに、状態の変更を管理するルールは、多くの場合、テーブルにデータとして保存できるため、簡単に維持できるコンパクトな表現を提供します。

どのように実装できますか？

簡単な例：

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

注：

この例では、簡単にするために、明示的な case / break 状態で switch（）を使用しています。実際には、多くの場合、 case は「フォールスルー」します。次の状態に。
大規模なステートマシンの保守を容易にするために、各 case で行われた作業を＆quot; worker＆quot;にカプセル化できます。関数。 while（）の上部で入力を取得し、それをワーカー関数に渡し、ワーカーの戻り値を確認して次の状態を計算します。
コンパクトにするために、 switch（）全体を関数ポインタの配列に置き換えることができます。各状態は、戻り値が次の状態へのポインターである関数によって具体化されます。 警告：これにより、ステートマシンが簡素化されるか、完全にメンテナンス不能になる可能性があるため、実装を慎重に検討してください。
組み込みデバイスは、致命的なエラーでのみ終了するステートマシンとして実装できます。その後、ハードリセットが実行され、ステートマシンに再び入ります。

他のヒント

すでにいくつかの素晴らしい答え。わずかに異なる観点から、より大きな文字列でテキストを検索することを検討してください。誰かがすでに正規表現に言及しており、これは重要なものではありますが、本当に特別な場合です。

次のメソッド呼び出しを検討してください：

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

find_in_string をどのように実装しますか？簡単なアプローチでは、次のようなネストされたループを使用します。

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

これは非効率的であるという事実は別として、ステートマシンを形成します！ここの状態はやや隠されています。コードを見やすくするためにコードを少し書き直します：

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

ここでの異なる状態は、検索する単語内のすべての異なる位置を直接表しています。グラフの各ノードには2つの遷移があります。文字が一致する場合、次の状態に進みます。他のすべての入力（つまり、現在の位置にある他のすべての文字）については、ゼロに戻ります。

このわずかな再定式化には大きな利点があります。いくつかの基本的な手法を使用して、より良いパフォーマンスが得られるように調整できるようになりました。実際、すべての高度な文字列検索アルゴリズム（現時点ではインデックスデータ構造を割引きます）は、このステートマシンの上に構築され、いくつかの側面を改善しています。

どのようなタスクですか

任意のタスクですが、私が見たものから、あらゆる種類の解析は状態マシンとして頻繁に実装されます。

なぜ？

一般に、文法の解析は簡単な作業ではありません。設計段階では、解析アルゴリズムをテストするための状態図が作成されるのがかなり一般的です。それをステートマシンの実装に変換するのは非常に簡単なタスクです。

方法？

まあ、あなたはあなたの想像力によってのみ制限されます。

caseステートメントとループ。

ラベルとgoto ステートメント

私は、現在の状態を表す関数ポインタの構造を使ってそれを見たことがあります。状態が変化すると、1つ以上の関数ポインターが更新されます。

コードでのみ行われているのを見ましたが、状態の変化とは単にコードの別のセクションで実行していることを意味します。（状態変数はなく、必要に応じて冗長コード。これは非常に単純な並べ替えとして示すことができ、非常に小さなデータセットにのみ役立ちます。

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

状態変数はありませんが、コード自体は状態を表します

State デザインパターンは、オブジェクト指向の方法でオブジェクトの状態を表します有限状態マシンの手段。通常、そのオブジェクトの実装の論理的な複雑さ（ifのネスト、多くのフラグなど）を減らすのに役立ちます

ほとんどのワークフローは、ステートマシンとして実装できます。たとえば、休暇申請や注文を処理します。

.NETを使用している場合は、Windows Workflow Foundationを試してください。ステートマシンのワークフローを非常に迅速に実装できます。

C＃を使用している場合、イテレータブロックを記述するときはいつでも、コンパイラに状態マシンを構築するように要求しています（イテレータのどこにいるかなどを追跡します）。

これは、テスト済みで動作するステートマシンの例です。シリアルストリームを使用しているとします（シリアルポート、tcp / ipデータ、またはファイルが典型的な例です）。この場合、同期、長さ、およびペイロードの3つの部分に分割できる特定のパケット構造を探しています。 3つの状態があり、1つはアイドル状態で、同期を待機しています。2つ目は、次のバイトの長さが適切な同期であり、3つ目の状態がペイロードを蓄積していることです。

この例は、バッファが1つしかない純粋なシリアルです。ここに記載されているように、不良バイトまたはパケットから回復し、おそらくパケットを破棄しますが、最終的には回復します。スライディングウィンドウのような他のことを実行して、すぐに回復することができます。これは、部分的なパケットがカットされてから新しい完全なパケットが開始されると言う場所です。以下のコードはこれを検出せず、パケット全体だけでなく部分的なパケットも破棄し、次のパケットで回復します。すべてのパケットをすべて処理する必要がある場合は、スライディングウィンドウが表示されます。

シリアルデータストリーム、tcp / ip、ファイルi / oなど、常にこの種のステートマシンを使用しています。または、おそらくtcp / ipプロトコル自体、メールを送信する、ポートを開く、サーバーが応答を送信するのを待つ、HELOを送信する、サーバーがパケットを送信するのを待つ、パケットを送信する、返信を待つ、本質的にその場合と下の場合、次のバイト/パケットが来るのを待っているアイドリングかもしれません。あなたが待っていたものを思い出すために、あなたが使用できる何かを待っているコードを再利用するためにも状態変数。ステートマシンがロジックで使用されるのと同じ方法（次のクロックを待つ、私が待っていたもの）。

ロジックのように、状態ごとに異なる処理を行いたい場合があります。この場合、適切な同期パターンがあれば、ストレージへのオフセットをリセットし、チェックサムアキュムレータをリセットします。パケットの長さの状態は、通常の制御パスから抜け出すことができる場合を示しています。すべてではありませんが、実際には、多くのステートマシンが通常のパス内でジャンプしたりループしたりする可能性があります。以下のものはほぼ線形です。

これが役立つことを望み、ステートマシンがソフトウェアでさらに使用されることを願っています。

テストデータには、ステートマシンが回復する意図的な問題があります。最初の正常なパケット、不正なチェックサムを持つパケット、および無効な長さを持つパケットの後に、いくつかのガベージデータがあります。私の出力は：

良好なパケット：FA0712345678EB 無効な同期パターン0x12 無効な同期パターン0x34 無効な同期パターン0x56 チェックサムエラー0xBF 無効なパケット長0 無効な同期パターン0x12 無効な同期パターン0x34 無効な同期パターン0x56 無効な同期パターン0x78 無効な同期パターン0xEB 良いパケット：FA081234567800EA これ以上のテストデータ

不正なデータにもかかわらず、ストリーム内の2つの正常なパケットが抽出されました。そして、不正なデータが検出され、対処されました。

 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>

unsigned char testdata[] =
{
    0xFA,0x07,0x12,0x34,0x56,0x78,0xEB,  
    0x12,0x34,0x56,  
    0xFA,0x07,0x12,0x34,0x56,0x78,0xAA,  
    0xFA,0x00,0x12,0x34,0x56,0x78,0xEB,  
    0xFA,0x08,0x12,0x34,0x56,0x78,0x00,0xEA  
};

unsigned int testoff=0;

//packet structure  
// [0] packet header 0xFA  
// [1] bytes in packet (n)  
// [2] payload  
// ... payload  
// [n-1] checksum  
//  

unsigned int state;

unsigned int packlen;  
unsigned int packoff;  
unsigned char packet[256];  
unsigned int checksum;  

int process_packet( unsigned char *data, unsigned int len )  
{  
    unsigned int ra;  

    printf("good packet:");
    for(ra=0;ra<len;ra++) printf("%02X",data[ra]);
    printf("\n");
}  
int getbyte ( unsigned char *d )  
{  
    //check peripheral for a new byte  
    //or serialize a packet or file  

    if(testoff<sizeof(testdata))
    {
        *d=testdata[testoff++];
        return(1);
    }
    else
    {
        printf("no more test data\n");
        exit(0);
    }
    return(0);
}

int main ( void )  
{  
    unsigned char b;

    state=0; //idle

    while(1)
    {
        if(getbyte(&b))
        {
            switch(state)
            {
                case 0: //idle
                    if(b!=0xFA)
                    {
                        printf("Invalid sync pattern 0x%02X\n",b);
                        break;
                    }
                    packoff=0;
                    checksum=b;
                    packet[packoff++]=b;

                    state++;
                    break;
                case 1: //packet length
                    checksum+=b;
                    packet[packoff++]=b;

                    packlen=b;
                    if(packlen<3)
                    {
                        printf("Invalid packet length %u\n",packlen);
                        state=0;
                        break;
                    }

                    state++;
                    break;
                case 2: //payload
                    checksum+=b;
                    packet[packoff++]=b;

                    if(packoff>=packlen)
                    {
                        state=0;
                        checksum=checksum&0xFF;
                        if(checksum)
                        {
                            printf("Checksum error 0x%02X\n",checksum);
                        }
                        else
                        {
                            process_packet(packet,packlen);
                        }
                    }
                    break;
            }
        }

        //do other stuff, handle other devices/interfaces

    }
}

ステートマシンはどこにでもあります。ステートマシンは、メッセージを受信したときに解析する必要がある通信インターフェイスで重要です。また、組み込みシステムの開発では、タイミングの制約が厳しいため、タスクを複数のタスクに分割する必要が何度もありました。

QAインフラストラクチャ。スクリーンスクレイプまたはテスト対象プロセスの実行を目的としています。（これは私の特定の経験分野です。現在の状態をスタックにプッシュし、すべてのTTYベースのスクリーンスクレーパーで使用するための状態ハンドラー選択のさまざまな方法を使用することをサポートする最後の雇用者のためにPythonでステートマシンフレームワークを構築しました）。 TTYアプリケーションを実行すると、限られた数の既知の状態を通過し、古い状態に戻すことができるため、概念モデルはうまく適合します（ネストされたメニューの使用について考えてください）。これはリリースされました（雇用主の許可を得て）。 Bazaar を使用して、 http://web.dyfis.net/bzr/isg_state_machine_framework/ コードを表示する場合。

チケット、プロセス管理、ワークフローシステム-チケットに、NEW、TRIAGED、IN-PROGRESS、NEEDS-QA、FAILED-QAおよびVERIFIED（たとえば）間の移動を決定する一連のルールがある場合、 'シンプルなステートマシンを取得しました。

小規模で、すぐに証明可能な組み込みシステムの構築-信号機の信号伝達は、考えられるすべての状態のリストが完全に列挙されて知られているという重要な例です。

パーサーとレクサーは、ステートマシンベースです。これは、ストリーミングで何かが決定される方法は、そのときの場所に基づいているためです。

多くのデジタルハードウェア設計では、回路の動作を指定するステートマシンを作成する必要があります。 VHDLを記述している場合は、かなり多く表示されます。

FSMは、複数の状態があり、刺激時に異なる状態に移行する必要があるすべての場所で使用されます。

（これは、少なくとも理論的にはほとんどの問題を網羅していることがわかります）

正規表現は、有限状態マシン（または「有限状態オートマトン」）の別の例です;）遊びに来てください。

コンパイルされた正規表現は有限状態マシンであり、正規表現が一致できる文字列のセットは、有限状態オートマトンが受け入れることができる言語（「正規言語」と呼ばれる）とまったく同じです。

ここで実際に使用されている理由を説明するものは何も表示されませんでした。

実用的な目的のために、プログラマーは通常、操作の途中でスレッド/出口を返すことを余儀なくされたときに1つを追加する必要があります。

たとえば、マルチステートHTTPリクエストがある場合、次のようなサーバーコードがあります。

Show form 1
process form 1
show form 2
process form 2

問題は、フォームを表示するたびに、コードがすべて論理的に流れて同じ変数を使用する場合でも、サーバー上のスレッド全体（ほとんどの言語）を終了する必要があることです。

コードにブレークを入れてスレッドを返す動作は、通常switchステートメントで行われ、ステートマシン（非常に基本的なバージョン）と呼ばれるものを作成します。

より複雑になると、どの状態が有効であるかを把握することが本当に難しくなります。通常、人々は＆quot; 状態遷移テーブル＆quot;を定義します。すべての状態遷移を記述します。

ステートマシンライブラリを作成しました。実際に状態遷移表を直接実装します。それは本当にきちんとした運動でしたが、どれだけうまくいくかわかりません...

有限状態マシンは、あらゆる自然言語の形態学的解析に使用できます。

理論的には、これは形態と構文が計算レベル間で分割されていることを意味します.1つは有限状態であり、もう1つはほとんど文脈依存ではありません（したがって、他の理論的なモデルが単語から形態素と形態素の関係ではなく単語）。

これは、機械翻訳や単語のグロスの分野で役立ちます。表面的には、構文解析や依存関係解析など、NLPのささいな機械学習アプリケーション用に抽出する低コストの機能です。

詳細を知りたい場合は、BeesleyとKarttunenによる Finite State Morphology と、PARCで設計されたXerox Finite State Toolkitをご覧ください。

現在取り組んでいるシステムの例があります。私は株式取引システムを構築中です。注文の状態を追跡するプロセスは複雑になる可能性がありますが、注文のライフサイクルの状態図を作成すると、既存の注文に新しい着信トランザクションをより簡単に適用できます。現在の状態から、新しいトランザクションが20のいずれかではなく、3つのもののいずれかにしかならないことがわかっている場合、そのトランザクションの適用に必要な比較ははるかに少なくなります。これにより、コードがはるかに効率的になります。

ステートドリブンのコードは、特定のタイプのロジックを実装するのに適した方法です（パーサーが例です）。たとえば、次のようないくつかの方法で実行できます。

特定のポイントで実際に実行されているコードのビットを駆動する状態（つまり、状態は、記述しているコードの一部で暗黙的です）。再帰降下パーサーは、このタイプのコードの良い例です。
switchステートメントなどの条件で何をするかを駆動する状態。
Lex などのパーサー生成ツールによって生成されたものなどの明示的な状態マシンおよび Yacc 。

すべての状態駆動コードが解析に使用されるわけではありません。一般的なステートマシンジェネレーターは、 smc です。ステートマシンの定義を（その言語で）吸入し、ステートマシンのコードをさまざまな言語で吐き出します。

良い答え。これが私の2セントです。有限状態マシンは、テーブルやwhileスイッチなど、複数の異なる方法で実装できる理論上のアイデアです（ただし、goto horrors と言う方法は誰にも教えないでください）。 FSMは正規表現に対応し、その逆も同様です。正規表現は構造化プログラムに対応しているため、FSMを実装する構造化プログラムを時々書くだけで済みます。たとえば、数値の単純なパーサーは、次の行に沿って記述できます。

/* implement dd*[.d*] */
if (isdigit(*p)){
    while(isdigit(*p)) p++;
    if (*p=='.'){
        p++;
        while(isdigit(*p)) p++;
    }
    /* got it! */
}

アイデアが得られます。また、より高速に実行される方法がある場合、それが何であるかわかりません。

典型的なユースケースは信号機です。

実装上の注意：Java 5の列挙には抽象メソッドを含めることができます。これは、状態依存の動作をカプセル化する優れた方法です。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow