用Java設計高性能狀態機

我正在開始編寫Java庫來實現高性能有限狀態機。 我知道這裏有很多庫，但我想從頭開始編寫自己的庫，因爲幾乎所有的庫都構造了自動優化，以便一次只處理一個庫。用Java設計高性能狀態機

我想知道SO社區中涉足狀態機設計的人員在實現像這些高性能庫時最重要/最好的設計原則。

思考

生成的自動機通常不龐大。（〜100-500州）。
雖然實施應該能夠規模。
執行應該啓用快速轉換（最小化，確定等）。
希望實現DFA，NFA，GNFA，PDA和可能的樹自動機。如果可能的話，希望在單個界面下。
內存使用和性能之間應該有一個很好的平衡。

對於目前的設計對我來說現在的問題是：

應爲State，Symbol和Transition類來定義？或者應該使用「隱藏的」內部結構。就我個人而言，我認爲使用類將會浪費大量的內存，因爲相同的信息可以以更簡潔的形式存儲。但是，這是否能夠實現更快的轉換？它是否有其他優點/缺點？
內部存儲數據的最佳方式是什麼？使用像HashMap和HashSet這樣的數據結構可以實現分攤的恆定時間查找，但是會涉及一些開銷。這是最好的方法嗎？將轉換信息存儲爲原始（或不存在）數組似乎浪費了相當多的內存。特別是當圖書館需要一次處理大量的自動機時。不同數據結構的優缺點有哪些？

我很欣賞任何輸入。謝謝！

來源

2011-03-12 Nico Huysamen

嗨，也許你可以使用我的教授實施作爲參考。它是基於DFA和NFA的開放源代碼。實施：http://www.brics.dk/automaton/性能基準：http://tusker.org/regex/regex_benchmark.html – 2011-03-12 10:57:26

@lasseespeholt - 大聲笑，我其實已經有代碼，我正在通過它。它是我發現的實際處於活躍開發階段的唯一Java庫之一。向我的教授表示感謝和問候！ – 2011-03-12 11:03:12

你有沒有想過在Drools中使用有狀態規則會話？ – 2011-03-12 12:50:27

那麼你希望它有多快？在brics.dk/automaton代碼沒有宣佈自己的國家和過渡類altough，很明顯，這些可以用原語被改寫（赫克，整個過渡類的狀態顯然會輕鬆地嵌在long）。

事情是，如果你移動，例如Transition類只是一個原始的，那麼你就不會被迫再使用慢HashMap<Transition,...>默認Java集合：您可以像使用特羅韋的TLongObjectHashMap（或TLongInt庫.. 。或TLongLong，無論如何）擁有默認HashMap大時代（Trove圖書館基本上提供了超高效的映射和集合，既快又小，當你使用基元時：你不會產生無數的垃圾，也不會產生不斷的不必要的包裝如果你進入了性能，那麼你確實想要檢查Trove ......並且他們的即將發佈的3.0版本比Trove 2.0快20％）。

但它真的有用嗎？顯然，圖書館已經足夠快了。毫無疑問，通過不浪費地創建對象和使用確實性能良好的集合，但不清楚它是否可取，可以使其更快。

除此之外，我很確定上面的庫不是線程安全的。國家構造做這將創建一個唯一的ID：

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

和構造從...... 90個不同的地方調用！的方式不

課本例如，在多線程的情況下創建一個唯一的ID（赫克，甚至使next_id揮發性是不夠的，你想要的，比方說，一個的AtomicInteger這裏）。我不知道圖書館不夠好，但這個ID thinggy看起來非常 fish to給我。

來源

2011-03-12 12:28:09 SyntaxT3rr0r

感謝您的信息，尤其是* Trove *，我一定會看看它。就速度而言，只要變速不受影響，速度越快越好。 – 2011-03-12 12:48:06

我一直在玩* Trove *。這些藏品瘋狂得很快。感謝您的鏈接！ – 2011-03-13 12:13:42

@Nico Huysamen：ahah，nice :)他們生成的方式也非常酷：他們基本上使用預處理器/代碼生成器，因爲不必爲所有基本類型複製Java代碼。 – SyntaxT3rr0r 2011-03-15 00:02:42

我有一些問題：

哪一部分你必須快，輸入FSA的，在建設FSA的，或執行FSA的？
FSA的輸入來自哪裏？人類是否置入狀態和弧線，或者是一些自動過程？真正的輸入是來自正式表達式轉換爲FSA嗎？
FSA多久可以更換一次？一秒鐘？一年一次？

你知道你需要什麼。除了學術性的圖靈機，我從來沒有見過一個重要的狀態機，它不是從文本表示開始，既可以是正則表達式也可以是結構化程序。

在我處理的每一種情況下，首選的實現是將正則表達式直接轉換爲簡單的結構化程序並編譯它。沒有什麼比這更快地執行。

來源

2011-03-12 14:11:24

1）實際上需要快速的是對自動機進行的任何轉換（確定，最小化等）。 2）由隨機發生器產生的99.9％。 3）如果你正在談論轉型，我會每年多說一次。 – 2011-03-12 21:38:14

@Nico：那麼我會做的是在最簡單的數據結構上對這些轉換算法進行原型設計。 [調整他們的現實輸入。]（http://stackoverflow.com/questions/926266/performance-optimization-strategies-of-last-resort/927773#927773）然後做第2版與任何數據結構，你現在知道是最好的。 – 2011-03-12 21:56:48

我忘了提。我不希望將正則表達式轉換爲FA（好吧，我也會這樣做，但不是最初）。當生成隨機FA時，我需要完全控制狀態數，轉換，每個狀態有多少轉換等等。只需轉換REGEX就會使該要求無效。 – 2011-03-13 08:55:39

用Java設計高性能狀態機

回答

相關問題