OberonCore

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

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




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

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3261
Откуда: Астрахань
1. x[m] выше - это не медиана. Это просто средний элемент.
Для поиска медианы надо выполнить другой алгоритм Хоора с производительностью О(n)
2. Для разделения можно выбрать любой элемент, хоть первый - это понятно.
2. Не понял, что вы понимаете под словом "переносить".


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

Зарегистрирован: Суббота, 27 Февраль, 2010 23:34
Сообщения: 746
Валерий Лаптев писал(а):
1. x[m] выше - это не медиана. Это просто средний элемент.
Для поиска медианы надо выполнить другой алгоритм Хоора с производительностью О(n)
2. Для разделения можно выбрать любой элемент, хоть первый - это понятно.
2. Не понял, что вы понимаете под словом "переносить".
1. Пусть будет срединный элемент...
3. Переносить? Просто присвоить, например, a[i] := a[j]; значение a[j] перенесено в элемент a[i].


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

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


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

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4625
Откуда: Россия, Орёл
Смысл переноса (оптимизация) заключается в смещении отрезка (типа A[i..j] <- A[i+1..j+1]) по ходу выполнения алгоритма (откуда и термин "перенос")?


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

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
Наверное имеется ввиду, что можно соптимизировать swap k-значений слева с k-значениями справа, имея по-прежнему буфер на 1 элемент.
[i1],[i2],...[ik] <-> [j1],[j2],...[jk]

Код:
[i1] ->  t,     [i1] <- [j1]
[i2] -> [j1] ,  [i2] <- [j2]
...
t    -> [jk]

справа налево "перенеслось" как и без оптимизации
слева направо - с кольцевым сдвигом на 1 элемент

Всё равно говорить несколько некорректно:
alexus писал(а):
Код:
t := a[i];
a[i] := a[j];
a[j] := t;
Но если задуматься, то два из трёх присваиваний здесь излишни...


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


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

Зарегистрирован: Суббота, 27 Февраль, 2010 23:34
Сообщения: 746
Собственно, имелась ввиду такая разновидность алгоритма быстрой сортировки:
Код:
procedure QuickSort(var a: TAOFI; const left, right: Integer);
var   d   : Boolean;
   x   : Integer;

   procedure QS(const l, r: Integer);
   var   i, j   : Integer;
   begin
      i := l;
      j := r;
      x := a[i];
      d := True;
      while (i < j) do begin
         if d then
            if (x > a[j]) then begin
               a[i] := a[j];
               d := False;
            end else
         else
            if (a[i] > x) then begin
               a[j] := a[i];
               d := True;
            end;
         if d then dec(j) else inc(i);
      end;
      a[i] := x;
      dec(i); inc(j);
      if (l < i) then QS(l, i);
      if (j < r) then QS(j, r);
   end;
begin
   QS(left, right);
end;


Процедура QuickSort представляет собой оболочку вокруг процедуры QS, необходимую, чтобы объявить локальные переменные и, в частности, чтобы не передавать адрес массива при каждом вызове QS.
Логическая переменная "d" определяет направление. При d=True перебираем элементы справа ( dec(j) ), при d=False перебираем элементы слева ( inc(i) ).
Здесь нет операции перестановки и всего один цикл. Срединного значения не используем, берём первый элемент последовательности (массива). При этом добавляется условные операторы проверки направления (хотя последнего тоже можно избежать, используя нечто вроде "процедурной переменной").
Второго условного оператора (if d then dec(j) else inc(i);) можно не применять, уложив действия в первый оператор "if d then...". Второй оператор ("if d then...") введён/оставлен для большей наглядности.
И последнее... оптимизация делалась для последующей реализации на ассемблере (СУБД создавалась на ассемблере), и данная разновидность давала лучший результат на i386. Возможно кому-то будет интересно...


Последний раз редактировалось alexus Суббота, 22 Октябрь, 2011 17:32, всего редактировалось 1 раз.

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

