powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задача оптимизации
38 сообщений из 38, показаны все 2 страниц
Задача оптимизации
    #40104178
_дух_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Есть простая и специфичная виртуалная машина (Для проверки регекспов). Она умеет только простые операции, безусловный переход и операцию деления процесса. И есть некоторый код для этой машины, который имеет одну точку входа и несколко точек выхода. Если один из процессов достигает любой точки выхода то все процессы заверщаются. Заранее известно что код может быть не оптимальным. Задача этот код оптимизировать. Очевидно что если некоторые команды никогда не выполняются их можно удалить. Но естъ ещё бесконечные циклы. Так-как они не видут к результату их тоже нужно оптимизировать.
Задачу можно рассматривать на ориентированном графе с заданной точкой старта и несколькими точками заверщения. Нужно наити все пути ведущие из точки начала в любую точку заверщения. Все отрези которые не входят в эти "пути" можно исключить.
Вот собственно ищю идею быстрого алгоритма.
...
Рейтинг: 0 / 0
Задача оптимизации
    #40104197
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_дух_,

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

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

используемые для оптимизации алгоритмы:
переход от НКА к ДКА - Subset construction
для минимизации ДКА, как вариант, есть простой алгоритм - http://sovietov.com/txt/minfa/minfa.html] Алгоритм Бржозовско
...
Рейтинг: 0 / 0
Задача оптимизации
    #40104199
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А почему там - бесконечные циклы?
...
Рейтинг: 0 / 0
Задача оптимизации
    #40104227
_дух_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
kealon(Ruslan),

Я не вижу как алгоритм минимизации ДКА применим к изложенной задаче. Задачи то совершенно разные.
...
Рейтинг: 0 / 0
Задача оптимизации
    #40104229
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_дух_,

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

автор И есть некоторый код для этой машины, который имеет одну точку входа и несколко точек выхода.
есть State, есть множественные переходы, если предположить что есть ещё условия переходов, то если мой хрустальный шар не сломался, то это и есть НКА
а значит из него можно сделать ДКА
...
Рейтинг: 0 / 0
Задача оптимизации
    #40104231
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_дух_,

если действия вашей "машины" можно описать наподобие этого кода
то ваш "специфичный код" и есть скомпилированные регулярки
...
Рейтинг: 0 / 0
Задача оптимизации
    #40104243
_дух_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
kealon(Ruslan)
_дух_,
вот, для начала, и сформулируйте задачу


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

Вот моя задача. Всё остальное - так немного лирики.
...
Рейтинг: 0 / 0
Задача оптимизации
    #40104245
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_дух_,

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

_дух_
Вот моя задача. Всё остальное - так немного лирики.
В "лирике" часто и кроется решение задачи. Не надо ее забывать.
...
Рейтинг: 0 / 0
Задача оптимизации
    #40104281
_дух_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
White Owl
пропущено...
У графов не бывает точек старта и точек завершения. Вообще не бывает.

Но нам ничто не мешает взять граф и сказать что одна из вершин точка старта или начала пути и также задать набор вершин - точек завершения или конечных точек пути. Такая постановка задачи корекектна.
...
Рейтинг: 0 / 0
Задача оптимизации
    #40104285
_дух_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
kealon(Ruslan)
_дух_,

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

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

Код: python
1.
[[1],[2],[3],FINISH]



Какой результат нам даст Алгоритм Бржозовско?
...
Рейтинг: 0 / 0
Задача оптимизации
    #40104286
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_дух_,

тынц - оч хорошая статья, на пальцах, так сказать
...
Рейтинг: 0 / 0
Задача оптимизации
    #40104308
_дух_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
kealon(Ruslan),

Я рад что вы знаете методы оптимизации ДКА но я повторяю - это не моя задача.
во первых не это не ДКА, во вторых мне ненужно уменьшать количество состояний.
...
Рейтинг: 0 / 0
Задача оптимизации
    #40104309
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_дух_
мне ненужно уменьшать количество состояний.
после выкидывания части ребер (переходов), некоторые вершины (состояния) могут быть недостижимы из старта. Их всё равно нужно оставить?
...
Рейтинг: 0 / 0
Задача оптимизации
    #40104315
_дух_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Имя пользователя1
после выкидывания части ребер (переходов), некоторые вершины (состояния) могут быть недостижимы из старта. Их всё равно нужно оставить?

Рёбра - это действия виртуальной машины. Состояния - не материальны. Просто число.
...
Рейтинг: 0 / 0
Задача оптимизации
    #40104320
_дух_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Имя пользователя1
_дух_
мне ненужно уменьшать количество состояний.
после выкидывания части ребер (переходов), некоторые вершины (состояния) могут быть недостижимы из старта. Их всё равно нужно оставить?

В моём случае "выкидывание рёбер" - это уже последствия. Достаточно наити все пути ведущие из точки начала в любую точку завершения.
...
Рейтинг: 0 / 0
Задача оптимизации
    #40104356
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_дух_
Имя пользователя1
пропущено...
после выкидывания части ребер (переходов), некоторые вершины (состояния) могут быть недостижимы из старта. Их всё равно нужно оставить?

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

Вроде стандартный алгоритм. Поиск минимального дерева. Или остовного.
...
Рейтинг: 0 / 0
Задача оптимизации
    #40104373
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_дух_
kealon(Ruslan)
_дух_,

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

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

Код: python
1.
[[1],[2],[3],FINISH]



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

FINISH и даст, переходы то у вас безусловные
а какой результат вы ожидаете?
...
Рейтинг: 0 / 0
Задача оптимизации
    #40104384
_дух_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
kealon(Ruslan),

