상태 머신에 사용
어떤 프로그래밍 영역에서 상태 머신을 사용합니까? 왜 ? 어떻게 구현할 수 있습니까?
편집 : 물어볼 것이 너무 많지 않은 경우 실용적인 예를 제공하십시오.
어떤 프로그래밍 영역에서 상태 머신을 사용합니까?
상태 머신을 사용하여 제한된 수의 조건 ( " 상태 ")에 존재할 수 있고 고정 된 규칙 집합에 따라 한 상태에서 다음 상태로 진행할 수있는 (실제 또는 논리) 객체를 나타냅니다 .
상태 머신을 사용하는 이유는 무엇입니까?
상태 머신은 복잡한 규칙 및 조건 세트를 표현하고 다양한 입력을 처리 하는 매우 간단한 방법입니다. 메모리가 제한된 임베디드 장치에서 상태 머신을 볼 수 있습니다. 잘 구현 된 상태 머신은 각 논리적 상태가 물리적 조건을 나타내므로 자체 문서화됩니다. 상태 머신은 절차 적 동등에 비해 적은 양의 코드 로 구현 될 수 있으며 매우 효율적으로 실행됩니다. 또한 상태 변경을 제어하는 규칙은 종종 테이블에 데이터로 저장되어 쉽게 유지 관리 할 수있는 간결한 표현을 제공합니다.
어떻게 구현할 수 있습니까?
간단한 예 :
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"작업자"기능으로 캡슐화 할 수 있습니다. 상단에서 입력을 가져와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
여기에서 다른 상태는 우리가 검색하는 단어의 모든 다른 위치를 직접 나타냅니다. 그래프의 각 노드에는 두 가지 전환이 있습니다. 문자가 일치하면 다음 상태로 이동합니다. 다른 모든 입력 (즉, 현재 위치의 다른 모든 문자)에 대해 0으로 돌아갑니다.
이 약간의 재구성에는 큰 이점이 있습니다. 이제 일부 기본 기술을 사용하여 더 나은 성능을 내도록 조정할 수 있습니다. 실제로 모든 고급 문자열 검색 알고리즘 (현재 인덱스 데이터 구조 할인)은이 상태 시스템을 기반으로 구축되어 일부 측면을 개선합니다.
어떤 일?
모든 작업을 제외하고 내가 본 것에서 모든 종류의 구문 분석은 자주 상태 시스템으로 구현됩니다.
왜?
문법 구문 분석은 일반적으로 간단한 작업이 아닙니다. 디자인 단계에서는 구문 분석 알고리즘을 테스트하기 위해 상태 다이어그램을 그리는 것이 일반적입니다. 이를 상태 머신 구현으로 변환하는 것은 매우 간단한 작업입니다.
어떻게?
글쎄, 당신은 당신의 상상력에 의해서만 제한됩니다.
나는 그것이 case 문과 루프로 수행되는 것을 보았다 .
레이블 및 goto 문으로 수행 한 것을 보았습니다 .
현재 상태를 나타내는 함수 포인터의 구조로 수행되는 것을 보았습니다. 상태가 변경되면 하나 이상의 함수 포인터 가 업데이트됩니다.
상태 변경은 단순히 코드의 다른 섹션에서 실행 중임을 의미하는 코드에서만 수행되는 것을 보았습니다. (상태 변수가없고 필요한 경우 중복 코드가 없습니다. 이는 매우 간단한 정렬로 입증 될 수 있으며 이는 매우 작은 데이터 세트에만 유용합니다.
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
상태 변수는 없지만 코드 자체는 상태를 나타냅니다.
상태 디자인 패턴은 유한 상태 머신을 이용하여 물체의 상태를 표현하는 객체 지향 방법. 일반적으로 해당 객체 구현의 논리적 복잡성을 줄이는 데 도움이됩니다 (중첩 된 if 's, 많은 플래그 등).
대부분의 워크 플로는 상태 시스템으로 구현할 수 있습니다. 예를 들어, 휴가 신청서 또는 주문 처리.
.NET을 사용하는 경우 Windows Workflow Foundation을 사용해보십시오. 상태 머신 워크 플로를 매우 빠르게 구현할 수 있습니다.
C #을 사용하는 경우 반복기 블록을 작성할 때마다 컴파일러에게 상태 머신을 빌드하도록 요청합니다 (반복기에서 현재 위치 추적 등).
다음은 상태 머신의 테스트되고 작동하는 예제입니다. 직렬 스트림에 있다고 가정합니다 (직렬 포트, tcp / ip 데이터 또는 파일이 일반적인 예입니다). 이 경우 동기화, 길이 및 페이로드의 세 부분으로 나눌 수있는 특정 패킷 구조를 찾고 있습니다. 세 가지 상태가 있습니다. 하나는 유휴 상태이며 동기화를 기다리고 있고, 두 번째 상태는 양호한 동기화 상태이며 다음 바이트는 길이 여야하며 세 번째 상태는 페이로드를 축적하는 것입니다.
이 예제는 순전히 하나의 버퍼 만있는 순전히 직렬입니다. 여기에 쓰여진대로 불량 바이트 또는 패킷에서 복구하여 패킷을 폐기 할 수 있지만 결국 복구하면 즉시 복구를 허용하는 슬라이딩 윈도우와 같은 다른 작업을 수행 할 수 있습니다. 이것은 부분 패킷이 짧게 끊어진 다음 새로운 완전한 패킷이 시작한다고 말한 곳입니다. 아래 코드는 이것을 감지하지 않고 전체 패킷뿐만 아니라 부분 패킷도 버리고 다음에 복구합니다. 모든 패킷을 처리해야하는 경우 슬라이딩 창을 사용하면 거기에 저장됩니다.
직렬 데이터 스트림, tcp / ip, 파일 i / o 등 항상 이런 종류의 상태 머신을 사용합니다. 또는 tcp / ip 프로토콜 자체, 이메일을 보내고, 포트를 열고, 서버가 응답을 보내고, HELO를 보내고, 서버가 패킷을 보내고, 패킷을 보내고, 응답을 기다리고, 등등. 본질적으로 그 경우와 아래의 경우에 당신은 그 다음 바이트 / 패킷이 들어올 때까지 기다릴 수 있습니다. 당신이 무엇을 기다리고 있었는지 기억하기 위해, 또한 당신이 사용할 수있는 것을 기다리는 코드를 재사용하기 위해 상태 변수. 상태 머신이 논리에서 사용되는 것과 같은 방식입니다 (다음 시계를 기다리는 중, 무엇을 기다리고 있었는지).
논리와 마찬가지로 각 상태에 대해 다른 작업을 수행 할 수 있습니다.이 경우 동기화 패턴이 좋은 경우 오프셋을 내 저장소로 재설정하고 체크섬 누산기를 재설정합니다. 패킷 길이 상태는 정상적인 제어 경로를 중단하려는 경우를 보여줍니다. 전부는 아닙니다. 사실 많은 상태 머신이 정상 경로 내에서 점프하거나 루프를 돌 수 있습니다. 아래의 것은 거의 선형입니다.
이것이 유용하고 상태 머신이 소프트웨어에서 더 많이 사용되기를 바랍니다.
테스트 데이터에는 상태 머신이 복구하는 의도적 인 문제가 있습니다. 첫 번째 양호한 패킷, 잘못된 체크섬이있는 패킷 및 유효하지 않은 길이의 패킷 이후에 일부 가비지 데이터가 있습니다. 내 결과는 다음과 같습니다.
좋은 패킷 : FA0712345678EB 잘못된 동기화 패턴 0x12 잘못된 동기화 패턴 0x34 잘못된 동기화 패턴 0x56 체크섬 오류 0xBF 잘못된 패킷 길이 0 잘못된 동기화 패턴 0x12 잘못된 동기화 패턴 0x34 잘못된 동기화 패턴 0x56 잘못된 동기화 패턴 0x78 잘못된 동기화 패턴 0xEB 좋은 패킷 : FA081234567800EA 더 이상 테스트 없음 데이터
잘못된 데이터에도 불구하고 스트림에서 두 개의 양호한 패킷이 추출되었습니다. 그리고 잘못된 데이터가 감지되고 처리되었습니다.
#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 infrastructure, intended to screen-scrape or otherwise run through a process under test. (This is my particular area of experience; I built a state machine framework in Python for my last employer with support for pushing the current state onto a stack and using various methods of state handler selection for use in all our TTY-based screen scrapers). The conceptual model fits well, as running through a TTY application, it goes through a limited number of known states, and can be moved back into old ones (think about using a nested menu). This has been released (with said employer's permission); use Bazaar to check out http://web.dyfis.net/bzr/isg_state_machine_framework/ if you want to see the code.
Ticket-, process-management and workflow systems -- if your ticket has a set of rules determining its movement between NEW, TRIAGED, IN-PROGRESS, NEEDS-QA, FAILED-QA and VERIFIED (for example), you've got a simple state machine.
Building small, readily provable embedded systems -- traffic light signaling is a key example where the list of all possible states has to be fully enumerated and known.
Parsers and lexers are heavily state-machine based, because the way something streaming in is determined is based on where you're at at the time.
A lot of digital hardware design involves creating state machines to specify the behaviour of your circuits. It comes up quite a bit if you're writing VHDL.
A FSM is used everywhere you have multiple states and need to transition to a different state on stimulus.
(turns out that this encompasses most problems, at least theoretically)
Regular expressions are another example of where finite state machines (or "finite state automata") come into play.
A compiled regexp is a finite state machine, and the sets of strings that regular expressions can match are exactly the languages that finite state automata can accept (called "regular languages").
I didn't see anything here that actually explained the reason I see them used.
For practical purposes, a programmer usually has to add one when he is forced to return a thread/exit right in the middle of an operation.
For instance, if you have a multi-state HTTP request, you might have server code that looks like this:
Show form 1
process form 1
show form 2
process form 2
The thing is, every time you show a form, you have to quit out of your entire thread on the server (in most languages), even if your code all flows together logically and uses the same variables.
The act of putting a break in the code and returning the thread is usually done with a switch statement and creates what is called a state machine (Very Basic Version).
As you get more complex, it can get really difficult to figure out what states are valid. People usually then define a "State Transition Table" to describe all the state transitions.
I wrote a state machine library, the main concept being that you can actually implement your state transition table directly. It was a really neat exercise, not sure how well it's going to go over though...
Finite state machines can be used for morphological parsing in any natural language.
Theoretically, this means that morphology and syntax are split up between computational levels, one being at most finite-state, and the other being at most mildly context sensitive (thus the need for other theoretical models to account for word-to-word rather than morpheme-to-morpheme relationships).
This can be useful in the area of machine translation and word glossing. Ostensibly, they're low-cost features to extract for less trivial machine learning applications in NLP, such as syntactic or dependency parsing.
If you're interested in learning more, you can check out Finite State Morphology by Beesley and Karttunen, and the Xerox Finite State Toolkit they designed at PARC.
I have an example from a current system I'm working on. I'm in the process of building a stock trading system. The process of tracking the state of an order can be complex, but if you build a state diagram for the life cycle of an order it makes applying new incoming transactions to the existing order much simpler. There are many fewer comparisons necessary in applying that transaction if you know from its current state that the new transaction can only be one of three things rather than one of 20 things. It makes the code much more efficient.
State driven code is a good way to implement certain types of logic (parsers being an example). It can be done in several ways, for example:
State driving which bit of code is actually being executed at a given point (i.e. the state is implicit in the piece of code you are writing). Recursive descent parsers are a good example of this type of code.
State driving what to do in a conditional such as a switch statement.
Explicit state machines such as those generated by parser generating tools such as Lex and Yacc.
Not all state driven code is used for parsing. A general state machine generator is smc. It inhales a definition of a state machine (in its language) and it will spit out code for the state machine in a variety of languages.
Good answers. Here's my 2 cents. Finite State Machines are a theoretical idea that can be implemented multiple different ways, such as a table, or as a while-switch (but don't tell anybody it's a way of saying goto horrors). It is a theorem that any FSM corresponds to a regular expression, and vice versa. Since a regular expression corresponds to a structured program, you can sometimes just write a structured program to implement your FSM. For example, a simple parser of numbers could be written along the lines of:
/* implement dd*[.d*] */
if (isdigit(*p)){
while(isdigit(*p)) p++;
if (*p=='.'){
p++;
while(isdigit(*p)) p++;
}
/* got it! */
}
You get the idea. And, if there's a way that runs faster, I don't know what it is.
A typical use case is traffic lights.
On an implementation note: Java 5's enums can have abstract methods, which is an excellent way to encapsulate state-dependent behavior.
참고URL : https://stackoverflow.com/questions/255797/uses-for-state-machines
'Programing' 카테고리의 다른 글
| PHP는 명령 줄에서 입력을 기다립니다. (0) | 2020.11.17 |
|---|---|
| AngularJ는 컨트롤러 ($ scope)에서 양식 개체에 액세스 할 수 없습니다. (0) | 2020.11.17 |
| 단위 테스트 ASP.NET DataAnnotations 유효성 검사 (0) | 2020.11.17 |
| jQuery.ready에 정의 된 함수를 전역 적으로 사용하려면 어떻게해야합니까? (0) | 2020.11.17 |
| 객체 내에서 objc_setAssociatedObject / objc_getAssociatedObject를 어떻게 사용합니까? (0) | 2020.11.17 |