用Java设计高性能状态机
我正在开始编写Java库来实现高性能的有限状态机。 我知道那里有很多库，但是我想从头开始编写自己的库，因为几乎所有的库都构建了自动机，这些自动机被优化为一次只能处理一个。
我想知道SO社区中涉及状态机设计的人员在实现像这样的高性能库时最重要/最好的设计原则是什么。
注意事项
- 生成的自动机通常不是很大的。 （~100-500州）。
- 实现应该能够扩展 。
- 实现应该能够实现快速转换 （最小化，确定等）。
- 希望实施DFA，NFA，GNFA，PDA和可能的Tree Automata。 希望在可能的情况下在单一界面下。
- 应该在内存使用和性能之间取得良好的平衡。
目前关于设计的当前问题是：
-
应该定义
State，Symbol和Transition类吗？ 或者应该使用“隐藏的”内部结构。 就个人而言，我觉得使用类本会浪费大量内存，因为相同的信息可以以更加浓缩的forms存储。 但是，这是否可以实现更快的转换？ 它是否有任何其他优点/缺点？ -
在内部存储数据的最佳方法是什么？ 使用像
HashMap和HashSet这样的数据结构可以实现分摊的常量时间查找，但是存在涉及开销的元素。 这是最好的方法吗？ 将转换信息存储为原始（或非）数组似乎浪费了相当多的内存。 特别是当库需要一次处理很多自动机时。 不同数据结构的优缺点是什么？
我很感激任何意见。 谢谢！
那么你想要多快？ brics.dk/automaton中的代码确实声明了自己的State和Transition类，显然，这些可以使用原语重写（哎呀，整个Transition类的状态显然很容易适合long ）。
事实上，如果你将Transition类简单地移动到一个原语，那么你就不必再使用慢速HashMap默认的Java集合：你可以使用像Trove的TLongObjectHashMap这样的TLongObjectHashMap （或者拥有默认HashMap TLongInt …或者TLongLong （无论如何）（Trove库基本上提供了超高效的地图和集合，无论是快速还是小，当你使用原语时：你不会产生无数垃圾也不会产生常数不必要地包裹原语，所以减少GC等。如果你进入性能，那么你确实要检查Trove ……而他们的3.0即将推出的版本比Trove 2.0快20％）。
但它真的有用吗？ 显然，图书馆已经足够快了。 毫无疑问，通过不浪费地创建对象并使用实际上表现良好的集合可以更快地制作它，但不清楚它是否可取。
除此之外，我很确定上面的库不是线程安全的。 State构造函数通过执行以下操作创建唯一ID：
static int next_id; . . . id = next_id++;
而那个构造函数是从… 90个不同的地方调用的！
一个不在multithreading场景中创建唯一ID的方法的教科书示例（ next_id ，即使将next_id volatile也不够，你想要这里的AtomicInteger ）。 我不太了解这个图书馆，但这个ID看起来非常可疑。
我有一些问题：
-
您需要快速完成哪些部分，FSA的输入 ，FSA的建立或FSA的执行 ？
-
FSA的输入来自哪里？ 人类投入了状态和弧线，还是一些自动过程？ 真正的输入是否来自转换为FSA的正则表达式？
-
FSA多久可以改变一次？ 一秒一次？ 一年一次？
你知道你需要什么。 除了学术图灵机，我从来没有见过一个重要的状态机，它不是从文本表示开始，无论是作为正则表达式还是结构化程序。
在我处理过的每一个案例中，首选实现是将正则表达式直接转换为简单的结构化程序并进行编译。 什么都不会比那更快地执行。