Зарегистрирован: Суббота, 29 Март, 2008 19:27
Сообщения: 1053
Откуда: Россия, Чебоксары
alexus писал(а):
if (l < i) then QS(l, i);
if (j < r) then QS(j, r);
А передача параметров и результатов через стек при рекурсии - это даже ведь не два лишних присваивания!
Да и глубины стека банально может не хватить...
Возможно, конечно, что конвейер конкретного типа процессоров со стеком работает лучше, и эффективность не страдает, но...


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

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
alexus писал(а):
Код:
   end else
  else

???


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

Зарегистрирован: Суббота, 29 Март, 2008 19:27
Сообщения: 1053
Откуда: Россия, Чебоксары
Peter Almazov писал(а):
???
??? В чём вопрос?


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

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Да чего-то не врубаюсь уже в этой каше паскалевской. Сам всегда ставил бЕгины и Энды и не заморачивался.


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

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
как раз и есть - оптимизация перестановок (кол-ва операций с буфером)
если опять же вспомнить:
alexus писал(а):
Код:
t := a[i];
a[i] := a[j];
a[j] := t;
Но если задуматься, то два из трёх присваиваний здесь излишни...


на самом деле и в приведённом выше коде оптимизированного алгоритма экономится только одна пересылка на каждый обмен значениями между левой и правой частью массива за исключением одного обмена.
в обоих вариантах реализации есть перестановка k пар значений
неоптимизированный вариант содержит 3k операций вида a:=b (обмен через буфер t)
оптимизированный - 2k+1


Последний раз редактировалось albobin Суббота, 22 Октябрь, 2011 19:10, всего редактировалось 6 раз(а).

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

Зарегистрирован: Суббота, 27 Февраль, 2010 23:34
Сообщения: 746
Alexey_Donskoy писал(а):
alexus писал(а):
if (l < i) then QS(l, i);
if (j < r) then QS(j, r);
А передача параметров и результатов через стек при рекурсии - это даже ведь не два лишних присваивания!
Передача параметров делается через регистры... давно уже... Но избежать локальных переменных, увы, не получится.
Цитата:
Да и глубины стека банально может не хватить...
... и массивы для сортировок можно взять такие, что массива жёстких дисков не хватит... Алексей, я просто привожу модифицированный алгоритм быстрой сортировки. Сама идея такого алгоритма (рекурсивного по своей сути) не пересматривалась. Он такой, какой есть... Если Вы предложите принципиально иную идею/иной алгоритм, то многим, и мне в их числе, будет очень интересно.


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

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
alexus писал(а):
Передача параметров делается через регистры... давно уже...
Хм...


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

Зарегистрирован: Суббота, 29 Март, 2008 19:27
Сообщения: 1053
Откуда: Россия, Чебоксары
alexus писал(а):
Передача параметров делается через регистры... давно уже...
Ну да, а в начале и в конце процедуры генерируется stack frame, например:
Код:
// p(i,j)
push ebx
push esi
mov esi, edx
mov ebx, eax
...
pop esi
pop ebx
А сами параметры через регистры передаются (eax, edx), да. :D

alexus писал(а):
Но избежать локальных переменных, увы, не получится.
Вот именно.
Тут, как и в любой алгоритмической задаче, есть выбор мжду объёмом памяти и её повторным использованием.
То есть можно иметь буфер в одну переменную и постоянно его переприсваивать, а можно иметь буфер в размере исходного массива, с однократным доступом к каждой ячейке. Собственно, подобные преобразования алгоритма по сути выглядят гомеоморфными (хотя отнюдь не изоморфными).

В данном случае, грубо говоря, сделан буфер размером с массив - только сделан неявно, при помощи стека и рекурсии.

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


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

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
Alexey_Donskoy писал(а):
А сами параметры через регистры передаются (eax, edx), да. :D
И еще не забыть, что регистры вот эти вот -- уж давно не железная, а всего лишь ... лингвистическая реальность микрокода 8)


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

