14

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

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

注意事项

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

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

  1. 应该定义State,Symbol和的类吗？Transition或者应该使用“隐藏”的内部结构。就我个人而言，我觉得像这样使用类会浪费大量内存，因为相同的信息可以以更简洁的形式存储。但是，这是否可以实现更快的转换？它还有其他优点/缺点吗？

  2. 在内部存储数据的最佳方式是什么？HashMap使用类似和的数据结构HashSet可以实现分摊的常数时间查找，但会涉及到一个开销元素。这是最好的方法吗？将转换信息存储为原始（或非）数组似乎会浪费大量内存。尤其是当库需要一次处理大量自动机时。不同数据结构的优缺点是什么？

我很感激任何意见。谢谢！

4

2 回答 2

8

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

问题是，例如，如果您将类移动为简单的原语，那么Transition您将不再被迫使用缓慢的默认HashMap<Transition,...>Java 集合：您可以使用拥有默认大时代（当您使用原语时，Trove 库基本上提供了超级高效的地图和集合，既快速又小：您不会产生无数垃圾，也不会不断不必要地环绕原语，因此减少 GC 等。如果您重新进入性能，那么你确实想检查 Trove...他们即将发布的 3.0 版本比 Trove 2.0 快 20%）。TLongObjectHashMapTLongIntTLongLongHashMap

但它真的有用吗？显然这个库已经足够快了。毫无疑问，通过不浪费地创建对象和使用确实表现良好的集合，它可以变得更快，但尚不清楚它是否是可取的。

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

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

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

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

于 2011-03-12T12:28:09.273 回答
3

我有一些疑问：

  • 哪个部分需要快，FSA的输入，FSA的搭建，还是FSA的执行？

  • FSA 的输入从何而来？人类是否会设置状态和弧线，或一些自动过程？真正的输入是否来自转换为 FSA 的正则表达式？

  • FSA 多久可以更改一次？一秒钟一次？一年一次？

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

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

于 2011-03-12T14:11:24.393 回答