OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Четверг, 28 Март, 2024 19:54

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 72 ]  На страницу Пред.  1, 2, 3, 4  След.
Автор Сообщение
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Воскресенье, 23 Октябрь, 2011 17:38 
Аватара пользователя

Зарегистрирован: Суббота, 27 Февраль, 2010 23:34
Сообщения: 746
Alexey_Donskoy писал(а):
alexus писал(а):
Если операции сравнения для нас не являются показательными, то надо сменить критерии оценки... Только и всего...
Так трудность-то в том, что критерии для разных исполнителей будут разными! ;)
Да, конечно, поэтому надо иметь возможность менять критерии.
Alexey_Donskoy писал(а):
alexus писал(а):
А Вы оригинал смотрели? Там всё та же рекурсия, и расход по памяти совершенно тот же...
Оригинал не смотрел. А что мешало сделать без рекурсии?
Попробуйте. Идея алгоритма довольна проста.
Alexey_Donskoy писал(а):
alexus писал(а):
Операция записи в память может быть довольно долгой.
Безусловно. Но, в принципе, стек - та же память. И косвенная адресация, и накладные расходы на вызов/возврат...
Стек не всегда "та же память", она для каждого процесса/потока уникальна, а следовательно, нет проблемы с синхронизацией, например. Но по сути, Вы правы.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Понедельник, 24 Октябрь, 2011 07:45 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
alexus писал(а):
Таким образом, задача свелась к тому, что надо найти "нужное место", попутно перенося меньшие элементы влево, а большие элементы вправо. Но операция переноса, не тождественна операции обмена, это всего одно присваивание, а не три...

Интересно, продолжает ли автор настаивать на своём тезисе. К слову, обмен в исходном варианте - это два переноса у автора, выполняющихся в разных ветках :) Но сама реализация алгоритма быстрой сортировки вполне съедобна.
<удалена фраза, не относящаяся к делу>


Последний раз редактировалось albobin Понедельник, 24 Октябрь, 2011 08:49, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Понедельник, 24 Октябрь, 2011 08:39 
Аватара пользователя

Зарегистрирован: Суббота, 27 Февраль, 2010 23:34
Сообщения: 746
albobin писал(а):
alexus писал(а):
Таким образом, задача свелась к тому, что надо найти "нужное место", попутно перенося меньшие элементы влево, а большие элементы вправо. Но операция переноса, не тождественна операции обмена, это всего одно присваивание, а не три...

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

Добавлю для Алексей Донского...
Для борьбы с избыточной рекурсией в алгоритме быстрой сортировки можно использовать интересный приём. Суть его состоит в следующем: когда мы нашли место для элемента (x), то дальше следуют два рекурсивных вызова процедуры QS, один для левой части, второй для правой части последовательности (массива). После этого процедура QS завершает свою работу.
Код:
      dec(i); inc(j);
      if (l < i) then QS(l, i);
      if (j < r) then QS(j, r);
Так вот, второй рекурсивный вызов можно заменить (без потери работоспособности сортировки) на безусловный переход к началу процедуры. На ЯВУ это сделать затруднительно, на ассемблере - легко. Но если такое возможно, тогда и один оставшийся рекурсивный вызов можно оптимизировать. Надо делать рекурсивный вызов не для левой и не для правой, а для наименьшей (из них) последовательности (наиболее короткой из 2-х частей массива). Например, i - l = 5, r - j = 12, тогда сначала делаем рекурсивный вызов QS(l, r), а затем GoTo(j, r). Если же i- l = 34, а r - j = 18, то тогда делаем QS(j, r) и затем GoTo(l, i). К сожалению, проиллюстрировать этот трюк на Паскале невозможно, но если интересно, то могу привести листинг на ассемблере (он кстати не намного больше по количеству строк, чем приведённый алгоритм на Паскале).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Понедельник, 24 Октябрь, 2011 11:23 

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1428
alexus писал(а):
Так вот, второй рекурсивный вызов можно заменить (без потери работоспособности сортировки) на безусловный переход к началу процедуры. На ЯВУ это сделать затруднительно, на ассемблере - легко.

На ЯВУ тоже не особо сложно
Код:
 if (j < r) then begin l := j ; goto 1; end;


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Понедельник, 24 Октябрь, 2011 12:47 
Аватара пользователя