Зарегистрирован: Суббота, 27 Февраль, 2010 23:34
Сообщения: 746
Alexey_Donskoy писал(а):
alexus писал(а):
Передача параметров делается через регистры... давно уже...
Ну да, а в начале и в конце процедуры генерируется stack frame, например:
Код:
// p(i,j)
push ebx
push esi
mov esi, edx
mov ebx, eax
...
pop esi
pop ebx
А сами параметры через регистры передаются (eax, edx), да. :D
Stack frame - это немного другое, он создаётся для локальных переменных. Его создают командами enter/leave или простым вычитанием из esp совокупного размера локальных переменных. Я повторю, что алгоритм оптимизировался для последующей реализации на ассемблере, а там всё в руках программиста... Например, в той реализации, о которой шла речь никаких push/pop не было.
Alexey_Donskoy писал(а):
В данном случае, грубо говоря, сделан буфер размером с массив - только сделан неявно, при помощи стека и рекурсии.
Это крайний случай...
Alexey_Donskoy писал(а):
Выбор конкретного способв реализации зависит от особенностей конкретного исполнителя (процессор, память), но ничего не прибавляет в теоретическом плане. Зато добавляет массу ограничений (ресурсы памяти прежде всего)...
Вы считаете, что предложенный вариант хуже оригинального из-за большего количества ограничений?.. Или Вам не нравятся ограничения оригинального алгоритма быстрой сортировки?..


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

Зарегистрирован: Суббота, 29 Март, 2008 19:27
Сообщения: 1053
Откуда: Россия, Чебоксары
alexus писал(а):
Я повторю, что алгоритм оптимизировался для последующей реализации на ассемблере, а там всё в руках программиста... Например, в той реализации, о которой шла речь никаких push/pop не было.
Пожалуйста. Но тут есть принципиально важное замечание - приведённый алгоритм не идентичен Вашей ассемблерной реализации. Об этом моменте я тут как-то писал в теме Что же такое алгоритм?
Потому как реализация машинно-зависима, и особенно машинно-зависимы "технические характеристики".
В то время как в самом алгоритме нет никакого процессора, кэша, конвейера и особенностей их взаимодействия.

Как вообще можно оценить эффективность именно алгоритма?
Считать по количесвту операций? Вообще не прокатит, уж сильно они разные.

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

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

