Теория оптимизации программ

[Sonic86]

Нашел свое преобразование в Вики: https://en.wikipedia.org/wiki/Loop-inva ... ode_motion - там тоже отсылают к Ахо, Сети, Ульману.

(Оффтоп)

rockclimber в сообщении #1101994 писал(а):

Sonic86 в сообщении #1101948 писал(а):

Язык взят исключительно для примера: он достаточно бедный и безглючный.

Я буквально пару недель назад напоролся на очень неприятный глюк (см. обсуждение тут). Это пока единственный известный мне глюк такого рода, но неприятно то, что типичная ошибка этапа компиляции вылезает только в рантайме. Другие языки такого себе не позволяют обычно. Oracle, насколько я знаю, в курсе, но считает, что это нормально. Случай не ваш конечно (раз вы в БД не лезете), просто, скорее, как иллюстрация того, что и на старуху бывает проруха.

Ой, да там достаточно того, что криво написанный group by не вылетает при компиляции. Ой не буду вспоминать.

rockclimber в сообщении #1101994 писал(а):

Sonic86 в сообщении #1101948 писал(а):

С таким же успехом я мог бы взять C++, Pascal, м.б. Delphi, Lua какой-нибудь - любой C-подобный процедурный язык.

Ну вот я бы не сказал, что с таким же успехом. Хоть я и фанат PL/SQL, но для вашей задачи он мало подходит, имхо. Может, вам все-таки что-то более классическое взять?

М.б. я вообще себе возьму какой-нибудь абстрактный примитивный язык с минимумом синтаксиса. Буду все писать процедурами вида pName(par1,...,parn);

mustitz в сообщении #1101983 писал(а):

Если это константное выражение, то да. Ну а так надо быть уверенным в том, составные части не изменились.

Ну да. Я опять повторюсь: я не привожу точные условия применения правила, поскольку они сильно будут зависеть от языка и м.б. еще чего-нибудь. Меня попросили привести примеры, я привел.

mustitz в сообщении #1101983 писал(а):

Если брать теорию, то мне больше нравится старый двухтомник Ахо, Ульман, «Теория синтаксического анализа, перевода и компиляции», 1978. Она более математична, чем книга Дракона. Там глава 11 (последняя во втором томе) как раз посвящена оптимизации.

Спасибо!

mustitz в сообщении #1101983 писал(а):

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

Спасибо! Нашел чего-то на хабре, почитаю. Интересно, сколько там цельной теории? Или это просто инструмент?

rockclimber в сообщении #1101994 писал(а):

mustitz в сообщении #1101983 писал(а):

Если от переменной явно или неявно взят адрес, или переменная может изменяться из другого потока?

Конкретно в PL/SQL этого нет.

Ой да, давайте без указателей, адресной арифметики и прочего насилия над мозгом. Не надо также ООП, классов, шаблонов, БД и еще что там есть, вполне достаточно арифметики и строк.

aa_dav в сообщении #1101966 писал(а):

Ну тот же Кнут незабвенный.

А том хотя бы какой? У меня до ИП Кнута руки дошли только до ГСЧ в середине 2-го тома.

aa_dav в сообщении #1101966 писал(а):

Как альтернативу я бы предложил https://ru.wikipedia.org/wiki/%D0%90%D0 ... 0%B8%D0%B7

Это больше плохо алгоритмизуемое искусство.
Вообще, вот я написал сортировку пузырьком. У меня даже близко нет ни одного преобразования, которое приводило бы к использованию метода "разделяй и властвуй". Потому то, что в Кормене описано - это пока как недоступное искусство. И там оно тоже неконструктивное. Т.е. там типа "возьмем такую-то задачу". Для нее внезапно есть вот такой-то алгоритм. Вот мы можем у него вычислить скорость. А откуда сам алгоритм взялся - непонятно. А в теории схем программ - там хоть преобразования есть.

Munin в сообщении #1102047 писал(а):

Под "оптимизацией" понимаются две сильно разные вещи:
- оптимизация порядка сложности алгоритма;
- оптимизация, не меняющая порядка сложности.

Примерно с 2000 года в программировании вырос и закрепился тезис, что первой заниматься нужно, а второй не нужно. <аргументы>

Sonic86, как видно по его примерам, под оптимизацией понимает вторую вещь. Ну так и не надо жаловаться, что она ушла в компиляторы.

Но важнее, конечно же, первая. Теории тут никакой нет, это дело творческое, максимум теория может помочь вычислить сложность алгоритма.

