Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: 1 2      [все]
 Задача оптимизации  [new]
_дух_
Member

Откуда:
Сообщений: 20
Есть простая и специфичная виртуалная машина (Для проверки регекспов). Она умеет только простые операции, безусловный переход и операцию деления процесса. И есть некоторый код для этой машины, который имеет одну точку входа и несколко точек выхода. Если один из процессов достигает любой точки выхода то все процессы заверщаются. Заранее известно что код может быть не оптимальным. Задача этот код оптимизировать. Очевидно что если некоторые команды никогда не выполняются их можно удалить. Но естъ ещё бесконечные циклы. Так-как они не видут к результату их тоже нужно оптимизировать.
Задачу можно рассматривать на ориентированном графе с заданной точкой старта и несколькими точками заверщения. Нужно наити все пути ведущие из точки начала в любую точку заверщения. Все отрези которые не входят в эти "пути" можно исключить.
Вот собственно ищю идею быстрого алгоритма.
13 окт 21, 17:05    [22383241]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6645
_дух_,

всё что касается регулярных выражений известно давно и исследовано вдоль и поперёк (если там действительно регулярки)
темы называются регулярные языки, конечные автоматы
при правильном подходе асимптотика проверки любой регулярки пропорциональна длине входной строки

группу регулярок довольно легко можно объединить в 1, тут всё от задачи зависит

используемые для оптимизации алгоритмы:
переход от НКА к ДКА - Subset construction
для минимизации ДКА, как вариант, есть простой алгоритм - Алгоритм Бржозовско
13 окт 21, 18:41    [22383298]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
mayton
Member

Откуда: loopback
Сообщений: 52996
А почему там - бесконечные циклы?
13 окт 21, 18:52    [22383303]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
_дух_
Member

Откуда:
Сообщений: 20
kealon(Ruslan),

Я не вижу как алгоритм минимизации ДКА применим к изложенной задаче. Задачи то совершенно разные.
13 окт 21, 20:54    [22383348]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6645
_дух_,

вот, для начала, и сформулируйте задачу

автор
И есть некоторый код для этой машины, который имеет одну точку входа и несколко точек выхода.

есть State, есть множественные переходы, если предположить что есть ещё условия переходов, то если мой хрустальный шар не сломался, то это и есть НКА
а значит из него можно сделать ДКА

Сообщение было отредактировано: 13 окт 21, 21:01
13 окт 21, 21:10    [22383350]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6645
_дух_,

если действия вашей "машины" можно описать наподобие этого кода
то ваш "специфичный код" и есть скомпилированные регулярки
13 окт 21, 21:24    [22383353]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
_дух_
Member

Откуда:
Сообщений: 20
kealon(Ruslan)
_дух_,
вот, для начала, и сформулируйте задачу


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

Вот моя задача. Всё остальное - так немного лирики.
13 окт 21, 22:53    [22383373]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6645
_дух_,

Алгоритм Бржозовско это и есть то, что доктор прописал
13 окт 21, 23:12    [22383380]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
White Owl
Member

