Разработка высокопроизводительного конечного автомата на Java

Ну, как быстро вы хотите, чтобы это было? Код на brics.dk/automaton действительно объявляет свои собственные классы State и Transition, хотя, очевидно, их можно переписать с использованием примитивов (черт возьми, состояние всего класса Transition, очевидно, легко поместится на long).

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

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

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

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

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

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

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

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

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

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

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

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