OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Среда, 16 Октябрь, 2019 15:31

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




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

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


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

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3093
Откуда: Астрахань
Мне вот пришлось.
Причем, сначала - скорость. По мере продвижения выяснилось, что не хватает 2 гига виртуальной памяти. Пришлось менять алгоритм для уменьшения требований по памяти.
Даже статью написал по программе... :)


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

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


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

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3093
Откуда: Астрахань
alexus писал(а):
В алгоритме быстрой сортировки, есть момент, когда происходит перестановка:
Код:
t := a[i];
a[i] := a[j];
a[j] := t;
Но если задуматься, то два из трёх присваиваний здесь излишни...

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


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

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

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


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

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


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

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


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

Зарегистрирован: Суббота, 12 Июль, 2008 22:49
Сообщения: 573
Откуда: Россия, Санкт-Петербург
Есть две ячейки памяти А и Б, зачем менять содержимое этих ячеек, если можно просто использовать далее вместо А, Б, а вместо Б, А? С точки зрения компьютера - это бесполезная трата ресурсов.


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

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

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

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

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


Вложения:
ЭФФЕКТИВНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА ДЖЕММИНГА.rar [476.15 КБ]
Скачиваний: 170
Статья-Лаптев.rar [42.04 КБ]
Скачиваний: 168
Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оптимизация алгоритмов
СообщениеДобавлено: Четверг, 20 Октябрь, 2011 09:02 
Аватара пользователя

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


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

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


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

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


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

Зарегистрирован: Суббота, 27 Февраль, 2010 23:34
Сообщения: 746
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];


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

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3093
Откуда: Астрахань
alexus писал(а):
В самом обмене нет никакой необходимости... если переформулировать (не меняя сути!) исходную для цикла задачу.

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


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

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2316
Откуда: Россия, Томск
Интересная тема!

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

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

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


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

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3093
Откуда: Астрахань
Да, из простых алгоритмов сортировка выбором - наилучшая. Там сравнений n^2, а перестановок только n - что и дает выигрыш. Сравнение-то это только одна команда процессора.
Кстати, в книге Бентли "обсасывается" бинарный поиск. Первая исходная версия и конечная оптимизированная различаются по быстродействию в 8 раз.


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

Зарегистрирован: Суббота, 27 Февраль, 2010 23:34
Сообщения: 746
Валерий Лаптев писал(а):
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); // просматриваем правую часть
Можно легко убедиться, что оба этих цикля являются подмножествами более общего цикла, когда мы просматриваем обе части последовательности, поочередно, то слева, то справа... пока не найдём "нужное место" для медианного элемента. "Нужное место" - это то место, где слева будут находиться элементы со значениями не больше медианного значения, а справа, соответственно, будут находиться все элементы со значениями не меньше медианного значения. Таким образом, задача свелась к тому, что надо найти "нужное место", попутно перенося меньшие элементы влево, а большие элементы вправо. Но операция переноса, не тождественна операции обмена, это всего одно присваивание, а не три...


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

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Кстати, да, когда я сам давным давно в первый раз изобретал сортировку, то как раз пытался сделать её на "переносе", а не на "обмене". Потом начитался всяких Кнутов и забыл про перенос...


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

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


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

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Иногда для ускорения программы (на порядок или на два порядка) надо кэшировать объекты для повторного использования. Возникает проблема на сколько большим сделать кэш и как его чистить. Я года четыре использовал всякие очень сложные хитрые кэши, а пару месяцев назад придумал чрезвычайно простое эффективное решение...


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

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


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

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


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

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