プログラミングのどの領域でステート マシンを使用しますか? なんで ？どうすれば実装できますか?
編集:あまりにも多くの質問をする必要がない場合は、実用的な例を提供してください。
29824 次
18 に答える
89
プログラミングのどの領域でステート マシンを使用しますか?
ステート マシンを使用して、限られた数の条件 (「状態」) で存在でき、一定の規則セットに従って 1 つの状態から次の状態に進む (実際のまたは論理的な) オブジェクトを表します。
ステート マシンを使用する理由
ステート マシンは、多くの場合、一連の複雑なルールと条件を表現し、さまざまな入力を処理するための非常にコンパクトな方法です。メモリが限られている組み込みデバイスにステート マシンが表示されます。適切に実装されたステート マシンは、各論理状態が物理的状態を表すため、自己文書化されます。ステート マシンは、同等の手続き型に比べてごくわずかな量のコードで具現化でき、非常に効率的に実行されます。さらに、状態の変化を制御するルールは、多くの場合、テーブルにデータとして格納できるため、簡単に維持できるコンパクトな表現が提供されます。
どうすれば実装できますか?
些細な例:
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
ノート：
この例では、わかりやすくするため
switch()に明示的なcase/状態を使用しています。break実際には、case意志は次の状態に「フォールスルー」することがよくあります。大規模なステート マシンの保守を容易にするために、それぞれで実行さ
caseれる作業を「worker」関数にカプセル化できます。の先頭で入力を取得し、while()それをワーカー関数に渡し、ワーカーの戻り値をチェックして次の状態を計算します。コンパクトにするために、全体
switch()を関数ポインターの配列に置き換えることができます。各状態は、戻り値が次の状態へのポインターである関数によって具現化されます。 警告:これにより、ステート マシンが単純化されるか、まったく保守できなくなる可能性があるため、実装は慎重に検討してください。組み込みデバイスは、壊滅的なエラーが発生した場合にのみ終了するステート マシンとして実装される場合があります。その後、ハード リセットを実行し、ステート マシンに再び入ります。
于 2008-11-01T19:46:35.790 に答える
22
すでにいくつかの素晴らしい答えがあります。少し異なる観点から、より大きな文字列でテキストを検索することを検討してください。誰かがすでに正規表現について言及していますが、これは重要ではありますが、実際には単なる特殊なケースです。
次のメソッド呼び出しを検討してください。
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 つの遷移があります。文字が一致する場合は次の状態に進みます。1 つおきの入力 (つまり、現在の位置にある 1 つおきの文字) では、ゼロに戻ります。
このわずかな再定式化には大きな利点があります。いくつかの基本的なテクニックを使用して微調整して、パフォーマンスを向上させることができるようになりました。実際、すべての高度な文字列検索アルゴリズム (当面はインデックス データ構造を無視します) は、このステート マシンの上に構築され、そのいくつかの側面を改善します。
于 2008-11-01T20:00:28.243 に答える
13
どんな仕事？
私が見たもの以外のすべてのタスクは、あらゆる種類の解析がステートマシンとして実装されることがよくあります。
なんで？
一般に、文法の解析は簡単な作業ではありません。設計段階では、解析アルゴリズムをテストするために状態図を作成するのが一般的です。それをステート マシンの実装に変換するのは、非常に簡単な作業です。
どのように？
まあ、あなたはあなたの想像力によってのみ制限されています。
私はそれが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
状態変数はありませんが、コード自体が状態を表します
于 2008-11-01T18:08:31.150 に答える
9
Stateデザイン パターンは、有限状態マシンによってオブジェクトの状態を表すオブジェクト指向の方法です。通常、そのオブジェクトの実装の論理的な複雑さを軽減するのに役立ちます (ネストされた if や多くのフラグなど)。
于 2008-11-01T18:06:28.457 に答える
6
C# を使用している場合は、イテレータ ブロックを記述するたびに、コンパイラにステート マシンを構築するように要求します (イテレータ内のどこにいるかを追跡するなど)。
于 2008-11-01T17:43:02.123 に答える
6
ほとんどのワークフローは、ステート マシンとして実装できます。たとえば、休暇申請や注文の処理などです。
.NET を使用している場合は、Windows Workflow Foundation を試してください。これを使用すると、ステート マシン ワークフローを非常に迅速に実装できます。
于 2008-11-01T17:31:26.407 に答える
4
以下は、ステート マシンのテスト済みの実際の例です。シリアル ストリームを使用しているとします (シリアル ポート、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データ
不良データにもかかわらず、ストリーム内の 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
}
}
于 2008-11-01T22:05:42.983 に答える
3
多くのデジタル ハードウェア設計には、回路の動作を指定するステート マシンの作成が含まれます。VHDL を書いている場合は、かなり出てきます。
于 2008-11-01T18:29:51.250 に答える
3
ステートマシンはどこにでもあります。ステート マシンは、受信時にメッセージを解析する必要がある通信インターフェイスで重要です。また、組み込みシステムの開発では、厳密なタイミング制約のために、1 つのタスクを複数のタスクに分割する必要が何度もありました。
于 2008-11-01T17:37:36.970 に答える
2
FSM は、複数の状態があり、刺激によって別の状態に遷移する必要があるあらゆる場所で使用されます。
（少なくとも理論的には、これがほとんどの問題を網羅していることが判明しました）
于 2008-11-01T18:33:18.060 に答える
2
正規表現は、有限状態マシン (または「有限状態オートマトン」) が活躍する別の例です。
コンパイルされた正規表現は有限状態マシンであり、正規表現が一致できる文字列のセットは、有限状態オートマトンが受け入れることができる言語 (「正規言語」と呼ばれます) とまったく同じです。
于 2008-11-01T18:24:29.857 に答える
2
スクリーン スクレイピングまたはテスト中のプロセスを実行するための QA インフラストラクチャ。(これは私の経験の特定の領域です。現在の状態をスタックにプッシュし、すべての TTY ベースのスクリーン スクレーパーで使用するための状態ハンドラー選択のさまざまな方法を使用して、最後の雇用主のために Python でステート マシン フレームワークを構築しました) . 概念モデルは、TTY アプリケーションを介して実行され、限られた数の既知の状態を通過し、古い状態に戻すことができるため、うまく適合します (ネストされたメニューの使用について考えてください)。これはリリースされました（雇用主の許可を得て）。コードを見たい場合は、Bazaarを使用してチェックアウトしてください。http://web.dyfis.net/bzr/isg_state_machine_framework/
チケット、プロセス管理、およびワークフロー システム -- チケットに、NEW、TRIAGED、IN-PROGRESS、NEEDS-QA、FAILED-QA、および VERIFIED の間の移動を決定する一連のルールがある場合 (たとえば)、シンプルなステートマシン。
小規模ですぐに証明可能な組み込みシステムの構築 - 信号機の信号は、考えられるすべての状態のリストを完全に列挙して把握する必要がある重要な例です。
パーサーとレクサーは、ステート マシンに大きく基づいています。これは、何かがストリーミングされる方法がその時点でどこにいるかに基づいて決定されるためです。
于 2008-11-01T17:38:54.580 に答える
2
私が取り組んでいる現在のシステムの例があります。株式取引システムを構築中です。注文の状態を追跡するプロセスは複雑になる可能性がありますが、注文のライフ サイクルの状態図を作成すると、新しい受信トランザクションを既存の注文に適用することがはるかに簡単になります。現在の状態から、新しいトランザクションが 20 のいずれかではなく 3 つのいずれかであることがわかっている場合、そのトランザクションを適用する際に必要な比較ははるかに少なくなります。これにより、コードがはるかに効率的になります。
于 2008-11-01T19:38:59.707 に答える
2
ここでは、それらが使用されている理由を実際に説明するものは何も見ませんでした.
実用的な目的のために、プログラマーは通常、操作の途中でスレッド/出口を強制的に返さなければならないときに、1 つ追加する必要があります。
たとえば、複数状態の HTTP 要求がある場合、サーバー コードは次のようになります。
Show form 1
process form 1
show form 2
process form 2
問題は、フォームを表示するたびに、コードがすべて論理的に一緒に流れ、同じ変数を使用している場合でも、サーバー上のスレッド全体を終了する必要があることです (ほとんどの言語で)。
コードにブレークを入れてスレッドを返すという行為は、通常、switch ステートメントで行われ、いわゆるステート マシン (非常に基本的なバージョン) を作成します。
複雑になると、どの状態が有効かを判断するのが非常に難しくなる可能性があります。次に、通常は「状態遷移表」を定義して、すべての状態遷移を記述します。
ステート マシン ライブラリを作成しました。主なコンセプトは、実際に状態遷移テーブルを直接実装できるということです。とてもいい練習でしたが、うまくいくかどうかはわかりません...
于 2008-11-18T22:36:07.090 に答える
1
有限ステート マシンは、あらゆる自然言語の形態学的解析に使用できます。
理論的には、これは、形態と構文が計算レベル間で分割されていることを意味し、一方はせいぜい有限状態であり、もう一方はせいぜい軽度の文脈依存です (したがって、他の理論モデルでは、単語から単語への依存ではなく、単語から単語への影響を考慮する必要があります)。形態素対形態素の関係)。
これは、機械翻訳や単語のグロスニングの分野で役立ちます。表向きは、構文解析や依存関係の解析など、NLP のそれほど重要でない機械学習アプリケーションのために抽出する低コストの機能です。
詳細については、Beesley と Karttunen による Finite State Morphologyと、PARC で設計された Xerox Finite State Toolkit を参照してください。
于 2008-11-01T18:08:13.913 に答える
0
良い答え。これが私の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! */
}
あなたはその考えを理解します。そして、もっと速く走る方法があるとしたら、それが何なのかわかりません。
于 2008-11-18T23:08:38.410 に答える
0
ステート ドリブン コードは、特定の種類のロジックを実装するのに適した方法です (パーサーがその例です)。たとえば、次のようないくつかの方法があります。
特定の時点で実際に実行されているコードのビットを駆動する状態 (つまり、状態は、記述しているコードの一部に暗黙的に含まれます)。 再帰降下パーサーは、このタイプのコードの良い例です。
switch ステートメントなどの条件文で何をすべきかを駆動する状態。
すべてのステート ドリブン コードが解析に使用されるわけではありません。一般的なステート マシン ジェネレーターは smcです。ステート マシンの定義を (その言語で) 吸い込み、ステート マシンのコードをさまざまな言語で吐き出します。
于 2008-11-01T19:08:11.373 に答える
0
典型的な使用例は信号機です。
実装上の注意: Java 5 の列挙型は、状態に依存する動作をカプセル化する優れた方法である抽象メソッドを持つことができます。
于 2010-08-20T09:56:14.853 に答える