用Java设计高性能状态机

Question

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

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

注意事项

1. 生成的自动机通常不是很大的.(约100-500州).
2. 实现应该能够扩展.
3. 实现应该能够实现快速转换(最小化,确定等).
4. 希望实施DFA,NFA,GNFA,PDA和可能的Tree Automata.希望在可能的情况下在单一界面下.
5. 应该在内存使用和性能之间取得良好的平衡.

目前关于设计的当前问题是:

1. 应该上课State,Symbol并Transition定义？或者应该使用"隐藏的"内部结构.我个人认为使用类本会浪费大量内存,因为相同的信息可以以更加浓缩的形式存储.但是,这是否可以实现更快的转换？它是否有任何其他优点/缺点？

2. 在内部存储数据的最佳方法是什么？使用类似的数据结构HashMap并HashSet启用分摊的常量时间查找,但是存在涉及的开销元素.这是最好的方法吗？将转换信息存储为原始(或非)数组似乎浪费了相当多的内存.特别是当库需要一次处理大量自动机时.不同数据结构的优缺点是什么？

我很感激任何意见.谢谢!

Answer 1

那么你想要多快？brics.dk/automaton中的代码确实声明了自己的State和Transition类,显然,这些可以使用原语重写(哎呀,整个Transition类的状态显然很容易适合a long).

事实上,如果你将Transition类移动到简单的原语,那么你就不会再被迫使用缓慢的HashMap<Transition,...>默认Java集合了:你可以使用像Trove这样的库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看起来非常可疑.