c - 访谈：函数指针 vs switch case

Question

在我的面试中，我被要求为一个有 100 个状态的系统实现一个状态机，每个状态又包含 100 个事件，我回答了以下 3 种方法：

• 如果别的
• 开关盒
• 函数指针

if-else 显然不适合这样的状态机，因此主要比较的是 switch-case 与函数指针之间的比较，这是根据我的理解进行的比较：

• 速度方面两者几乎相同。
• Switch-case 不像函数指针那样模块化
• 函数指针有更多的内存开销。

有人可以确认上述理解是否正确吗？

Answer 1

函数指针方法可能有一个变体：一个包含函数指针以及其他信息的结构。所以你可以让一个函数处理几种情况。

除此之外，我认为你是对的。另外，我会考虑值得考虑的有关内存和速度的开销，但希望足够小以在最后被忽略。

Answer 2

您可以指定有关您的状态和事件的更多详细信息。假设您的状态是连续整数。那么你也能

1. 编写一个表以包含所有状态和每个状态处理函数。接收事件时，引用此表并调用相应的处理函数。

2. 对于每个状态，编写一个包含所有事件及其事件处理函数的表。在处理状态事件时查找此表。

这2个查表的时间复杂度是O(1)，空间复杂度是O(m*n)

但是，你怎么能拥有 100 种状态的 FSM 和 100 种类型的事件呢？我建议你简化你的 FSM 设计，1~100 的数字可能是一个特定事件的参数。

Answer 3

我不知道你的面试官想听什么，我希望这不是太离题，但如果我正在面试某人，我会在证明自己的框架之前知道现有框架的优缺点，特别是在那个规模上.

C++ 替代品（如果您可以使用它们，感谢 glglgl 指出您似乎想要 C）将是：

Boost.MSM 虽然速度极快，但在这种规模上是不可能的。原因是编译时间、mpl::vector/list 约束以及您将拥有一个巨大的源文件。

Boost.Statecharts 可以处理 100 个状态，但每个状态 100 个事件会最大化 mpl::vector/list 约束。就个人而言，如果我有 100 个事件处于一个状态，我会尝试将它们分组并使用自定义反应，但这显然取决于应用程序。

我看不出为什么 Qt 的状态机不会扩展那么大（如果我错了，请纠正我）但它的数量级要慢一些，所以我从不使用它。

我所知道的唯一好的 C 替代方案是：

QP 在 C 和 C++ 中可用并且可以扩展那么大，具有良好的组织并且“不仅仅是一个状态机”，因为它处理事件队列、并发和内存管理等。滚动你自己的可能会产生更好的性能（取决于你的技能和你投入了多少时间），但应该注意的是，事件的内存管理可能最终需要比状态机实现更多的优化。QP 为您做到了这一点，而且做得很好。