Я согласен полностью! И меня больше интересует все-таки первое, чем второе.

Maslov в сообщении #1101982 писал(а):

Sonic86, с какой целью оптимизируете?

С целью развлечения С целью удовлетворения любопытства, например.

Давайте я другой пример приведу, ладно (видимо, никто мне больше все равно не ответит).
Хочу я написать значит программу, которая решает мне судоку. Алгоритм решения я какой-то там себе представляю, он там частичный и все равно может упереться в небольшой перебор. Но писать его мне лень. Зато мне интересно написать программу, которая оптимизирует другие программы (пусть там немножко понижает асимптотику - уже хорошо). И пусть я ее написал. Беру я задачу судоку и переписываю ее в виде совершенно унылого тормозного кода

 A[1][1]=a11;
A[1][2]=a12;
...
A[9][9]=a99;

for(i1=1;i1<10;i1++){
...
    for(i81=1;i81<10;i81++){
      if(a11=i1 && ... && a81=i81){
        if(Все элементы в строках разные &&...){
          printf('решение');
        }
      }
    }
...
}

Далее беру я этот код и скармливаю программе-оптимизатору. Насколько сильного эффекта я могу добиться?

[Munin]

arseniiv в сообщении #1102069 писал(а):

Ну здрасьте. Нет, нужно.

Скажем так. Нужно, но гораздо реже, чем думают энтузиасты. Гораздо чаще это - ошибка, называемая premature optimization.

arseniiv в сообщении #1102069 писал(а):

Имеется в виду сравнительно высокоуровневая оптимизация: например, изменение структуры данных: вместо итератора, к примеру, дерево какое, если нужно постоянно узнавать, содержится ли в множестве элемент.

Это как раз пример первой :-)

[_Ivana]

Sonic86 в сообщении #1102134 писал(а):

Далее беру я этот код и скармливаю программе-оптимизатору. Насколько сильного эффекта я могу добиться?

Если программа-оптимизатор посерфит в гугле алгоритмы обхода графов в ширину и глубину, зарегистрирует логин на каком-нибудь компьютерном форуме и создаст там тему с таким вопросом, проанализирует ответы и выберет лучший - то можно добиться достаточно сильного эффекта

[Maslov]

Sonic86 в сообщении #1102134 писал(а):

Далее беру я этот код и скармливаю программе-оптимизатору. Насколько сильного эффекта я могу добиться?

Если Ваша программа-оптимизатор работает на уровне локальной оптимизации кода (типа правил, описанных Вами в стартовом посте), то, боюсь, никакого. Никакой оптимизатор не сможет преобразовать грубый перебор во что-то более рациональное. В частности, ни одно из Ваших правил не сможет превратить $O(n)$ в $O(\log n)$

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

Хотя... вон какие штуки люди делают: https://habrahabr.ru/post/236689/

Цитата:

Автоматическая оптимизация алгоритмов с помощью быстрого возведения матриц в степень
Пусть мы хотим вычислить десятимиллионное число Фибоначчи программой на Python. Функция, использующая тривиальный алгоритм, на моём компьютере будет производить вычисления более 25 минут. Но если применить к функции специальный оптимизирующий декоратор, функция вычислит ответ всего за 18 секунд (в 85 раз быстрее)

Дальше - про содержательную оптимизацию питонного байт-кода.

[Xaositect]

Sonic86 в сообщении #1102134 писал(а):

Вообще, вот я написал сортировку пузырьком. У меня даже близко нет ни одного преобразования, которое приводило бы к использованию метода "разделяй и властвуй". Потому то, что в Кормене описано - это пока как недоступное искусство. И там оно тоже неконструктивное. Т.е. там типа "возьмем такую-то задачу". Для нее внезапно есть вот такой-то алгоритм. Вот мы можем у него вычислить скорость. А откуда сам алгоритм взялся - непонятно. А в теории схем программ - там хоть преобразования есть.