Зарегистрирован: Суббота, 27 Февраль, 2010 23:34
Сообщения: 746
Trurl писал(а):
alexus писал(а):
Так вот, второй рекурсивный вызов можно заменить (без потери работоспособности сортировки) на безусловный переход к началу процедуры. На ЯВУ это сделать затруднительно, на ассемблере - легко.

На ЯВУ тоже не особо сложно
Код:
 if (j < r) then begin l := j ; goto 1; end;
Ну, GoTo - это, конечно не сложно, но вопрос, как с GoTo передать параметры? Если сделать их изменяемыми (var), то меняется логика... а, если const (как сделано ранее), то им нельзя присвоить новые значения...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Понедельник, 24 Октябрь, 2011 13:03 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Решение тут - научить компилятор преобразовывать концевой вызов из рекурсии в jmp с нек. вспом. действиями.
Это несложно.
Тут только штука в том, чтобы такая оптимизация гарантировалась именно описанием языка, тогда можно будет полагаться на это.
Это полезно и для автоматного программирования - назначили каждому состоянию по процедуре и прыгаем из состояния в состояние просто вызовом процедуры очередного состояния.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Понедельник, 24 Октябрь, 2011 13:55 
Аватара пользователя

Зарегистрирован: Суббота, 12 Июль, 2008 22:49
Сообщения: 575
Откуда: Россия, Санкт-Петербург
Только непонятно причём тут алгоритм?
То что тут обсуждается - тонкости реализации под платформу x86.
А вы попробуйте эту оптимизацию к платформе Z80 прилепить - одна фикция получится.
А вот алгоритм быстрой сортировки как был, так и есть (в том числе реализованный на этой платформе).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Понедельник, 24 Октябрь, 2011 14:06 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
Илья Ермаков писал(а):
Решение тут - научить компилятор преобразовывать концевой вызов из рекурсии в ...

В обсуждаемом алгоритме концевых вызовов две штуки


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Понедельник, 24 Октябрь, 2011 14:12 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
Madzi писал(а):
То что тут обсуждается - тонкости реализации под платформу x86.

Позвольте спросить какие? Код на ЯВУ приведён, исходный вариант - Дракон схема.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Понедельник, 24 Октябрь, 2011 14:23 
Аватара пользователя

Зарегистрирован: Суббота, 29 Март, 2008 19:27
Сообщения: 1053
Откуда: Россия, Чебоксары
albobin писал(а):
Позвольте спросить какие? Код на ЯВУ приведён...
Да такие, что на другой платформе алгоритм уже будет неэффективен, его надо будет существенно изменять.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Понедельник, 24 Октябрь, 2011 14:47 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
albobin писал(а):
Илья Ермаков писал(а):
Решение тут - научить компилятор преобразовывать концевой вызов из рекурсии в ...

В обсуждаемом алгоритме концевых вызовов две штуки


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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Понедельник, 24 Октябрь, 2011 15:03 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
Илья Ермаков писал(а):
albobin писал(а):
Илья Ермаков писал(а):
Решение тут - научить компилятор преобразовывать концевой вызов из рекурсии в ...

В обсуждаемом алгоритме концевых вызовов две штуки


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

Код:
 
      if (l < i) then QS(l, i);
      if (j < r) then QS(j, r);

Может быть только первый, или только второй , или сначала один а затем второй. Как понимать тогда "нет никаких действий в вызывающей процедуре"?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Понедельник, 24 Октябрь, 2011 15:23 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Хм.
Я не смотрел в исходный алгоритм и даже не вспоминал его.

Отреагировал на Вашу фразу "два концевых вызова", подумал, что там else.

Тогда здесь, если говорить статически, не два концевых вызова, а один, второй.
Если не говорить о динамическом выявлении "концовости", что уже избыточно сложная оптимизация.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Понедельник, 24 Октябрь, 2011 15:43 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
Да, правильнее было бы сказать "два как бы концевых ..." :)
А вообще то зачем бороться с рекурсией в реализации рекурсивного по своей сути алгоритма. Сортировки и другие есть.


Последний раз редактировалось albobin Понедельник, 24 Октябрь, 2011 15:49, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Понедельник, 24 Октябрь, 2011 15:45 
Аватара пользователя

