インタビュー中に、各状態に 100 のイベントがある 100 の状態を持つシステムの状態マシンを実装するように求められました。私は次の 3 つのアプローチに答えました。
if-else は明らかにそのようなステート マシンには適していないため、主な比較はスイッチ ケースと関数ポインターの間でした。私の理解による比較は次のとおりです。
上記の理解が正しいかどうか誰かが確認できますか?
関数ポインターのアプローチには、関数ポインターと他の情報を含む構造体という別の方法があるかもしれません。したがって、1 つの関数に複数のケースを処理させることができます。
これに加えて、私はあなたが正しいと思います。さらに、メモリと速度に関するオーバーヘッドを考慮する価値はあると思いますが、最終的には無視できるほど小さいことを願っています。
状態とイベントに関する詳細を指定できます。あなたの状態が連続整数であると仮定します。その後、次のことができます
すべての状態と状態ごとのハンドラー関数を含むテーブルを作成します。イベント受信時はこのテーブルを参照し、対応するハンドラ関数を呼び出してください。
状態ごとに、すべてのイベントとそのイベント ハンドラー関数を含むテーブルを作成します。状態のイベントを処理するときに、このテーブルを参照してください。
これら 2 つのテーブルを検索する時間の複雑さは O(1) であり、空間の複雑さは O(m*n) です。
しかし、どうすれば 100 の状態を持つ FSM と 100 の種類を持つイベントを持つことができるのでしょうか? FSM の設計を簡素化することをお勧めします。1 ～ 100 の数値は、特定のイベントのパラメーターである可能性があります。
インタビュアーが何を聞きたかったのかわかりませんが、これがあまり話題から外れていないことを願っていますが、誰かにインタビューする場合、特にその規模で独自のフレームワークを展開することを正当化する前に、既存のフレームワークの長所と短所を知るためのポイントを与えます.
C++ の代替 (使用できる場合は、C が必要なようであることを指摘してくれた glglgl に感謝します) は次のようになります。
Boost.MSM は非常に高速ですが、その規模では問題外です。理由は、コンパイル時間、mpl::vector/list の制約、および 1 つの巨大なソース ファイルがあるためです。
Boost.Statecharts は 100 の状態で機能しますが、状態ごとに 100 のイベントがあると、mpl::vector/list の制約が最大になります。個人的には、1 つの状態に 100 個のイベントがある場合、とにかくそれらをグループ化し、カスタム リアクションを使用しようとしますが、それは明らかにアプリケーションに依存します。
Qt のステート マシンがそれほど大きく拡張されない理由はわかりませんが (間違っている場合は訂正してください)、桁違いに遅いので使用しません。
私が知っている唯一の良いCの代替案は次のとおりです。
QP は C および C++ で利用可能であり、その規模を拡張でき、優れた組織を持ち、イベント キュー、同時実行性、およびメモリ管理などを処理するという点で「ステート マシン以上」です。ただし、イベントのメモリ管理には、それ自体のステート マシンの実装よりも多くの最適化が必要になる可能性があることに注意してください。QP はこれを非常にうまく行います。