14

私は、高性能の有限状態マシンを実装する Java ライブラリの作成を開始しようとしています。たくさんのライブラリがあることは知っていますが、ほとんどすべてのライブラリが一度に 1 つだけを処理するように最適化されたオートマトンを構築するため、ゼロから独自のライブラリを作成したいと考えています。

ステート マシンの設計に手を出した SO コミュニティの人々が、このような高性能ライブラリの実装に関して最も重要で最良の設計原則をどのように感じているかを知りたいです。

考慮事項

  1. 生成されるオートマトンは通常、大規模ではありません。(~ 100-500 州)。
  2. ただし、実装はスケーリングできる必要があります。
  3. 実装は、高速変換(最小化、決定化など) を有効にする必要があります。
  4. DFA、NFA、GNFA、PDA、およびおそらくツリー オートマトンの実装を検討しています。可能であれば、単一のインターフェースの下でうまくいけば。
  5. メモリ使用量とパフォーマンスのバランスが取れている必要があります。

現時点でのデザインに関する現在の質問は次のとおりです。

  1. State、SymbolおよびのクラスをTransition定義する必要がありますか? または、「隠された」内部構造を使用する必要があります。個人的には、クラスをそのまま使用すると、同じ情報をより凝縮された形式で格納できるため、多くのメモリが浪費されると感じています。しかし、これはより速い変換を可能にしますか? 他に長所/短所はありますか？

  2. データを内部に保存する最良の方法は何ですか? HashMapおよびのようなデータ構造を使用するとHashSet、償却された一定時間のルックアップが可能になりますが、関連するオーバーヘッドの要素があります。これが最善の方法ですか？遷移情報をプリミティブ (またはそうでない) 配列として保存すると、かなりの量のメモリが浪費されるようです。特に、ライブラリが一度に多くのオートマトンを処理する必要がある場合。異なるデータ構造の長所と短所は何ですか?

ご意見をお待ちしております。ありがとう！

4

2 に答える 2

8

さて、あなたはそれをどれくらい速くしたいですか？brics.dk/automatonのコードは、独自のStateクラスとTransitionクラスを宣言していますが、明らかに、これらはプリミティブを使用して書き換えることができます (実際、Transitionクラス全体の状態は明らかに に簡単に適合しますlong)。

たとえば、クラスを単純なプリミティブに移動すると、遅いTransitionデフォルトのHashMap<Transition,...>Java コレクションを使用する必要がなくなりTLongObjectHashMapますTLongInt。デフォルトの大きな時間 (Trove ライブラリは、基本的に、プリミティブを操作するときに、高速かつ小型の両方で非常に効率的なマップとセットを提供します: 無数のガベージを生成したり、プリミティブを不必要にラップしたりする必要がないため、GC などが少なくなります。パフォーマンスに興味がある場合は、Trove をチェックしてください...そして、彼らの 3.0 の次のリリースは、Trove 2.0 よりも 20% 高速です)。TLongLongHashMap

しかし、それは本当に役に立ちますか？どうやら、そのライブラリはすでに十分に高速です。オブジェクトを無駄に作成せず、実際にパフォーマンスの高いコレクションを使用することで高速化できることは間違いありませんが、それが望ましいかどうかは明らかではありません。

それに加えて、上記のライブラリがスレッドセーフではないことは確かです。State コンストラクターは、次のようにして一意の ID を作成します。

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

そして、そのコンストラクターは... 90 の異なる場所から呼び出されます!

マルチスレッドのシナリオで一意の ID を作成しない方法の教科書の例(ほら、next_id 揮発性にするだけでは不十分です。たとえば、ここではAtomicIntegerが必要です)。ライブラリについてはよくわかりませんが、この ID は非常に怪しいものに見えます。

于 2011-03-12T12:28:09.273 に答える
3

いくつか質問があります:

  • FSAの入力、FSAの構築、またはFSAの実行のどの部分が高速である必要がありますか?

  • FSA の情報はどこから得られますか? 人間がステートとアークを挿入するのか、それとも何らかの自動プロセスを実行するのか? 実際の入力は、FSA に変換された正規表現から来ていますか?

  • FSA はどのくらいの頻度で変更できますか? 1秒に1回？一年に一度？

あなたはあなたが必要なものを知っています。学術的なチューリング マシンは別として、正規表現または構造化プログラムのいずれかとして、テキスト表現から開始されていない重要なステート マシンを見たことがありません。

私が対処したすべてのケースで、推奨される実装は、正規表現を単純な構造化プログラムに直接変換してコンパイルすることでした。それよりも速く実行されるものはありません。

于 2011-03-12T14:11:24.393 に答える