Судя по ответам в упомянутой теме, общая постановка вопроса никого особо не интересует.
В лучшем случае - интересует переносимость алгоритма (то есть его некие абстрактно-сферические в вакууме свойства, которые для конкретного исполнителя будут в общем случае заведомо неэффективны)...


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

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
Alexey_Donskoy писал(а):
Судя по ответам в упомянутой теме, общая постановка вопроса никого особо не интересует.
В лучшем случае - интересует переносимость алгоритма (то есть его некие абстрактно-сферические в вакууме свойства
Так это давным-давно известно и без ответов в упомянутой теме.

Только почему же абстрактно-сферические.
Вполне конкретная вещь -- как начинаешь переносить, так вполне конкретные килокалории мозг жжёт.

----
Кстати, переносимость -- частный случай evolvability, которое, из опыта человечества, есть главный показатель качества программ. Просто замечание.
----

Для CISC-CPU на микрокоде с внутренним RISC'ом и многоуровневыми непрозрачными, меняющимися от модели CPU к модели кэшами -- возня с ассемблером -- не сильно осмысленная штука.
Может, для драйверописателя в Интеле или АМД, -- но не для прикладника.
Есть чистенький код -- и ладушки.


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

Зарегистрирован: Суббота, 27 Февраль, 2010 23:34
Сообщения: 746
Alexey_Donskoy писал(а):
alexus писал(а):
Я повторю, что алгоритм оптимизировался для последующей реализации на ассемблере, а там всё в руках программиста... Например, в той реализации, о которой шла речь никаких push/pop не было.
Пожалуйста. Но тут есть принципиально важное замечание - приведённый алгоритм не идентичен Вашей ассемблерной реализации. Об этом моменте я тут как-то писал в теме Что же такое алгоритм?
Потому как реализация машинно-зависима, и особенно машинно-зависимы "технические характеристики".
В то время как в самом алгоритме нет никакого процессора, кэша, конвейера и особенностей их взаимодействия.
Говорить об "идентичности" неправильно. Дело в том, что запись алгоритма и реализация алгоритма используют разные языки. Поэтому реализация может только соответствовать алгоритму или не соответствовать, а быть идентичной, в общем случае, не может (разве что процессор поддерживает язык записи алгоритма). Д.Кнут описывает алгоритмы, потом приводит их реализацию на ассемблере. Вы считаете, что эта работа не имеет смысла, поскольку описание - это одно, а реализация совсем другое?.. Другие авторы использовали готовые алгоритмические языки, третьи выдумывали новые (псевдо-)языки. Мне думается, что важно и то, и другое (и описание алгоритма, и его реализация).
Alexey_Donskoy писал(а):
Как вообще можно оценить эффективность именно алгоритма?
Считать по количесвту операций? Вообще не прокатит, уж сильно они разные.
Да, различны... Но эффективность оценивается по определённым операциям, например, операциям сравнения, чтения/записи и т.п. И в оценке работы алгоритма записывают, что он требует, например, N операций сравнения в худшем случае. Другой алгоритм, дающий тот же результат, требует N^2 операций сравнения. Теперь у нас есть основание для сравнения данных алгоритмов. Если операции сравнения для нас не являются показательными, то надо сменить критерии оценки... Только и всего...
Alexey_Donskoy писал(а):
alexus писал(а):
Вы считаете, что предложенный вариант хуже оригинального из-за большего количества ограничений?..
Считаю, что хуже. Потому что эффективность его непредсказуема из-за машинной зависимости (как правило, рекурсия - очень дорогой механизм). В то время как ограничения по ресурсам (память) заранее очевидны.
А Вы оригинал смотрели? Там всё та же рекурсия, и расход по памяти совершенно тот же... (ни на бит больше или меньше).
Alexey_Donskoy писал(а):
Кстати, сравните, насколько для большинства процессоров пара лишних присваиваний (пусть даже с косвенной адресацией) эффективнее вызова процедуры с параметрами. Это общий принцип, Ваша ассемблерная реализация может его и нарушить - в частном случае...
Алексей, не надо сравнивать зелёное с теплым... Это не слишком правильно. Операция записи в память может быть довольно долгой. Посмотрите для примера на многопроцессорные SMP-архитектуры. Прежде, чем записать что-то в память, должна быть выполнена операция синхронизации кэшей процессоров (соблюдение когерентности кэшей). Это объясняет почему производительность компьютеров не растёт пропорционально количеству установленных в нём процессоров/ядер. При прохождении определённого предела количества процессоров/ядер производительность компьютера может не расти, а снижаться... С другой стороны, мы привыкли, что память работает очень быстро, но это не всегда справедливо. Та же флэш-память работает значительно медленнее, и чтение/запись в эту память может происходить существенно медленнее, чем выполнение рекурсивного вызова...
Alexey_Donskoy писал(а):
Судя по ответам в упомянутой теме, общая постановка вопроса никого особо не интересует.
В лучшем случае - интересует переносимость алгоритма (то есть его некие абстрактно-сферические в вакууме свойства, которые для конкретного исполнителя будут в общем случае заведомо неэффективны)...
Ну, раз нет интереса, значит надо закрыть тему... Вот и всё.


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

Зарегистрирован: Суббота, 29 Март, 2008 19:27
Сообщения: 1053
Откуда: Россия, Чебоксары
alexus писал(а):
Мне думается, что важно и то, и другое (и описание алгоритма, и его реализация).
Мне тоже так думается.
Более того, особенности реализации очень часто диктуют выбор предпочтительного алгоритма.
Так, на стековых процессорах рекурсия может быть много оптимальнее, а на обычных оптимальным может быть линейная работа с массивом...

alexus писал(а):
Если операции сравнения для нас не являются показательными, то надо сменить критерии оценки... Только и всего...
Так трудность-то в том, что критерии для разных исполнителей будут разными! ;)

alexus писал(а):
А Вы оригинал смотрели? Там всё та же рекурсия, и расход по памяти совершенно тот же...
Оригинал не смотрел. А что мешало сделать без рекурсии?

alexus писал(а):
Операция записи в память может быть довольно долгой.
Безусловно. Но, в принципе, стек - та же память. И косвенная адресация, и накладные расходы на вызов/возврат...


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

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


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

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


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

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