Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.143.9.115] |
|
Страницы: (2) [1] 2 все ( Перейти к последнему сообщению ) |
Сообщ.
#1
,
|
|
|
Макросу передаётся 4 параметра: A, B, C и D.
Задача макроса - загрузить в регистры ax, bx, cx и dx значения из этих 4 параметров (ax=A, bx=B, cx=C, dx=D). Для простоты условимся, что параметром может быть число или регистр (ax, bx, cx или dx). Вроде бы всё просто: ax = A bx = B cx = C dx = D Когда макросу передаются числа (например, 1,2,3,4), проблем нет. Проблемы начинаются тогда, когда передаются регистры (или числа с регистрами). Например, передаём 1,cx,2,ax. Тогда получаем: ax = 1 bx = cx cx = 2 dx = ax Эту проблему можно решить, переместив присвоение dx = ax в самое начало (или ax = 1 в конец). Более сложная ситуация: передаём dx,ax,bx,cx ax = dx bx = ax cx = bx dx = cx Здесь как не переставляй, ничего не получится. Однако нам на помощь приходит ещё одна допустимая операция (помимо присвоения) - обмен значениями: ax <-> bx ax <-> cx ax <-> dx Итак, задача №1 (задача минимум): выполнить правильное присвоение, используя наименьшее кол-во операций (присвоения или обмена... если нет разницы какую из операций использовать, присвоение предпочтительнее, но критерий минимизации кол-ва операций важнее). Использовать какие-либо другие регистры (как временные) нельзя. Обмен можно производить только между регистрами (т.е. нельзя сделать обмен между регистром и числом). Пример: dx,cx,bx,ax, решение: ax <-> dx bx <-> cx Пример: 1,dx,ax,bx, решение: cx = ax ax = 1 bx <-> dx Пример: ax,dx,cx,dx, решение: bx = dx Задача №2 (задача максимум): а) при передаче одинаковых чисел заменять числа регистрами, б) использование ax в операциях обмена предпочтительнее, чем другие регистры. Т.е.: ax <-> bx ax <-> cx ax <-> dx dx <-> ax dx <-> bx dx <-> cx По поводу пункта "а" (заменять числа регистрами) имеется в виду следующее. Нужно занести значения dx,1,ax,1, решение: cx = ax ax = dx bx = 1 cx = bx <-- это лучше, чем cx = 1 Подскажите, пожалуйста, как это можно реализовать алгоритмически? Решение нужно не для 4 значений конкретно, а для любого кол-ва (2, 5, 11). Добавлено Хотя, вроде с заменой чисел регистрами (по второй задаче, пункт "а") всё просто: если присвоение такого же значения уже было выше, использовать этот регистр вместо числа |
Сообщ.
#2
,
|
|
|
Больше всего сбивает с толку выбранная терминология (числа, регистры...). Но если избавиться от этой терминологической хрени, а затем формализовать, то задачка оказывается чуть ли не родной сестрой расчёта редакционного предписания.
|
Сообщ.
#3
,
|
|
|
Akina, ок, давай заменим слово "регистр" словом "переменная"
Цитата Akina @ Предписания или расстояние (забиваю в поиске, находится именно "расстояние"). Как-то ещё по-другому такой алгоритм называется? расчёта редакционного предписания |
Сообщ.
#4
,
|
|
|
Расстояние (Левенштейна сотоварищи, если чё) - это сколько от начала до конца. А предписание - это ещё плюс рассказ, как идти.
|
Сообщ.
#5
,
|
|
|
Akina, ну х/з... схожесть вроде есть некоторая, но ИМХО что-то совсем другое... там вставка, удаление... обмена нет (между соседними только если).
|
Сообщ.
#6
,
|
|
|
Мда... нет слов, чтобы выразиться.
Есть начальное состояние. Есть конечное состояние. Есть список разрешённых действий. Задача - найти наиболее короткую последовательность разрешённых действий, трансформирующую начальное состояние в конечное. И это "некоторая схожесть"? |
Сообщ.
#7
,
|
|
|
Цитата Akina @ Тогда не выражайся нет слов, чтобы выразиться. Пока не углублялся в эту тему. Спасибо, посмотрю |
Сообщ.
#8
,
|
|
|
Сначала читаешь значения в локальные _ax, _bx, _cx, _dx, потом если в макрос передается, скажем, "ax", пишешь в данный регистр сохраненный _ax. И так далее.
|
Сообщ.
#9
,
|
|
|
Задача теоретическая или практическая? Если второе, то просто воспользуйся предыдущим советом - сохрани значения во временные переменные, и читай из них - поиск оптимального варианта всё равно будет выполняться на пару порядков дольше, чем присвоение по этому порядку. А если теоретическая, то это просто обход в ширину на графе присвоений.
|
Сообщ.
#10
,
|
|
|
Цитата Vesper @ Сначала читаешь значения в локальные _ax, _bx, _cx, _dx, потом если в макрос передается, скажем, "ax", пишешь в данный регистр сохраненный _ax. И так далее. Цитата Jin X @ Использовать какие-либо другие регистры (как временные) нельзя. OpenGL, задача практическая, но то, что "поиск оптимального варианта всё равно будет выполняться на пару порядков дольше" - это не страшно. Это будет происходить внутри генератора кода (макроса), который на выходе даст нужную последовательность действий. Это похоже на оптимизацию, которую делают компиляторы (только тут препроцессинг). Т.е. не так важно, сколько времени компилятор будет выполнять оптимизацию, главное, чтобы на выходе получился чистый и быстрый код. |
Сообщ.
#11
,
|
|
|
Jin X
Ну тогда тебе всё дадено. Составляй полный словарь операций (если надо - даже с весами), формализуй исходную и конечную точки, и запускай поиск в ширину до SUM(MAX(in)+MAX(out)). На выходе получишь или набор версий оптимального кода, или NULL. |
Сообщ.
#12
,
|
|
|
Тогда завалится на обыкновенном F○, она же (bx, cx, dx, ax). Придется использовать временные переменные так или иначе. Кроме того, современные компиляторы должны уметь убирать неиспользуемые присвоения как минимум.
|
Сообщ.
#13
,
|
|
|
Цитата Vesper @ Тогда завалится на обыкновенном F○, она же (bx, cx, dx, ax). А повнимательнее если читать? среди допустимых действий есть такое, как "обмен значениями". |
Сообщ.
#14
,
|
|
|
Короче, я придумал алгоритм сам
Получение типов значений и поиск "петель". I. Создаём массив типов значений T[1..n]=0 и регистров цикла L[1..n] (второй массив можно не инициализировать), после чего проходимся по всем регистрам (x=1..n): 1. если регистру с номером x присваивается он же сам, переходим к следующему витку цикла; 2. если присваивается число, то T[x]='num'; 3. если присваивается регистр, то смотрим, не получается ли в итоге "петля" (т.е. цепочка присвоений возвращается к этому же регистру, например, ax->bx->ax, ax->cx->bx->dx->ax), для этого создаём "внутренний" цикл: А) y=x; LR=название_текущего_регистра Б) T[y]='reg'; L[y]=IR; PR=регистр_который_присваивается_текущему регистру; PRnum=номер_регистра_PR В) если PR=IR (это петля?): для всех k=x..n: если L[x]=IR, то T[x]='loop'; после всех замен завершаем внутренний цикл Г) регистру PR присваивается другой регистр? - да: y=PRnum, goto Б) - нет: завершаем внутренний цикл Упорядоченное присвоение. II. Проходимся по всем регистрам (x=1..n) 1. Процедура присвоения регистра номер x. А) Если T[x]='num', то перебираем регистры ещё раз (k=1..n) и проверяем: если T[k]='done', то reg(x)=reg(k) и выходим из цикла k; если присвоения не было, то reg(x)=n; в любом случае в конце делаем T[x]='done' Б) Если T[n]='reg' то перебираем регистры ещё раз (k=1..n): если x <> k и T[k]='reg' и регистру номер k присваивается регистр номер x, вызываем процедуру присвоения "1" рекурсивно, передав ему параметр k (в качестве x); после этого reg(x)=присваиваемый_регистр; T[x]='done' В) Если T[n]='loop', то T[k]='done', LR=регистр и перебираем все регистры ещё раз (k=1..n): если T[k]='loop' и L[k]=LR, то меняем reg(x) и reg(k); T[k]='done' Типа такого |
Сообщ.
#15
,
|
|
|
Снова вернулся к этой теме и переработал алгоритм. Всё оказалось немного сложнее (например, петля может содержать "хвост", который не участвует в ней, т.е. A=B, B=C, C=D, D=B - здесь элемент A является лишним; ну и др. нюансы).
В общем, решил написать всё на ЯВУ (в частности, на Delphi). Потестил результат – всё работает В данном алгоритме реализована "программа максимум": при обмене отдаётся предпочтение аккумулятору, если он присутствует, а также регистру присваивается значение другого регистра, если ему уже присвоено такое же значение. Привожу код. Возможно кому-то пригодится. Или кто-то сможет найти ошибку либо оптимизировать его – буду рад обратной связи {$APPTYPE CONSOLE} uses SysUtils; //{$DEFINE Debug} const // Типы присвоений atNone = 0; // Нет присвоения либо это неглавный регистр петли atVal = 1; // Присвоение обычного значения (не регистра из списка R) atReg = 2; // Присвоение значения регистра atRegCh = 3; // Присвоение значения регистра (элементы текущей проверяемой цепочки) atRegNL = 4; // Присвоение значения регистра, точно не участвующего в петлях atLoop = 5; // Главный регистр петли atDone = 255; // Присвоение выполнено Count = 10; // Кол-во регистров Acc = 'D'; // Аккумулятор (предпочтительный регистр для обмена) var R, V: array [1..Count] of String; // R - названия регистров, которым присваивается значение, V - присваиваемые им значения T, LP, LN: array [1..Count] of Word; // T - типы присвоений (см. atXXX), LP - индексы предыдущих регистров цепочки/петли, LN - порядковый номер регистра в цепочке i, j, k, m, n: Word; Flag: Boolean; begin // Ввод данных for i := 1 to Count do begin R[i] := Chr(64+i); // Регистры будут иметь названия A, B, C, D... важное условие алгоритма: все регистры списка R должны быть разными! Write(R[i], '='); ReadLn(V[i]); V[i] := UpperCase(Trim(V[i])); // Приводим значения к верхнему регистру и удаляем концевые пробелы end; // Этап 1.1. Заполнение массива T for i := 1 to Count do begin if V[i] = '' then T[i] := atNone // Пусто, присвоения нет else begin T[i] := atVal; // Предполагаем, что регистру присваивается обычное значения (не регистр из списка R) for j := 1 to Count do if V[i] = R[j] then // Регистру присваивается другой регистр? if i = j then T[i] := atNone // Регистру присваивается он сам else T[i] := atReg // Регистру присваивается другой регистр end end; // Этап 1.2. Поиск петель, коррекция массива T и заполнение массивов LP и LN for i := 1 to Count do if T[i] = atReg then // Регистру i присваивается другой регистр begin // Проверка цепочки присвоений на наличие петли m := i; // m - индекс главного регистра петли (с которым в дальнейшем будет производиться обмен) n := i; // n - индекс регистра, которому присваивается другой регистр цепочки k := 1; // Это первый регистр в цепочке Flag := False; // Петля не найдена repeat LN[n] := k; // Порядковый номер регистра в цепочке T[n] := atRegCh; // Помечаем регистр как участвующий в петле Inc(k); for j := 1 to Count do // Ищем индекс регистра, который присваивается регистру n (а он точно есть, т.к. T[n] = atReg) if R[j] = V[n] then // Нашли? begin if R[j] = Acc then m := j; // Это аккумулятор? Тогда m = новый индекс главного регистра в цепочке LP[j] := n; // Индекс предыдущего регистра цепочки (предполагаемой петли) Break; // Выходим из цикла, если нашли end; n := j; // Следующий регистр // Пометка регистров петли if T[n] = atRegCh then // Это петля? begin k := LN[n]; // Порядковый номер первого регистра петли (без учёта хвоста в начале цепочки) for j := 1 to Count do if T[j] = atRegCh then // Проверяем все регистры этой петли if LN[j] < k then begin T[j] := atRegNL; // Если порядковый номер первого регистра этой петли меньше порядкового номера текущего регистра этой петли, значит это хвост, не участвующей в петле // (мы помечаем его другим значением, чтобы не тратить время на эти циклы, если мы найдем ещё более ранний элемент этого хвоста) if j = m then m := n // Если это главный регистр, меняем его на n end else T[j] := atNone; // Иначе это регистр петли, помечаем его T[m] := atLoop; // Помечаем главный регистр Flag := True; // Петля найдена Break // Выходим из цикла после нахождения петли end until T[n] <> atReg; if not Flag then for j := 1 to Count do if T[j] = atRegCh then T[j] := atRegNL // Если петля не найдена, помечаем все регистры atRegCh как atRegNL (неучаствующие в петлях) end; {$IFDEF Debug} WriteLn; WriteLn('Tables:'); WriteLn('#'#9'R'#9'V'#9'T'#9'LP'#9'LN'); for i := 1 to Count do WriteLn(i, #9, R[i], #9, V[i], #9, T[i], #9, LP[i], #9, LN[i]); {$ENDIF} WriteLn; WriteLn('Assignment sequence:'); // Зтап 2.1. Присвоение значений регистрам, не находящимся в петле repeat n := 0; // Присвоений не было for i := 1 to Count do if T[i] in [atVal, atReg, atRegNL] then begin // Поиск регистров, которые зависят от текущего (R[i]) Flag := False; // Зависимый регистр пока не найден for j := 1 to Count do if (T[j] in [atReg, atRegNL]) and (V[j] = R[i]) then begin Flag := True; // Если нашли, то выходим из цикла Break end; if not Flag then begin // Присвоение значения (зависимых регистров нет) if T[i] = atVal then begin if V[i] = '0' then WriteLn(R[i], '=zero (xor itself)') else begin // Простое значение Flag := False; // Значение ещё не присваивалось ранее for j := 1 to Count do if (V[i] = V[j]) and (T[j] = atDone) then begin WriteLn(R[i], '=', R[j], ' (value is already set)'); Flag := True; Break end; if not Flag then WriteLn(R[i], '=', V[i], ' (simple value)'); end end else WriteLn(R[i], '=', V[i]); // Присвоение одного регистра другому T[i] := atDone; // Присвоение выполнено Inc(n); // Присвоение было Break // Прерываем цикл for i end end until n = 0; // Зтап 2.2. Обмен значений регистров (находящихся в петле) for i := 1 to Count do if T[i] = atLoop then begin k := i; repeat n := LP[k]; WriteLn(R[i], '<->', R[n]); k := n; // Переходим к следующему until LP[k] = i // Пока не наткнёмся на себя самого end end. p.s. Теперь осталось перевести всё это на макросредства Assembler'а |