Проектирование высокопроизводительного State Machine на 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 классы, хотя, очевидно, они могут быть переписаны с использованием примитивов (черт, весь Переход состояние класса, очевидно, легко поместится в long).

Дело в том, что если вы, например, переместите класс Transition в простой примитив, то вы невынужден больше использовать медленные HashMap<Transition,...> коллекции Java по умолчанию: вы можете использовать библиотеки вроде Trove TLongObjectHashMap (или TLongInt ... или TLongLong, что угодно), которым принадлежит значение по умолчанию HashMapбольшие времена (библиотеки Trove в основном предоставляют карты и наборы, которые являются очень эффективными, быстрыми и маленькими, когда вы работаете с примитивами: вы не генерируете бесчисленное количество мусора или постоянную ненужную обертку вокруг примитивов, поэтому меньше GC и т. д. Если выв производительность, тогда вы действительно хотите проверить Trove ... И их предстоящая версия 3.0 на 20% быстрее, чем Trove 2.0).

Но действительно ли это полезно?Видимо, эта библиотека уже достаточно быстро.Нет никаких сомнений в том, что это можно сделать быстрее, не создавая ненужных объектов и используя коллекции, которые действительно хорошо работают, но не ясно, что это было бы желательно.

Кроме того, я почти уверен, что приведенная выше библиотекане является потокобезопасным.Конструктор State создает уникальный идентификатор, выполняя это:

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

, и этот конструктор вызывается из ... 90 разных мест!

Пример из учебника о способе не создать уникальный идентификатор в многопоточном сценарии (черт, даже сделать next_id volatile было бы недостаточно, вы хотите, скажем, AtomicInteger здесь).Я не знаю библиотеку достаточно хорошо, но эта идентификационная штуковина выглядит очень подозрительно для меня.

Answer 2

У меня есть несколько вопросов:

• Какая часть вам нужна для быстрого ввода: ввода FSA, здания FSA или исполнения FSA?

• Откуда поступает ввод FSA? Человек ставит в состояния и дуги или какой-то автоматический процесс? Реальный ввод поступает от регулярного выражения, преобразованного в FSA?

• Как часто FSA может меняться? Раз в секунду? Раз в год?

Вы знаете, что вам нужно. Помимо академических машин Тьюринга, я никогда не видел существенного конечного автомата, который бы не начинался с текстового представления, будь то регулярное выражение или структурированная программа.

В каждом случае, с которым я имел дело, предпочтительной реализацией было преобразование регулярного выражения непосредственно в простую структурированную программу и его компиляцию. Ничто не будет выполняться быстрее, чем это.