я как бы издалека намекал что это граф - не автомат.
...
Рейтинг: 0 / 0
Задача оптимизации
    #40104386
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А переходы между состояниями автомата - граф.
...
Рейтинг: 0 / 0
Задача оптимизации
    #40104426
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_дух_
kealon(Ruslan),

я как бы издалека намекал что это граф - не автомат.
ваши намёки интереса не представляют, вы же доктору не говорите "догодайся сам, а я посижу" ? вот на форуме тоже самое.
мы пока от вас даже внятного условия задачи не видим, как же вам помочь то?
...
Рейтинг: 0 / 0
Задача оптимизации
    #40104473
_дух_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
kealon(Ruslan)
мы пока от вас даже внятного условия задачи не видим, как же вам помочь то?


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

Если вам что-то непонятно задавайте вопрос.
Подозреваю студент до вопроса не созрел но про вшей билет выучил.
...
Рейтинг: 0 / 0
Задача оптимизации
    #40104479
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_дух_,

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

22383615

а ответ на ваш вопрос тот же самый
22383380
только чуть упростить его: "отжиг" с выходов, потом отжиг со входа по оставшемся переходам
...
Рейтинг: 0 / 0
Задача оптимизации
    #40104733
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_дух_
Задачу можно рассматривать на ориентированном графе с заданной точкой старта и несколькими точками заверщения. Нужно наити все пути ведущие из точки начала в любую точку завершения.

Форд-Фалкерсон и его модификации. Ищет кратчайшие пути из заданной вершины графа в любую другую. Рекомендую.
...
Рейтинг: 0 / 0
Задача оптимизации
    #40104757
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov
Ищет кратчайшие пути из заданной вершины графа в любую другую.
как я понял, нужны все пути в заданные вершины, а не только кратчайшие.
...
Рейтинг: 0 / 0
Задача оптимизации
    #40104772
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если все нужны, тогда и циклы нужны, и комбинации циклов. А так да, алгоритмов дофига, и зачем было здесь спрашивать?
...
Рейтинг: 0 / 0
Задача оптимизации
    #40104931
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1
как я понял, нужны все пути в заданные вершины, а не только кратчайшие.

Тогда простая рекурсия. Но она зациклится есть есть хоть одно кольцо.
...
Рейтинг: 0 / 0
Задача оптимизации
    #40104947
Фотография Верблюд
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1
Dimitry Sibiryakov
Ищет кратчайшие пути из заданной вершины графа в любую другую.
как я понял, нужны все пути в заданные вершины, а не только кратчайшие.


"всех" путей может оказаться бесконечно много.
...
Рейтинг: 0 / 0
Задача оптимизации
    #40104976
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если хороводы кругами не не накручивать, бесконечностей не будет.
...
Рейтинг: 0 / 0
Задача оптимизации
    #40104989
Фотография Верблюд
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98
Если хороводы кругами не не накручивать, бесконечностей не будет.


Тогда в задаче следует указать "не накручивая хороводы". Иначе непонятно будет чего хотят.
...
Рейтинг: 0 / 0
Задача оптимизации
    #40105088
_дух_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Сделал примерно так:
Поиск в глубину запоминает альтернативные вершины для продолжения поиска в стеке.
При прохождении вершины в ней запоминается глубина стека.
На каждом шаге сначала проверяем это значение для новой вершины - В.
Если вершину не посещали - запоминаем глубину и продолжаем.
Иначе просматриваем все вершины и заменяем значение в них на мин(В, значение вершины) (**)
И специальные значения если через вершину (не) проходит путь ведущий к выходу.

Проблематично как мне видится действие (**).
Просмотр всех N вершин в худшем случае выполнится N раз. В итоге O(N^2)
Можно ли сделать быстрее?
...
Рейтинг: 0 / 0
Задача оптимизации
    #40105091
_дух_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
В коде нагляднее.


Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
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 ....
	
}


...
Рейтинг: 0 / 0
Задача оптимизации
    #40105096
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_дух_,

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

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

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

PS: множества <куда, откуда> и <откуда, куда> естественно MultiMap (т.е. позволяют хранить несколько ключей)
...
Рейтинг: 0 / 0
Задача оптимизации
    #40105111
_дух_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
kealon(Ruslan),

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

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


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

Ну и в заключениу к вашему "отжигному" алгоритму - достижимые конечные состояния нужно сначала найти. Это 5 цикл O(N)
...
Рейтинг: 0 / 0
Задача оптимизации
    #40105116
_дух_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
kealon(Ruslan),

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

В моей задаче нету входного сигнала следователно это не КА, следовательно методы для ДКА и НКА не применимы.
...
Рейтинг: 0 / 0
Задача оптимизации
    #40105136
_дух_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
kealon(Ruslan)
_дух_,
вот вы упёртый


вы можете вести диалог на уровне, без оскорблений и перехода на личности?
...
Рейтинг: 0 / 0
Задача оптимизации
    #40105157
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_дух_,

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

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

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

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

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


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

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

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

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

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

Всё просто?
...
Рейтинг: 0 / 0
Задача оптимизации
    #40105271
_дух_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
kealon(Ruslan),

А есть ещё поговорка - если у бабушки есть член то он уже дедушка.
Да, как вы написали сделать можно, но это как бы сказать -странно- привести задачу к общему случаю для того что бы реализовать решение для частного случая. И третий пункт задачи минимизации ДКА нам не нужен. Ну да бог с ним, а вот алгоритм который вы описали - частный случай - мне подходит / спасибо. Буду думать о компактном представлении реверснутого графа.
...
Рейтинг: 0 / 0
38 сообщений из 38, показаны все 2 страниц
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задача оптимизации
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]