Откуда:
Сообщений: 12906
[quot _дух_#22383373]
Задачу можно рассматривать на ориентированном графе с заданной точкой старта и несколькими точками заверщения.
У графов не бывает точек старта и точек завершения. Вообще не бывает.
То о чем ты думаешь это не граф а "конечный автомат". В графическом выражении конечный автомат похож на граф, но только похож.
Регулярные выражения можно с легкостью представить в виде "недетерменированного конечного автомата" (НКА), любой НКА можно превратить в "детерминированный конечный автомат" (ДКА). На любой ДКА можно натравить алгоритмы Мили, Мура или уже упомянутого Бржозовского.

_дух_
Вот моя задача. Всё остальное - так немного лирики.
В "лирике" часто и кроется решение задачи. Не надо ее забывать.
14 окт 21, 03:43    [22383414]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
_дух_
Member

Откуда:
Сообщений: 20
White Owl
пропущено...
У графов не бывает точек старта и точек завершения. Вообще не бывает.

Но нам ничто не мешает взять граф и сказать что одна из вершин точка старта или начала пути и также задать набор вершин - точек завершения или конечных точек пути. Такая постановка задачи корекектна.
14 окт 21, 08:14    [22383440]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
_дух_
Member

Откуда:
Сообщений: 20
kealon(Ruslan)
_дух_,

Алгоритм Бржозовско это и есть то, что доктор прописал

К такому доктору я бы не обращался. Это разные задачи.
Давайте на простом примере покажу.
Пусть граф задан таким образом:

[[1],[2],[3],FINISH]


Какой результат нам даст Алгоритм Бржозовско?
14 окт 21, 08:23    [22383444]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6645
_дух_,

тынц - оч хорошая статья, на пальцах, так сказать
14 окт 21, 08:24    [22383445]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
_дух_
Member

Откуда:
Сообщений: 20
kealon(Ruslan),

Я рад что вы знаете методы оптимизации ДКА но я повторяю - это не моя задача.
во первых не это не ДКА, во вторых мне ненужно уменьшать количество состояний.
14 окт 21, 09:56    [22383476]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
Имя пользователя1
Member

Откуда:
Сообщений: 779
_дух_
мне ненужно уменьшать количество состояний.
после выкидывания части ребер (переходов), некоторые вершины (состояния) могут быть недостижимы из старта. Их всё равно нужно оставить?
14 окт 21, 10:07    [22383482]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
_дух_
Member

Откуда:
Сообщений: 20
Имя пользователя1
после выкидывания части ребер (переходов), некоторые вершины (состояния) могут быть недостижимы из старта. Их всё равно нужно оставить?

Рёбра - это действия виртуальной машины. Состояния - не материальны. Просто число.
14 окт 21, 10:21    [22383488]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
_дух_
Member

Откуда:
Сообщений: 20
Имя пользователя1
_дух_
мне ненужно уменьшать количество состояний.
после выкидывания части ребер (переходов), некоторые вершины (состояния) могут быть недостижимы из старта. Их всё равно нужно оставить?

В моём случае "выкидывание рёбер" - это уже последствия. Достаточно наити все пути ведущие из точки начала в любую точку завершения.
14 окт 21, 10:34    [22383497]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
mayton
Member

Откуда: loopback
Сообщений: 52996
_дух_
Имя пользователя1
пропущено...
после выкидывания части ребер (переходов), некоторые вершины (состояния) могут быть недостижимы из старта. Их всё равно нужно оставить?

В моём случае "выкидывание рёбер" - это уже последствия. Достаточно наити все пути ведущие из точки начала в любую точку завершения.

Вроде стандартный алгоритм. Поиск минимального дерева. Или остовного.
14 окт 21, 12:50    [22383584]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6645
_дух_
kealon(Ruslan)
_дух_,

Алгоритм Бржозовско это и есть то, что доктор прописал

К такому доктору я бы не обращался. Это разные задачи.
Давайте на простом примере покажу.
Пусть граф задан таким образом:

[[1],[2],[3],FINISH]


Какой результат нам даст Алгоритм Бржозовско?

FINISH и даст, переходы то у вас безусловные
а какой результат вы ожидаете?
14 окт 21, 13:25    [22383615]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
_дух_
Member

Откуда:
Сообщений: 20
kealon(Ruslan),

я как бы издалека намекал что это граф - не автомат.
14 окт 21, 13:52    [22383639]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 54791
А переходы между состояниями автомата - граф.
14 окт 21, 13:54    [22383641]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6645
_дух_
kealon(Ruslan),

я как бы издалека намекал что это граф - не автомат.
ваши намёки интереса не представляют, вы же доктору не говорите "догодайся сам, а я посижу" ? вот на форуме тоже самое.
мы пока от вас даже внятного условия задачи не видим, как же вам помочь то?
14 окт 21, 15:05    [22383696]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
_дух_
Member

Откуда:
Сообщений: 20
kealon(Ruslan)
мы пока от вас даже внятного условия задачи не видим, как же вам помочь то?


Для вас третий раз повторю:
Задачу можно рассматривать на ориентированном графе с заданной точкой старта и несколькими точками заверщения. Нужно наити все пути ведущие из точки начала в любую точку завершения.

Если вам что-то непонятно задавайте вопрос.
Подозреваю студент до вопроса не созрел но про вшей билет выучил.
14 окт 21, 15:52    [22383747]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6645
_дух_,

я вам и задал вопрос

22383615

а ответ на ваш вопрос тот же самый
22383380
только чуть упростить его: "отжиг" с выходов, потом отжиг со входа по оставшемся переходам
14 окт 21, 16:05    [22383755]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 54791
_дух_
Задачу можно рассматривать на ориентированном графе с заданной точкой старта и несколькими точками заверщения. Нужно наити все пути ведущие из точки начала в любую точку завершения.

Форд-Фалкерсон и его модификации. Ищет кратчайшие пути из заданной вершины графа в любую другую. Рекомендую.
15 окт 21, 14:02    [22384222]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
Имя пользователя1
Member

Откуда:
Сообщений: 779
Dimitry Sibiryakov
Ищет кратчайшие пути из заданной вершины графа в любую другую.
как я понял, нужны все пути в заданные вершины, а не только кратчайшие.
15 окт 21, 15:42    [22384260]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
exp98
Member

Откуда:
Сообщений: 3192
Если все нужны, тогда и циклы нужны, и комбинации циклов. А так да, алгоритмов дофига, и зачем было здесь спрашивать?
15 окт 21, 17:03    [22384279]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 54791
Имя пользователя1
как я понял, нужны все пути в заданные вершины, а не только кратчайшие.

Тогда простая рекурсия. Но она зациклится есть есть хоть одно кольцо.
16 окт 21, 13:56    [22384556]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
Верблюд
Member

Откуда: Яженичеловек!!!
Сообщений: 65074
Имя пользователя1
Dimitry Sibiryakov
Ищет кратчайшие пути из заданной вершины графа в любую другую.
как я понял, нужны все пути в заданные вершины, а не только кратчайшие.


"всех" путей может оказаться бесконечно много.
16 окт 21, 16:01    [22384585]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
exp98
Member

Откуда:
Сообщений: 3192
Если хороводы кругами не не накручивать, бесконечностей не будет.
16 окт 21, 22:21    [22384636]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
Верблюд
Member

Откуда: Яженичеловек!!!
Сообщений: 65074
exp98
Если хороводы кругами не не накручивать, бесконечностей не будет.


Тогда в задаче следует указать "не накручивая хороводы". Иначе непонятно будет чего хотят.
17 окт 21, 00:09    [22384666]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
_дух_
Member

Откуда:
Сообщений: 20
Сделал примерно так:
Поиск в глубину запоминает альтернативные вершины для продолжения поиска в стеке.
При прохождении вершины в ней запоминается глубина стека.
На каждом шаге сначала проверяем это значение для новой вершины - В.
Если вершину не посещали - запоминаем глубину и продолжаем.
Иначе просматриваем все вершины и заменяем значение в них на мин(В, значение вершины) (**)
И специальные значения если через вершину (не) проходит путь ведущий к выходу.

Проблематично как мне видится действие (**).
Просмотр всех N вершин в худшем случае выполнится N раз. В итоге O(N^2)
Можно ли сделать быстрее?
18 окт 21, 09:12    [22384882]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
_дух_
Member

Откуда:
Сообщений: 20
В коде нагляднее.

+

void OptimizeCode(int startNode)
{
	const int MATCH_TRACE = -1;
	const int IMPASSE_TRACE = -2;

	var tracemap = new int[_codeSize];
	int branch = 1;
	Stack<int> stack = null;

	int node = startNode;
	while (node < _codeSize)
	{
		int resolution = tracemap[node];
		if (resolution != 0)
		{
			if (resolution == branch)
				resolution = IMPASSE_TRACE;
			else if (IMPASSE_TRACE != resolution)
				branch = resolution;
		}
		else
		{
			tracemap[node] = branch;
			var inst = _code[node];
			switch (inst.OpCode)
			{
				case OPCODE_EXIT:
					resolution = branch = MATCH_TRACE;
					break;

				case OPCODE_HALT:
					resolution = IMPASSE_TRACE;
					break;
					
				case OPCODE_JUMP:
					node = target;
					continue;

				case OPCODE_SPLIT:
					if (stack == null)
						stack = new Stack<int>();
					stack.Push(inst.Target);
					branch = 1 + stack.Count;
					node += 1;
					continue;

				default:
					node += 1;
					continue;
			}
		}
		for (int i = tracemap.Length; --i >= 0;)
			if (tracemap[i] != 0 && branch <= tracemap[i])
				tracemap[i] = resolution;
		if (stack == null || stack.Count == 0)
			break;
		branch = stack.Count;
		node = stack.Pop();
	}
	// Here more ....
	
}

18 окт 21, 09:25    [22384885]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6645
_дух_,

вот вы упёртый, почитайте описание Алгоритм Бржозовского, это всего лишь модифицированный алгоритм распрастранения

в вашем случае он выполняется за O(N)
выполняется он максимум в 4 цикла, каждый из которых имеет асимптотику O(N)

1 цикл - ищите все переходы в ассоциативный массив <куда, откуда>
2 цикл - на старте помещаете в стек\очередь все результатные состояния и с помощью ассоциативного массива из первого цикла "обжигаете" пока стек не исчезнет, на выходе должны получиться "обожжённые пути"
3 цикл : из "обожённых" путей со второго цикла, нужно составить ассоциативный массив <откуда, куда> (его можно заполнить и во втором цикле)
4 цикл фактически тот же алгоритм что и во 2-м, но уже с использованием мапы<откуда, куда> от точек старта

PS: множества <куда, откуда> и <откуда, куда> естественно MultiMap (т.е. позволяют хранить несколько ключей)
18 окт 21, 10:15    [22384901]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
_дух_
Member

Откуда:
Сообщений: 20
kealon(Ruslan),

Для начала вы описываете здесь какой-то "отжигной" алоритм, но не алгоритм Бржозовского. Или я чего-то не вижу?

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


Уже это уже противоречит вашему утверждению про "всего 4 цикла".

Ну и в заключениу к вашему "отжигному" алгоритму - достижимые конечные состояния нужно сначала найти. Это 5 цикл O(N)
18 окт 21, 11:23    [22384938]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
_дух_
Member

Откуда:
Сообщений: 20
kealon(Ruslan),

про Алгоритм Бржозовского - применим для НКА и ДКА.
Из вики про КА
При работе на вход КА поступают последовательно входные воздействия, а на выходе КА формирует выходные сигналы.

В моей задаче нету входного сигнала следователно это не КА, следовательно методы для ДКА и НКА не применимы.
18 окт 21, 11:47    [22384947]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
_дух_
Member

Откуда:
Сообщений: 20
kealon(Ruslan)
_дух_,
вот вы упёртый


вы можете вести диалог на уровне, без оскорблений и перехода на личности?
18 окт 21, 12:34    [22384977]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6645
_дух_,

есть такой анекдот

+
автор
Задача I
Пусть у нас есть пустой чайник, кран с водой, спички, газовая конфорка.
Перед физиком и математиком ставят задачу вскипятить воду.
Действуют они одинаково.
1. Наливают воду в чайник.
2. Зажигают конфорку.
3. Ставят чайник на огонь и ждут, пока закипит.

Модифицируем Задачу I в Задачу II.
У нас уже есть чайник, наполненный водой и зажженная конфорка. Цель та же: вскипятить воду.

Физик ставит чайник на огонь и ждет, пока вода закипит.

Математик выключает огонь, выливает воду из чайника и говорит: теперь задача сводится к предыдущей. (В некоторых интерпретациях математик после этого ждет, пока придет физик и вскипятит воду)))


