OberonCore
https://forum.oberoncore.ru/

Оптимизация алгоритмов
https://forum.oberoncore.ru/viewtopic.php?f=5&t=3620
Страница 1 из 4

Автор:  alexus [ Четверг, 20 Октябрь, 2011 08:11 ]
Заголовок сообщения:  Оптимизация алгоритмов

Вопросам оптимизации алгоритмов уделяется всё меньше внимания. Объясняется это, как правило, просто: скорость вычисления постоянно возрастает, объёмы оперативной памяти растут не менее быстро... так зачем мучиться... Но, человек на то и человек, что любит помучится, "растечься мыслью по древу"... даже если "древо" называют "hardware".

Автор:  Валерий Лаптев [ Четверг, 20 Октябрь, 2011 08:25 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов

Мне вот пришлось.
Причем, сначала - скорость. По мере продвижения выяснилось, что не хватает 2 гига виртуальной памяти. Пришлось менять алгоритм для уменьшения требований по памяти.
Даже статью написал по программе... :)

Автор:  alexus [ Четверг, 20 Октябрь, 2011 08:27 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов

В сообщении Заголовок: Промежуточный формат приведен вариант алгоритма быстрой сортировки. В своё время (когда мы работали над СУБД), приходилось много заниматься оптимизацией алгоритмов сортировки, поиска, построениями "деревьев", то есть, теми алгоритмами, которые общеизвестны и потому, над ними УЖЕ не думают, дают/берут... как у учебнике...
В алгоритме быстрой сортировки, есть момент, когда происходит перестановка:
Код:
t := a[i];
a[i] := a[j];
a[j] := t;
Но если задуматься, то два из трёх присваиваний здесь излишни...

Автор:  Валерий Лаптев [ Четверг, 20 Октябрь, 2011 08:29 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов

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

Если у нас есть команда обмена, то да. А если нет?

Автор:  alexus [ Четверг, 20 Октябрь, 2011 08:33 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов

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

Если у нас есть команда обмена, то да. А если нет?
В самом обмене нет никакой необходимости... если переформулировать (не меняя сути!) исходную для цикла задачу.

Автор:  alexus [ Четверг, 20 Октябрь, 2011 08:34 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов

Валерий Лаптев писал(а):
Мне вот пришлось.
Причем, сначала - скорость. По мере продвижения выяснилось, что не хватает 2 гига виртуальной памяти. Пришлось менять алгоритм для уменьшения требований по памяти.
Даже статью написал по программе... :)
Это интересно... Можно ссылку на статью?..

Автор:  Alexey_Donskoy [ Четверг, 20 Октябрь, 2011 08:52 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов

alexus писал(а):
В самом обмене нет никакой необходимости... если переформулировать (не меняя сути!) исходную для цикла задачу.
Можно подробнее? Что-то с ходу не соображается...

Автор:  Madzi [ Четверг, 20 Октябрь, 2011 08:56 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов

Есть две ячейки памяти А и Б, зачем менять содержимое этих ячеек, если можно просто использовать далее вместо А, Б, а вместо Б, А? С точки зрения компьютера - это бесполезная трата ресурсов.

Автор:  Валерий Лаптев [ Четверг, 20 Октябрь, 2011 09:00 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов

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

Это был наш астраханский семинар и сборник - на сидюке.
Вот вордовский файл и презентация
Постановка задачи:
Цитата:
Квадратная дискретная решетка L×L узлов, L > 1000
Случайным образом по горизонтали или вертикали размещаются k-меры, k ≈ L/100
Степень анизотропии S = (ng – nv)/(ng + nv),
При |S| = 1 все k-меры размещаются либо по вертикали, либо по горизонтали; при S = 0 оба направления равновероятны

Критерий окончания – нельзя разместить ни одного k-мера доминирующего направления

Схема алгоритма:
Цитата:
Пока возможно размещение в доминантной ориентации
Генерировать текущую ориентацию
Если возможно размещение в текущей ориентации
Генерировать координаты узла
Пока НЕ возможно разместить к_мер в текущей ориентации
Генерировать координаты узла
Конец_цикла
Разместить к_мер
Увеличить счетчики
Конец_если
Конец_цикла


Вложения:
ЭФФЕКТИВНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА ДЖЕММИНГА.rar [476.15 КБ]
Скачиваний: 446
Статья-Лаптев.rar [42.04 КБ]
Скачиваний: 436

Автор:  alexus [ Четверг, 20 Октябрь, 2011 09:02 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов

Alexey_Donskoy писал(а):
alexus писал(а):
В самом обмене нет никакой необходимости... если переформулировать (не меняя сути!) исходную для цикла задачу.
Можно подробнее? Что-то с ходу не соображается...
А Вы не "с ходу", Алексей. Это довольно увлекательно, а если нет, то и обсуждать незачем... Понаблюдайте, что происходит во время сортировки, напишите простую программку, сделайте вывод массива так часто, как сочтёте нужным. Конечно, я могу рассказать, но тогда тему надо было назвать Справочник по Оптимальным/Быстрым Алгоритмам. Но это не слишком интересно... Мысль должна пространство для развития... :)

Автор:  Валерий Лаптев [ Четверг, 20 Октябрь, 2011 09:07 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов

Добавлю. Я студням часто подкидываю задачку про умножение комплексных чисел.
Стандартная формула включает 4 умножения. Можно написать за 3. На количество сложений-вычитаний ограничений нет.
Задачка сродни алгоритму Шрассена для матриц. Там умножение матриц 2*2 выполняется за 8 умножений. Он нашел - за 7.

Автор:  alexus [ Четверг, 20 Октябрь, 2011 09:14 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов

Валерий Лаптев писал(а):
Добавлю. Я студням часто подкидываю задачку про умножение комплексных чисел.
Стандартная формула включает 4 умножения. Можно написать за 3. На количество сложений-вычитаний ограничений нет.
Задачка сродни алгоритму Шрассена для матриц. Там умножение матриц 2*2 выполняется за 8 умножений. Он нашел - за 7.
Да, это знакомо... В начале своей программистской деятельности довелось заниматься преобразованиями Фурье, Уолша и т.п. над временными комплексными последовательностями... Вряд ли что-то там можно улучшить, разве только загрузку/разгрузку стека сопроцессора (FPU), но это на современных процессорах не актуально.

Автор:  alexus [ Четверг, 20 Октябрь, 2011 09:23 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов

Madzi писал(а):
Есть две ячейки памяти А и Б, зачем менять содержимое этих ячеек, если можно просто использовать далее вместо А, Б, а вместо Б, А? С точки зрения компьютера - это бесполезная трата ресурсов.
Менять нужно, поскольку результатом является отсортированная последовательность значений, хранящихся в ячейках. Можно, конечно, сортировать не значения, а индексы ячеек памяти, но сути это не меняет, поскольку в данном случае значениями будут индексы.

Да, замену присваиваний на XOR не предлагать... это не оптимизация, а трюк, хотя и красивый :)
Код:
t := a[i];
a[i] := a[j];
a[j] := t;
Для целых чисел равносильно (если не считать исчезновения локальной переменной t):
Код:
a[i] := a[i] xor a[j];
a[j] := a[i] xor a[j];
a[i] := a[i] xor a[j];

Автор:  Валерий Лаптев [ Четверг, 20 Октябрь, 2011 09:51 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов

alexus писал(а):
В самом обмене нет никакой необходимости... если переформулировать (не меняя сути!) исходную для цикла задачу.

Исходная задача цикла: переставить удаленные элементы поближе к нужному месту.
Делается это относительно некоего "разделяющего" элемента х.
Это у Вирта так.

Автор:  Александр Ильин [ Четверг, 20 Октябрь, 2011 10:14 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов

Интересная тема!

Я пока не догадался, как убрать перестановку из QuickSort'а, но обязательно подумаю.

Вообще, с этими алгоритмами не всё так очевидно, как кажется. У меня был случай, когда мой собственный алгоритм сортировки стабильно обгонял QuickSort на случайных входных данных. Дело было в стандартной дельфийской демо-программе, показывающей параллельную работу нитей. Там три нити одновременно сортируют массивы, а для наглядности после каждой перестановки элементов выводят содержимое массива на экран, но не в виде чисел, а графически: стопка чёрточек, в которой большое число - длинная чёрточка, малое - короткая. Можно, таким образом, видеть, как три стопки сортируются: одна пузырьком, другая quicksort'ом, третья ещё чем-то.

Мой алгоритм выигрывал на том, что у него было меньшее число перестановок и, соответственно, он меньше тратил времени на перерисовку. Я этот алгоритм ещё когда в школе учился придумал, а потом узнал, что он называется сортировка выбором.

Автор:  Валерий Лаптев [ Четверг, 20 Октябрь, 2011 10:18 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов

Да, из простых алгоритмов сортировка выбором - наилучшая. Там сравнений n^2, а перестановок только n - что и дает выигрыш. Сравнение-то это только одна команда процессора.
Кстати, в книге Бентли "обсасывается" бинарный поиск. Первая исходная версия и конечная оптимизированная различаются по быстродействию в 8 раз.

Автор:  alexus [ Четверг, 20 Октябрь, 2011 10:28 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов

Валерий Лаптев писал(а):
alexus писал(а):
В самом обмене нет никакой необходимости... если переформулировать (не меняя сути!) исходную для цикла задачу.
Исходная задача цикла: переставить удаленные элементы поближе к нужному месту.
... переставить элементы в порядке возрастания/убывания их значений.
Валерий Лаптев писал(а):
Делается это относительно некоего "разделяющего" элемента х.
... этот элемент иногда называют медианой...

Вопрос, который меня интересовал... почему медиану предпочитают выбирать из середины последовательности/массива. С точки зрения логики, любой элемент можно выбрать в качестве медианы, если исходить из того, что значения элементов распределены случайным образом. Таким образом, определять середину последовательности не обязательно, можно в качестве медианы использовать первый элемент последовательности, например.
Выбор медианы из середины последовательности, позволяет написать два цикла, первый будет просматривать элементы до медианы, второй, после медианы:
Код:
m := (left + right) div 2; // выбираем медианный элемент
x := a[m]; // получаем медиану
i := left;
j := right;
while (a[i] < x) do inc(i); // просматриваем левую часть
while (a[j] > x) do dec(j); // просматриваем правую часть
Можно легко убедиться, что оба этих цикля являются подмножествами более общего цикла, когда мы просматриваем обе части последовательности, поочередно, то слева, то справа... пока не найдём "нужное место" для медианного элемента. "Нужное место" - это то место, где слева будут находиться элементы со значениями не больше медианного значения, а справа, соответственно, будут находиться все элементы со значениями не меньше медианного значения. Таким образом, задача свелась к тому, что надо найти "нужное место", попутно перенося меньшие элементы влево, а большие элементы вправо. Но операция переноса, не тождественна операции обмена, это всего одно присваивание, а не три...

Автор:  Сергей Губанов [ Четверг, 20 Октябрь, 2011 10:42 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов

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

Автор:  alexus [ Четверг, 20 Октябрь, 2011 10:47 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов

Сергей Губанов писал(а):
Кстати, да, когда я сам давным давно в первый раз изобретал сортировку, то как раз пытался сделать её на "переносе", а не на "обмене". Потом начитался всяких Кнутов и забыл про перенос...
Потому может быть мне и нравилось писать на ассемблере... думать заставляет, особенно... таких ленивых, как я... :)

Автор:  Сергей Губанов [ Четверг, 20 Октябрь, 2011 10:50 ]
Заголовок сообщения:  Re: Оптимизация алгоритмов

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

Страница 1 из 4 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/