OberonCore
https://forum.oberoncore.ru/

Оптимизация алгоритмов
https://forum.oberoncore.ru/viewtopic.php?f=5&t=3620		 Страница 2 из 4
Автор:  Валерий Лаптев [ Четверг, 20 Октябрь, 2011 10:54 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов
1. x[m] выше - это не медиана. Это просто средний элемент.
Для поиска медианы надо выполнить другой алгоритм Хоора с производительностью О(n)
2. Для разделения можно выбрать любой элемент, хоть первый - это понятно.
2. Не понял, что вы понимаете под словом "переносить".
Автор:  alexus [ Четверг, 20 Октябрь, 2011 11:22 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов
Валерий Лаптев писал(а):
1. x[m] выше - это не медиана. Это просто средний элемент.
Для поиска медианы надо выполнить другой алгоритм Хоора с производительностью О(n)
2. Для разделения можно выбрать любой элемент, хоть первый - это понятно.
2. Не понял, что вы понимаете под словом "переносить".
1. Пусть будет срединный элемент...
3. Переносить? Просто присвоить, например, a[i] := a[j]; значение a[j] перенесено в элемент a[i].
Автор:  albobin [ Четверг, 20 Октябрь, 2011 19:21 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов
Лучше назвать это не переносом, а кирдыком значения в ячейке i :)
Автор:  Евгений Темиргалеев [ Пятница, 21 Октябрь, 2011 08:56 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов
Смысл переноса (оптимизация) заключается в смещении отрезка (типа A[i..j] <- A[i+1..j+1]) по ходу выполнения алгоритма (откуда и термин "перенос")?
Автор:  albobin [ Пятница, 21 Октябрь, 2011 09:19 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов
Наверное имеется ввиду, что можно соптимизировать 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;
Но если задуматься, то два из трёх присваиваний здесь излишни...


И первое присваивание нужно и последнее, а вот срединных может быть больше чем одно в зависимости от кол-ва элементов вовлечённых в кольцевой по сути сдвиг.
Автор:  alexus [ Суббота, 22 Октябрь, 2011 07:57 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов
Собственно, имелась ввиду такая разновидность алгоритма быстрой сортировки:
Код:
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. Возможно кому-то будет интересно...
Автор:  Alexey_Donskoy [ Суббота, 22 Октябрь, 2011 09:27 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов
alexus писал(а):
if (l < i) then QS(l, i);
if (j < r) then QS(j, r);
А передача параметров и результатов через стек при рекурсии - это даже ведь не два лишних присваивания!
Да и глубины стека банально может не хватить...
Возможно, конечно, что конвейер конкретного типа процессоров со стеком работает лучше, и эффективность не страдает, но...
Автор:  Peter Almazov [ Суббота, 22 Октябрь, 2011 09:31 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов
alexus писал(а):
Код:
   end else
  else

???
Автор:  Alexey_Donskoy [ Суббота, 22 Октябрь, 2011 10:13 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов
Peter Almazov писал(а):
???
??? В чём вопрос?
Автор:  Peter Almazov [ Суббота, 22 Октябрь, 2011 10:18 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов
Да чего-то не врубаюсь уже в этой каше паскалевской. Сам всегда ставил бЕгины и Энды и не заморачивался.
Автор:  albobin [ Суббота, 22 Октябрь, 2011 17:25 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов
как раз и есть - оптимизация перестановок (кол-ва операций с буфером)
если опять же вспомнить:
alexus писал(а):
Код:
t := a[i];
a[i] := a[j];
a[j] := t;
Но если задуматься, то два из трёх присваиваний здесь излишни...


на самом деле и в приведённом выше коде оптимизированного алгоритма экономится только одна пересылка на каждый обмен значениями между левой и правой частью массива за исключением одного обмена.
в обоих вариантах реализации есть перестановка k пар значений
неоптимизированный вариант содержит 3k операций вида a:=b (обмен через буфер t)
оптимизированный - 2k+1
Автор:  alexus [ Суббота, 22 Октябрь, 2011 17:37 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов
Alexey_Donskoy писал(а):
alexus писал(а):
if (l < i) then QS(l, i);
if (j < r) then QS(j, r);
А передача параметров и результатов через стек при рекурсии - это даже ведь не два лишних присваивания!
Передача параметров делается через регистры... давно уже... Но избежать локальных переменных, увы, не получится.
Цитата:
Да и глубины стека банально может не хватить...
... и массивы для сортировок можно взять такие, что массива жёстких дисков не хватит... Алексей, я просто привожу модифицированный алгоритм быстрой сортировки. Сама идея такого алгоритма (рекурсивного по своей сути) не пересматривалась. Он такой, какой есть... Если Вы предложите принципиально иную идею/иной алгоритм, то многим, и мне в их числе, будет очень интересно.
Автор:  Info21 [ Суббота, 22 Октябрь, 2011 19:51 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов
alexus писал(а):
Передача параметров делается через регистры... давно уже...
Хм...
Автор:  Alexey_Donskoy [ Воскресенье, 23 Октябрь, 2011 10:20 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов
alexus писал(а):
Передача параметров делается через регистры... давно уже...
Ну да, а в начале и в конце процедуры генерируется stack frame, например:
Код:
// p(i,j)
push ebx
push esi
mov esi, edx
mov ebx, eax
...
pop esi
pop ebx
А сами параметры через регистры передаются (eax, edx), да. :D

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

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

Выбор конкретного способв реализации зависит от особенностей конкретного исполнителя (процессор, память), но ничего не прибавляет в теоретическом плане. Зато добавляет массу ограничений (ресурсы памяти прежде всего)...
Автор:  Info21 [ Воскресенье, 23 Октябрь, 2011 12:08 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов
Alexey_Donskoy писал(а):
А сами параметры через регистры передаются (eax, edx), да. :D
И еще не забыть, что регистры вот эти вот -- уж давно не железная, а всего лишь ... лингвистическая реальность микрокода 8)
Автор:  alexus [ Воскресенье, 23 Октябрь, 2011 12:30 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов
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 писал(а):
Выбор конкретного способв реализации зависит от особенностей конкретного исполнителя (процессор, память), но ничего не прибавляет в теоретическом плане. Зато добавляет массу ограничений (ресурсы памяти прежде всего)...
Вы считаете, что предложенный вариант хуже оригинального из-за большего количества ограничений?.. Или Вам не нравятся ограничения оригинального алгоритма быстрой сортировки?..
Автор:  Alexey_Donskoy [ Воскресенье, 23 Октябрь, 2011 12:51 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов
alexus писал(а):
Я повторю, что алгоритм оптимизировался для последующей реализации на ассемблере, а там всё в руках программиста... Например, в той реализации, о которой шла речь никаких push/pop не было.
Пожалуйста. Но тут есть принципиально важное замечание - приведённый алгоритм не идентичен Вашей ассемблерной реализации. Об этом моменте я тут как-то писал в теме Что же такое алгоритм?
Потому как реализация машинно-зависима, и особенно машинно-зависимы "технические характеристики".
В то время как в самом алгоритме нет никакого процессора, кэша, конвейера и особенностей их взаимодействия.

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

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

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

Судя по ответам в упомянутой теме, общая постановка вопроса никого особо не интересует.
В лучшем случае - интересует переносимость алгоритма (то есть его некие абстрактно-сферические в вакууме свойства, которые для конкретного исполнителя будут в общем случае заведомо неэффективны)...
Автор:  Info21 [ Воскресенье, 23 Октябрь, 2011 13:05 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов
Alexey_Donskoy писал(а):
Судя по ответам в упомянутой теме, общая постановка вопроса никого особо не интересует.
В лучшем случае - интересует переносимость алгоритма (то есть его некие абстрактно-сферические в вакууме свойства
Так это давным-давно известно и без ответов в упомянутой теме.

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

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

Для CISC-CPU на микрокоде с внутренним RISC'ом и многоуровневыми непрозрачными, меняющимися от модели CPU к модели кэшами -- возня с ассемблером -- не сильно осмысленная штука.
Может, для драйверописателя в Интеле или АМД, -- но не для прикладника.
Есть чистенький код -- и ладушки.
Автор:  alexus [ Воскресенье, 23 Октябрь, 2011 15:56 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов
Alexey_Donskoy писал(а):
alexus писал(а):
Я повторю, что алгоритм оптимизировался для последующей реализации на ассемблере, а там всё в руках программиста... Например, в той реализации, о которой шла речь никаких push/pop не было.
Пожалуйста. Но тут есть принципиально важное замечание - приведённый алгоритм не идентичен Вашей ассемблерной реализации. Об этом моменте я тут как-то писал в теме Что же такое алгоритм?
Потому как реализация машинно-зависима, и особенно машинно-зависимы "технические характеристики".
В то время как в самом алгоритме нет никакого процессора, кэша, конвейера и особенностей их взаимодействия.
Говорить об "идентичности" неправильно. Дело в том, что запись алгоритма и реализация алгоритма используют разные языки. Поэтому реализация может только соответствовать алгоритму или не соответствовать, а быть идентичной, в общем случае, не может (разве что процессор поддерживает язык записи алгоритма). Д.Кнут описывает алгоритмы, потом приводит их реализацию на ассемблере. Вы считаете, что эта работа не имеет смысла, поскольку описание - это одно, а реализация совсем другое?.. Другие авторы использовали готовые алгоритмические языки, третьи выдумывали новые (псевдо-)языки. Мне думается, что важно и то, и другое (и описание алгоритма, и его реализация).
Alexey_Donskoy писал(а):
Как вообще можно оценить эффективность именно алгоритма?
Считать по количесвту операций? Вообще не прокатит, уж сильно они разные.
Да, различны... Но эффективность оценивается по определённым операциям, например, операциям сравнения, чтения/записи и т.п. И в оценке работы алгоритма записывают, что он требует, например, N операций сравнения в худшем случае. Другой алгоритм, дающий тот же результат, требует N^2 операций сравнения. Теперь у нас есть основание для сравнения данных алгоритмов. Если операции сравнения для нас не являются показательными, то надо сменить критерии оценки... Только и всего...
Alexey_Donskoy писал(а):
alexus писал(а):
Вы считаете, что предложенный вариант хуже оригинального из-за большего количества ограничений?..
Считаю, что хуже. Потому что эффективность его непредсказуема из-за машинной зависимости (как правило, рекурсия - очень дорогой механизм). В то время как ограничения по ресурсам (память) заранее очевидны.
А Вы оригинал смотрели? Там всё та же рекурсия, и расход по памяти совершенно тот же... (ни на бит больше или меньше).
Alexey_Donskoy писал(а):
Кстати, сравните, насколько для большинства процессоров пара лишних присваиваний (пусть даже с косвенной адресацией) эффективнее вызова процедуры с параметрами. Это общий принцип, Ваша ассемблерная реализация может его и нарушить - в частном случае...
Алексей, не надо сравнивать зелёное с теплым... Это не слишком правильно. Операция записи в память может быть довольно долгой. Посмотрите для примера на многопроцессорные SMP-архитектуры. Прежде, чем записать что-то в память, должна быть выполнена операция синхронизации кэшей процессоров (соблюдение когерентности кэшей). Это объясняет почему производительность компьютеров не растёт пропорционально количеству установленных в нём процессоров/ядер. При прохождении определённого предела количества процессоров/ядер производительность компьютера может не расти, а снижаться... С другой стороны, мы привыкли, что память работает очень быстро, но это не всегда справедливо. Та же флэш-память работает значительно медленнее, и чтение/запись в эту память может происходить существенно медленнее, чем выполнение рекурсивного вызова...
Alexey_Donskoy писал(а):
Судя по ответам в упомянутой теме, общая постановка вопроса никого особо не интересует.
В лучшем случае - интересует переносимость алгоритма (то есть его некие абстрактно-сферические в вакууме свойства, которые для конкретного исполнителя будут в общем случае заведомо неэффективны)...
Ну, раз нет интереса, значит надо закрыть тему... Вот и всё.
Автор:  Alexey_Donskoy [ Воскресенье, 23 Октябрь, 2011 16:24 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов
alexus писал(а):
Мне думается, что важно и то, и другое (и описание алгоритма, и его реализация).
Мне тоже так думается.
Более того, особенности реализации очень часто диктуют выбор предпочтительного алгоритма.
Так, на стековых процессорах рекурсия может быть много оптимальнее, а на обычных оптимальным может быть линейная работа с массивом...

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

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

alexus писал(а):
Операция записи в память может быть довольно долгой.
Безусловно. Но, в принципе, стек - та же память. И косвенная адресация, и накладные расходы на вызов/возврат...
Страница 2 из 4 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/