Я когда-то видел статью, в которой описывался переход от сортировки вставками до сортировки слиянием, но сейчас хоть убей не могу ее нагуглить. Была она вроде в каком-то месте, связанном с функциональным программированием, возможно, ICFP. Дело там шло примерно так: сортировка вставками - это свертка $\operatorname{sort}([x_1, x_2, \dots,x_n]) = \operatorname{insert}(x_n,\dots,\operatorname{insert}(x_2, \operatorname{insert}(x_1, []))\dots)$. От перестановки в последовательности иксов у нас результат не меняется, по определению сортировки. Значит, есть некоторая коммутативная ассоциативная операция $\operatorname{merge}(xs, ys)$, для которой $\operatorname{insert}$ является частным случаем когда $xs = [x]$. Дальше мы берем и заменяем эти самые $\operatorname{insert}$ в сортировке на $\operatorname{merge}$ и с помощью ассоциативности реорганизуем дерево свертки из такого: $\xymatrix{ & \bullet\ar[d] & \bullet\ar[d] & \dots & \bullet\ar[d] & \bullet\ar[d] \\ \bullet\ar[r] & \bullet\ar[r] & \bullet\ar[r] & \dots\ar[r] & \bullet\ar[r] & \bullet}$ в сбалансированное.

[mserg]

Записываем задачу сортировки математически.

Дано: вектор целых (для определенности) чисел $a$ длины $N$.
Найти функцию $f:1..N \rightarrow 1..N$ такую, что
1. $f$ - биекция
2. $y_{i-1} \le y_i$, где $i = 1, 2, …, N-1$, $y=a(f(<1,2,…,N>))$

Данная задача решается алгоритмом перебора всех возможных функций (это примерно $O(N^N)$) и в выборе такой $f$, что выполняются все условия.

Поиск более эффективного вычисления функции $f$ состоит в эквивалентном преобразовании математической постановки задачи. Т.е. нужно выбрать набор разрешенных закорючек для таких преобразований и указать, каким образом вычисляется функция по ее математической формулировке. Например: если в описании задачи/подзадачи имеем не равенство, то это перебор.

Если хочется теории, как все это может производиться корректно, полно и т.п., то получится труд а-ля Бурбаки. Проблемы эффективности поиска рассматривать не будем, т.к. ТС спрашивал про теорию.

На этом постановка задачи не заканчивается, т.к. нужно оценивать, насколько каждый вариант вычисления функции $f$ нам подходит. Для этого требуется иметь репозиторий исходных данных (множество векторов $a$). Его также можно назвать "обучающим набором данных". Репозиторий должен содержать данные, отражающие "модель" применения функции $f$ на «практике».

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

Задача состоит в переборе суть эквивалентных алгоритмов и выборе минимума по критерию оптимальности. При этом можно вспомнить про переобучение и другие прелести, которые характерны для задач обучения: алгоритм будет прекрасно работать на обучающих примерах, а если подсунуть пример не из обучающего множества, то он будет работать медленно.

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

[arseniiv]

(Оффтоп)

Munin в сообщении #1102143 писал(а):

Гораздо чаще это - ошибка, называемая premature optimization.

Мне подумалось, об этом в теме сейчас, наверное, все знают, и потому можно считать, что речь не о ней.

[mustitz]

Sonic86 в сообщении #1102134 писал(а):

Ну да. Я опять повторюсь: я не привожу точные условия применения правила, поскольку они сильно будут зависеть от языка и м.б. еще чего-нибудь. Меня попросили привести примеры, я привел.

Я не верю, что существует некоторая общая «оптимизация» в вакууме. Все приёмы, как мне кажется, очень сильно привязаны к конкретному языку программированию. Если брать чистый C, то использование указателей превращает оптимизацию в ад. Поэтому там надо пользоваться const и restrict, иначе чуть ли не каждая операция будет сбрасывать значения всех переменных. Проблема в том, что большинство языков требуют/допускают интеграцию с C, и тут становится вопрос, что важнее: оптимизация или интеграция? Потому что любое обращение к внешней С-процедуре может изменить всё. С другой стороны есть Haskell и функциональные языки, где нет изменяемых переменных, и, как следствие, открываются большие просторы оптимизации. Посредине стоит Ada 2012, где есть контрактное программирование, можно доказать некоторые свойства программы, ...

Sonic86 в сообщении #1102134 писал(а):

mustitz в сообщении #1101983 писал(а):

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

Спасибо! Нашел чего-то на хабре, почитаю. Интересно, сколько там цельной теории? Или это просто инструмент?

Просто инструмент, читай универсальный ассемблер, которые может быть перекодирован в любой другой. Соответственно, оптимизация только на уровне ассемблерного кода.

Sonic86 в сообщении #1102134 писал(а):

Беру я задачу судоку и переписываю ее в виде совершенно унылого тормозного кода

...

Далее беру я этот код и скармливаю программе-оптимизатору. Насколько сильного эффекта я могу добиться?

Не думаю, что эффект будет сильный :) Это уже ближе к автоматическому доказательству теорем, потому как надо менять алгоритм. А потом доказать их эквивалентность. Мне так видится.