1. 首页
  2. 问题
  3. 用Java设计高性能状态机
一尘不染

用Java设计高性能状态机

java

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

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

注意事项

  1. 生成的自动机通常并不庞大。（〜100-500个州）。
  2. 该实现应该能够 扩展 。
  3. 该实现应支持 快速转换 （最小化，确定化等）。
  4. 希望实施DFA，NFA，GNFA，PDA以及可能的Tree Automata。如果可能，希望在单个界面下。
  5. 应该在内存使用和性能之间取得良好的平衡。

目前，有关我的设计方面的问题是：

  1. 如果班State，Symbol和Transition界定？还是应该使用“隐藏的”内部结构。我个人认为使用此类本身会浪费大量内存，因为相同的信息可以以更简洁的形式存储。但是，这是否可以加快转换速度？它还有其他优点/缺点吗？

  2. 在内部存储数据的最佳方法是什么？使用类似的数据结构HashMap并HashSet启用分期的固定时间查找，但其中涉及一些开销。这是最好的方法吗？将过渡信息存储为原始（或不存储）数组似乎浪费了很多内存。尤其是当图书馆需要一次处理大量自动机时。不同数据结构的优缺点是什么？

感谢您的投入。谢谢！


阅读 760

收藏
2020-12-03

共1个答案

一尘不染

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

事情是，如果你移动，例如，Transition类只是一个原始的，那么你就不会被迫再使用缓慢的HashMap<Transition,...>默认Java集合：您可以使用库，例如特罗韦的TLongObjectHashMap（或者TLongInt…或者TLongLong，无论）这
拥有
的默认的HashMap重要时间（在使用基元时，Trove库基本上提供了高效且快速的小型映射和集：您不会生成无数的垃圾，也不会不断地在基元周围进行不必要的包装，因此不会减少GC等。重新进入性能，那么您确实要检查Trove
…并且即将推出的3.0版本比Trove 2.0快20％。

但这真的有用吗？显然，该库已经足够快了。毫无疑问，可以通过不浪费创建对象并使用实际运行良好的集合来提高它的速度，但尚不清楚这是否可取。

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

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

然后从90个不同的地方调用该构造函数！

在多线程方案中 不 创建唯一ID 的方法的教科书示例（哎呀，甚至使next_id volatile 都不够，您想要在这里使用
AtomicInteger ）。我对图书馆不太了解，但是这个ID东西对我来说似乎 非常 可疑。

2020-12-03