Добрый день. У меня есть детерминированный полный конечный автомат. Мне нужно

Question

Добрый день. У меня есть детерминированный полный конечный автомат. Мне нужно

с помощью этого автомата читать входную последовательность символов, получаемых из итератора.

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

Это решение, на первый взгляд, является избыточным с точки зрения производительности. Поскольку в каждый следующий момент, зная состояние в котором мы находимся, нам нужно сравнивать только символы алфавита для определения следующего перехода из данного состояния, а не сравнивать по всем парам вида (<произвольное состояние>, <символ алфавита>).

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

В Расте нет оператора goto, но есть циклы с метками.

В связи с этим у меня есть два вопроса:

1. На ваш взгляд, насколько разумным была бы такая оптимизация вообще?
2. Как всё-таки можно организовать систему безусловных переходов по меткам?

#backend #embedded #programming #russian #rust

0

08.06.2022

2 ответов

25 просмотров

Traveller Kolsky

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

0

08.06.2022

Денис Артемов · Accepted Answer

Денис Артемов

А в чём проблема-то? Проседает производительность?

0

08.06.2022

172 похожих чатов

Добрый день. У меня есть детерминированный полный конечный автомат. Мне нужно

2 ответов

Похожие вопросы