在 Java 中设计高性能状态机

performance java fsm

2022-09-04 03:46:27

我正在开始编写一个Java库来实现高性能的有限状态机。我知道那里有很多库，但我想从头开始编写自己的库，因为几乎所有的库都构建了针对一次只处理一个而优化的自动机。

我想知道在实现这样的高性能库时，SO社区中涉足状态机设计的人觉得最重要/最好的设计原则是什么。

考虑

生成的自动机通常不是巨大的。（约100-500个州）。
不过，实现应该能够扩展。
实现应实现快速转换（最小化、确定等）。
希望实现DFA，NFA，GNFA，PDA和可能的Tree Automata。如果可能的话，希望在单个界面下。
应该在内存使用和性能之间取得良好的平衡。

目前对我来说，目前关于设计的问题是：

是否应定义和的类？或者应该使用“隐藏”的内部结构。就个人而言，我觉得使用这样的类会浪费大量的内存，因为相同的信息可以以更精简的形式存储。但是，这是否能够实现更快的转换？它是否具有任何其他优点/缺点？StateSymbolTransition
在内部存储数据的最佳方式是什么？使用类似和的数据结构可以实现摊销的常量时间查找，但涉及到一个开销元素。这是最好的方法吗？将转换信息存储为原始（或非）数组似乎浪费了相当多的内存。特别是当库需要一次处理很多自动机时。不同数据结构的优缺点是什么？HashMapHashSet

我感谢任何投入。谢谢！

答案 1

那么，您希望它有多快？brics.dk/automaton 的代码确实声明了自己的状态和Transition类，显然，这些可以使用基元重写（哎呀，整个Transition类的状态显然很容易适应）。long

问题是，例如，如果你将类移动到一个原始状态，那么你就不会被迫再使用缓慢的默认Java集合：你可以使用像Trove这样的库（或者......或者，等等），它拥有默认的大时间（Trove库基本上提供了超级高效的映射和集，既快速又小，当你使用基元时：你不会生成无数的垃圾，也不会不断地不必要地包裹基元，所以更少的GC等。如果您喜欢性能，那么您确实要检查Trove...他们即将发布的3.0版本比Trove 2.0快20%）。TransitionHashMap<Transition,...>TLongObjectHashMapTLongIntTLongLongHashMap

但它真的有用吗？显然，该库已经足够快了。毫无疑问，通过不浪费地创建对象和使用实际表现良好的集合，可以更快地做到这一点，但目前还不清楚这是否可取。

除此之外，我很确定上面的库不是线程安全的。状态构造函数通过执行以下操作创建唯一 ID：

static int next_id;
.
.
.
id = next_id++;

并且该构造函数是从...90个不同的地方！

在多线程场景中不创建唯一ID的方法的教科书示例（哎呀，即使使易失性也不够，你想要，比如说，这里的AtomicInteger）。我对图书馆不够了解，但这个ID的东西对我来说看起来很可疑。next_id

答案 2

我有一些问题：

您需要快速的哪一部分，FSA的输入，FSA的构建或FSA的执行？
FSA的输入来自哪里？人类是输入状态和弧线，还是一些自动过程？实际输入是否来自转换为 FSA 的正则表达式？
FSA多久可以更改一次？每秒一次？一年一次？

您知道自己需要什么。除了学术图灵机之外，我从未见过一个重要的状态机不是从文本表示开始的，无论是作为正则表达式还是结构化程序。

在我处理过的每种情况下，首选的实现是将正则表达式直接转换为简单的结构化程序并进行编译。没有什么比这更快执行了。