Доказывается применимость очень просто, вот давайте сделаем как математики
у вас есть набор путей <откуда, куда>

а давай туда условие перехода добавим инкрементально (1, 2, 3 и т.д), т.е. на каждый переход у нас получится единственное неповторимое условие

и что мы увидим? КА
причём, ДКА, так как условия переходов у нас уникальные

а дальше что делать? - мы знаем ...

теперь по асимптотике, говорится, что алгоритм может быть экспоненциальным, но в самом алгоритме мы видим только циклы по количеству элементов O(N). Экспоненциальность получается в subset construction, при преобразовании
из НКА в ДКА. Но у нас уже ДКА, следовательно количество элементов может только уменьшаться!!!
следовательно алгоритм O(N) для нашего случая

Всё просто?
18 окт 21, 13:20    [22385006]     Ответить | Цитировать Сообщить модератору
 Re: Задача оптимизации  [new]
_дух_
Member

Откуда:
Сообщений: 20
kealon(Ruslan),

А есть ещё поговорка - если у бабушки есть член то он уже дедушка.
Да, как вы написали сделать можно, но это как бы сказать -странно- привести задачу к общему случаю для того что бы реализовать решение для частного случая. И третий пункт задачи минимизации ДКА нам не нужен. Ну да бог с ним, а вот алгоритм который вы описали - частный случай - мне подходит / спасибо. Буду думать о компактном представлении реверснутого графа.
18 окт 21, 19:26    [22385211]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: 1 2      [все]
Все форумы / Программирование Ответить