На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
Страницы: (2) [1] 2  все  ( Перейти к последнему сообщению )  
> Загрузка значений
    Макросу передаётся 4 параметра: A, B, C и D.
    Задача макроса - загрузить в регистры ax, bx, cx и dx значения из этих 4 параметров (ax=A, bx=B, cx=C, dx=D).
    Для простоты условимся, что параметром может быть число или регистр (ax, bx, cx или dx).

    Вроде бы всё просто:
    ExpandedWrap disabled
      ax = A
      bx = B
      cx = C
      dx = D

    Когда макросу передаются числа (например, 1,2,3,4), проблем нет. Проблемы начинаются тогда, когда передаются регистры (или числа с регистрами). Например, передаём 1,cx,2,ax. Тогда получаем:
    ExpandedWrap disabled
      ax = 1
      bx = cx
      cx = 2
      dx = ax
    С присвоением bx=cx проблем нет, а вот в dx уже записывается не переданное значение ax, а изменённое в первой строке.
    Эту проблему можно решить, переместив присвоение dx = ax в самое начало (или ax = 1 в конец).

    Более сложная ситуация: передаём dx,ax,bx,cx
    ExpandedWrap disabled
      ax = dx
      bx = ax
      cx = bx
      dx = cx

    Здесь как не переставляй, ничего не получится.
    Однако нам на помощь приходит ещё одна допустимая операция (помимо присвоения) - обмен значениями:
    ExpandedWrap disabled
      ax <-> bx
      ax <-> cx
      ax <-> dx


    Итак, задача №1 (задача минимум): выполнить правильное присвоение, используя наименьшее кол-во операций (присвоения или обмена... если нет разницы какую из операций использовать, присвоение предпочтительнее, но критерий минимизации кол-ва операций важнее). Использовать какие-либо другие регистры (как временные) нельзя. Обмен можно производить только между регистрами (т.е. нельзя сделать обмен между регистром и числом).

    Пример: dx,cx,bx,ax, решение:
    ExpandedWrap disabled
      ax <-> dx
      bx <-> cx

    Пример: 1,dx,ax,bx, решение:
    ExpandedWrap disabled
      cx = ax
      ax = 1
      bx <-> dx

    Пример: ax,dx,cx,dx, решение:
    ExpandedWrap disabled
      bx = dx


    Задача №2 (задача максимум): а) при передаче одинаковых чисел заменять числа регистрами, б) использование ax в операциях обмена предпочтительнее, чем другие регистры.
    Т.е.:
    ExpandedWrap disabled
      ax <-> bx
      ax <-> cx
      ax <-> dx
    лучше, чем:
    ExpandedWrap disabled
      dx <-> ax
      dx <-> bx
      dx <-> cx

    По поводу пункта "а" (заменять числа регистрами) имеется в виду следующее.
    Нужно занести значения dx,1,ax,1, решение:
    ExpandedWrap disabled
      cx = ax
      ax = dx
      bx = 1
      cx = bx   <-- это лучше, чем cx = 1


    Подскажите, пожалуйста, как это можно реализовать алгоритмически?
    Решение нужно не для 4 значений конкретно, а для любого кол-ва (2, 5, 11).

    Добавлено
    Хотя, вроде с заменой чисел регистрами (по второй задаче, пункт "а") всё просто: если присвоение такого же значения уже было выше, использовать этот регистр вместо числа :)
      Больше всего сбивает с толку выбранная терминология (числа, регистры...). Но если избавиться от этой терминологической хрени, а затем формализовать, то задачка оказывается чуть ли не родной сестрой расчёта редакционного предписания.
        Akina, ок, давай заменим слово "регистр" словом "переменная" :)

        Цитата Akina @
        расчёта редакционного предписания
        Предписания или расстояние (забиваю в поиске, находится именно "расстояние"). Как-то ещё по-другому такой алгоритм называется?
          Расстояние (Левенштейна сотоварищи, если чё) - это сколько от начала до конца. А предписание - это ещё плюс рассказ, как идти.
            Akina, ну х/з... схожесть вроде есть некоторая, но ИМХО что-то совсем другое... там вставка, удаление... обмена нет (между соседними только если).
              Мда... нет слов, чтобы выразиться.

              Есть начальное состояние. Есть конечное состояние. Есть список разрешённых действий. Задача - найти наиболее короткую последовательность разрешённых действий, трансформирующую начальное состояние в конечное.

              И это "некоторая схожесть"?
                Цитата Akina @
                нет слов, чтобы выразиться.
                Тогда не выражайся :)
                Пока не углублялся в эту тему. Спасибо, посмотрю ;)
                  Сначала читаешь значения в локальные _ax, _bx, _cx, _dx, потом если в макрос передается, скажем, "ax", пишешь в данный регистр сохраненный _ax. И так далее.
                    Задача теоретическая или практическая? Если второе, то просто воспользуйся предыдущим советом - сохрани значения во временные переменные, и читай из них - поиск оптимального варианта всё равно будет выполняться на пару порядков дольше, чем присвоение по этому порядку. А если теоретическая, то это просто обход в ширину на графе присвоений.
                      Цитата Vesper @
                      Сначала читаешь значения в локальные _ax, _bx, _cx, _dx, потом если в макрос передается, скажем, "ax", пишешь в данный регистр сохраненный _ax. И так далее.
                      Цитата Jin X @
                      Использовать какие-либо другие регистры (как временные) нельзя.


                      OpenGL, задача практическая, но то, что "поиск оптимального варианта всё равно будет выполняться на пару порядков дольше" - это не страшно. Это будет происходить внутри генератора кода (макроса), который на выходе даст нужную последовательность действий.
                      Это похоже на оптимизацию, которую делают компиляторы (только тут препроцессинг). Т.е. не так важно, сколько времени компилятор будет выполнять оптимизацию, главное, чтобы на выходе получился чистый и быстрый код.
                        Jin X
                        Ну тогда тебе всё дадено. Составляй полный словарь операций (если надо - даже с весами), формализуй исходную и конечную точки, и запускай поиск в ширину до SUM(MAX(in)+MAX(out)). На выходе получишь или набор версий оптимального кода, или NULL.
                          Тогда завалится на обыкновенном F○, она же (bx, cx, dx, ax). Придется использовать временные переменные так или иначе. Кроме того, современные компиляторы должны уметь убирать неиспользуемые присвоения как минимум.
                            Цитата Vesper @
                            Тогда завалится на обыкновенном F○, она же (bx, cx, dx, ax).

                            А повнимательнее если читать? среди допустимых действий есть такое, как "обмен значениями".
                              Короче, я придумал алгоритм сам :)

                              Получение типов значений и поиск "петель".
                              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'

                              Типа такого :)
                                Снова вернулся к этой теме и переработал алгоритм. Всё оказалось немного сложнее (например, петля может содержать "хвост", который не участвует в ней, т.е. A=B, B=C, C=D, D=B - здесь элемент A является лишним; ну и др. нюансы).
                                В общем, решил написать всё на ЯВУ (в частности, на Delphi). Потестил результат – всё работает :D
                                В данном алгоритме реализована "программа максимум": при обмене отдаётся предпочтение аккумулятору, если он присутствует, а также регистру присваивается значение другого регистра, если ему уже присвоено такое же значение.
                                Привожу код. Возможно кому-то пригодится. Или кто-то сможет найти ошибку либо оптимизировать его – буду рад обратной связи ;)
                                ExpandedWrap disabled
                                  {$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'а :wall:
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0579 ]   [ 16 queries used ]   [ Generated: 28.03.24, 21:45 GMT ]