Зарегистрирован: Суббота, 27 Февраль, 2010 23:34
Сообщения: 746
Илья Ермаков писал(а):
Решение тут - научить компилятор преобразовывать концевой вызов из рекурсии в jmp с нек. вспом. действиями.
Это несложно.
В принципе, конечно, не сложно...
Илья Ермаков писал(а):
Тут только штука в том, чтобы такая оптимизация гарантировалась именно описанием языка, тогда можно будет полагаться на это.
Хм?.. Непонятно, о каких гарантиях идёт речь?..
Илья Ермаков писал(а):
Это полезно и для автоматного программирования - назначили каждому состоянию по процедуре и прыгаем из состояния в состояние просто вызовом процедуры очередного состояния.
Ух, тут бы не ошибиться... если в одной процедуре количество формальных параметров, передаваемых через стек, будет иным, чем в той процедуре, откуда прыгали (jump), то... проблемы возникнут при разгрузке стека. Тоже относится к совокупному размеру локальных переменных...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Понедельник, 24 Октябрь, 2011 15:57 
Аватара пользователя

Зарегистрирован: Суббота, 27 Февраль, 2010 23:34
Сообщения: 746
Madzi писал(а):
Только непонятно причём тут алгоритм?
То что тут обсуждается - тонкости реализации под платформу x86.
"Реализации" чего, позвольте поинтересоваться?..
Madzi писал(а):
А вы попробуйте эту оптимизацию к платформе Z80 прилепить - одна фикция получится.
А вот алгоритм быстрой сортировки как был, так и есть (в том числе реализованный на этой платформе).
Ну, почему же... берём паскалевский код (см. выше)... достаём из пыльного шкафа Robotron-1715, компилятор от Borlanda Turbo Pascal 3.0... и вполне себе рабочий код получаем. И всё что говорилось про оптимизацию будет вполне справедливо под Zilog80... Мало того, и под UltraSPARC IV+ (Panther) (Sun) эта вариация кода работала.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Понедельник, 24 Октябрь, 2011 16:03 
Аватара пользователя

Зарегистрирован: Суббота, 27 Февраль, 2010 23:34
Сообщения: 746
Alexey_Donskoy писал(а):
albobin писал(а):
Позвольте спросить какие? Код на ЯВУ приведён...
Да такие, что на другой платформе алгоритм уже будет неэффективен, его надо будет существенно изменять.
Неэффективен по сравнению с чем?.. Если мы сравниваем оригинальный алгоритм с модифицированным, то вполне возможно что на разных платформах соотношение их эффективности будет отличаться... Это относится не только к разному "железу", но и к разным ОС, разным компиляторам... Но что же из этого следует?.. Не надо выдумывать алгоритмы? Не надо создавать их модификации?.. Не имеет смысла всё это обсуждать?..


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Понедельник, 24 Октябрь, 2011 16:06 
Аватара пользователя

Зарегистрирован: Суббота, 27 Февраль, 2010 23:34
Сообщения: 746
Илья Ермаков писал(а):
albobin писал(а):
В обсуждаемом алгоритме концевых вызовов две штуки
Всё верно, оба компилятор может реализовать без рекурсии.
Концевой вызов - это после возврата из которого больше нет никаких действий в вызывающей процедуре.
Стоп! Стоп! Стоп! Не объясните мне как-то "оба и без рекурсии"?.. Честное слово, очень интересно!..


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Понедельник, 24 Октябрь, 2011 16:11 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
Дык мы уже консенсус нашли - виновато некорректное использование терминов и некоторая невнимательность :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Понедельник, 24 Октябрь, 2011 16:16 
Аватара пользователя

Зарегистрирован: Суббота, 27 Февраль, 2010 23:34
Сообщения: 746
albobin писал(а):
Да, правильнее было бы сказать "два как бы концевых ..." :)
А вообще то зачем бороться с рекурсией в реализации рекурсивного по своей сути алгоритма. Сортировки и другие есть.
Мы говорили об оптимизации алгоритма... Частичное избавление от рекурсии - это часть оптимизации. Другое дело, что не всякую оптимизацию можно сделать на ЯВУ и тогда получаем зависимость от "исполнителя"... Но сама идея замены рекурсии безусловным переходом... довольно интересна.

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


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 72 ]  На страницу Пред.  1, 2, 3, 4  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 4


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
cron
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2024, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB