Pull to refresh

Comments 20

OsipovRoman, большое спасибо за статью! Она действительно очень полезная и практичная!


К пункту 1.2


В этом совете основной посыл состоит в том, что надо использовать функциональную парадигму при необходимости применить функцию к списку. Однако, показанный эффект ускорения достигается совершенно не этим. Дело в том, что в случае с Map[#^2&, data] ускорения достигается благодаря комбинации чистая функция + встроенный цикл + упакованный массив, когда Математика встречает такую конструкцию, то применяет автокомпиляцию, которая и дает ускорение. Соответственно если использовать "шаблонную" функцию + цикл + упакованный массив — автокомпиляция не используется. И в конкретно этом случае применение Map/Table не даст разницы во времени выполнения.



Также на скриншоте видно, что нет разницы между использование чистой функции в полной записи Function[x, x^2] и в короткой #^2&. Действительно разница во времени вычисления есть при применении любой функции к неупакованному массиву при помощи Map и Table. Table проигрывает в этом случае и это не зависит от того, чистая была функция или шаблонная.


К пункту 1.4


На мой взгляд сравнение проведено некорректно. Опять же в заголовке сказано про процедурный стиль, но эффект, который дает такую разницу во времени заключается в другом. Первая операция выполнялась медленно не из-за While, а из-за медленной операции вставки. Так как списки в Математике неизменяемы, то вставка нового элемента всегда происходит с пересозданием списка целиком. Зная это тот же самый код можно переписать вот так:



Т.е. здесь заранее создается массив на 20000 целых чисел, а затем заполняется. И как теперь видно проблема была не в цикле While. Хотя без сомнения код на скриншоте не самый идеологически хороший. А что касается ускорения во втором случае — здесь была использована рекурсия с мемоизацией. Для человеческого глаза это понятнее, также не создается никаких дополнительных списков, куда надо вставлять значения и ничего не перепутать. Однако этот способ сохраняет все 20000 значений в определении. Поэтому, например, повторный вызов f /@ Range[20000] вообще должен выполнится за нулевое время, но в итоге выполнится за константное время, которое требуется на получение списка значений из памяти:



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


К пункту 3.2


Здесь мне хочется добавить, что использовать Parallelization -> True и Listable отдельно не имеет никакого смысла. Эти две опции (как показывают эксперименты) дают эффект ускорения только при совместном использовании. Я думаю популярное слово "параллелизация" введет читателей в заблуждение. Она есть, но применяется исключительно при применении к списку аргументов. Соответственно список делится на равные части по числу процессорных ядер и функция вызывается на каждом ядре попеременно для всех элементов. Если передавать один аргумент — этого эффекта не будет. Т.е. вот так cfunc[{1, 2, 3, 4}] — функция вычислит значение на каждом ядре отдельно, а вот так: {cfunc[1], cfunc[2], cfunc[3], cfunc[4]} уже нет. И еще одно замечание: fJITCompiledListable — определение этой функции не соответствует заявленному, потому что в нем по умолчанию будет также Parallelization -> True. Чтобы функция принимала на вход список и к каждому элементу применялась на одном ядре необходимо принудительно указывать False. На скриншоте ниже показано, что использование двух опций отдельно эквивалентно их отсутствию, если оценивать по скорости. И только комбинация опций дает ускорение в число раз равное количеству ядер:



Еще одним способом ускорить скомпилированную функцию является возможность оптимизации выражений, когда повторяющиеся части выражения вычисляются только один раз. Например в коде ниже это x^2:



Чтобы убедиться в том, что повторяющиеся части выражения действительно были заменены посмотрим на "псевдобайткод" скомпилированных функций:



И последнее про компиляцию при помощи Compile. Не всякое выражение будет скомпилировано. Существует определенный список валидных функций, которые можно использовать в выражениях внутри Compile. Посмотреть на него можно вот так:


Needs["Compile`"]
Compile`CompilerFunctions[]

Еще одной тема, которой не хватает для полноты картины и раскрытия компиляции в Wolfram Language — это экспериментальные функции в версии Wolfram Language 12.0: FunctionCompile, KernelFunction и связанные с ними. На мой взгляд одним из преимуществ данных функций является возможность более строгого указания типов входных аргументов и типа результата, а также добавлена возможность безболезненно использовать вызов встроенной функции ядра Математики внутри скомпилированной.


Спасибо всем, кто дочитал этот комментарий и очень надеюсь, что кому-то поможет это небольшое дополнение по теме компиляции выражений в Wolfram Language.

Кирилл, спасибо за отличный комментарий! Вы отлично уточнили эти пункты.

Безусловно все в одну статью невозможно запихнуть, а если углубляться в дебри, то можно написать хороший томик)

Перед собой я ставил главную цель: продемонстрировать на простых примерах главные краеугольные камни ускорения кода в Wolfram Language. Ведь, как я в статье постарался сфокусировать внимание читателя на том, что медленность Wolfram Language это миф. К сожалению, у нас пока что мало знают об этом языке.

Отрадно, что вы, очевидно, глубоко в теме)!
К сожалению, у нас пока что мало знают об этом языке
Я бы даже сказал, что WL — самый недооценённый язык на текущий момент, причём за пропаганду Mathematica мне никто ничего не платит))

Я думаю, что политика продвижения Mathematica и WL не совсем верная. Не нужно упирать на то, насколько он крут и в нём можно сделать всё, что угодно — это вызывает скорее отторжение. Пользователь должен сам осознать и сделать свой выбор без давление извне.

Противопоставлять Mathematica нужно прежде всего Matlab-у и Mathcad-у — это наиболее популярные инструменты для прототипирования и символьных расчётов. Я сам пришёл к Mathematica тогда, когда Mathcad не смог решить какое-то уравнение, и поначалу было непросто приспособиться к новому синтаксису. Но когда приспособился, он вдохновил меня настолько, что я решил разориться на лицензионную версию — не для работы, а для личного пользования, и если сравнивать с Matlab-ом — цена действительно смешная.

Продвигать Mathematica нужно (как мне кажется) не для уже сформировавшихся разработчиков, а для школьников и студентов, у которых всё ещё впереди. Чтобы он привык в любой непонятной ситуации открывать Mathematica или документацию к Mathematica (которой тоже нету равных по содержательности).
Я бы даже сказал, что WL — самый недооценённый язык на текущий момент, причём за пропаганду Mathematica мне никто ничего не платит))

Целиком согласен. Регулярно говорю об этом и требуется подчас потратить немало сил, чтобы убедить заказчика его использовать. Но потом ситуация меняется, когда распробуют)

Продвигать Mathematica нужно (как мне кажется) не для уже сформировавшихся разработчиков, а для школьников и студентов, у которых всё ещё впереди

Да, это разумно, безусловно. Как и то, что вы написали на тему Matlab, Maple, к которым я добавил бы еще Maple, скажем, и вещи, типа SymPy.
По-моему, тут не хватает самой главной рекомендации — не используйте списки и рекурсию там, где они не нужны явным образом. Использовать списки для рекурсивного нахождения чисел Фибоначчи — это треш, за это нужно бить палкой по голове. Вы можете не знать, что в WL есть встроенная функция для чисел Фибоначчи, но вы обязаны знать, что в WL есть решатель рекуррентных уравнений! Пишите
RSolve[{f[n + 2] == f[n] + f[n + 1], f[1] == f[2] == 1}, f, n]
получите ответ
{{f -> Function[{n}, Fibonacci[n]]}}
его и используйте. Если вы не знаете, что значит «Fibonacci» — пишите
Fibonacci[n] // FunctionExpand
получите формулу в явном виде
((1/2 (1 + Sqrt[5]))^n - (2/(1 + Sqrt[5]))^n Cos[Pi n])/Sqrt[5]

Если вам действительно нужен список из чисел Фибоначчи — не используйте примеры из статьи. Используйте
Table[Fibonacci[n], {n, 10}]

По-моему, тут не хватает самой главной рекомендации — не используйте списки и рекурсию там, где они не нужны явным образом. Использовать списки для рекурсивного нахождения чисел Фибоначчи — это треш, за это нужно бить палкой по голове. Вы можете не знать, что в WL есть встроенная функция для чисел Фибоначчи, но вы обязаны знать, что в WL есть решатель рекуррентных уравнений!

Думаю вы это не мне писали, а сообществу. В противном случае это просто смешно, так как эти функции я давно популяризирую.

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

Рад, что в комментариях это отмечено. На канале у меня скоро выйдут ролики про FindSequenceFunction и RSolve, хотя там много функций, для поиска всяких зависимостей в последовательностях. А решение рекуррентных уравнений — это то, на чем все это базируется.

Если вам действительно нужен список из чисел Фибоначчи — не используйте примеры из статьи. Используйте
Table[Fibonacci[n], {n, 10}]

А вот тут вы жесткоко ошибаетесь. Встроенная функция медленная, весьма. Она может помимо чисел генерировать полиномы Фибоначчи, тут она может помочь. А так представленный способ быстр, причем чем больше нужно чисел, тем в большее число раз.


Думаю вы это не мне писали, а сообществу
Конечно, это я не вам лично писал — это просто комментарий, отражающий некоторые идеи, возможно ошибочные. Как я об этом узнаю, если буду держать их при себе?

1) «преждевременная оптимизация — корень всех зол» ©. Кто не согласен, пусть первым кинет в меня камень. Наглядность важнее, особенно при прототипировании.

2) способность WL решать рекуррентные уравнения вообще говоря не очевидна — я сам о ней узнал чисто случайно, и примеры с рекурсивным вычислением факториала этому никак не способствуют.

3) использовать WL игнорируя всю мощь его символьного движка — это примерно то же самое, что использовать компилятор с++ не используя классы, перегрузку операторов, умные указатели, шаблоны и всё такое. Так и тут возникает закономерный вопрос — а зачем вообще нужен WL, если это всё точно так же реализуется на c/c++/c#/python и наверняка будет работать ещё быстрее?

А вот тут вы жесткоко ошибаетесь. Встроенная функция медленная, весьма.
По-моему, это очевидный недостаток языка или его реализации конкретной версии — учитывая, что сам Леонид Шифрин постоянно твердит «используйте встроенные функции, если они есть, и не изобретайте велосипеды», да и вы здесь же пишете «используйте функциональное программирование». Если у нас рекуррентная последовательность определена как функция — мы можем использовать её в качестве аргумента, интегрировать/дифференцировать, делать подстановки и всё такое.
1) «преждевременная оптимизация — корень всех зол» ©. Кто не согласен, пусть первым кинет в меня камень. Наглядность важнее, особенно при прототипировании.

И да и нет. Смотрите: когда я руководил на протяжении почти 3 лет разработкой очень большого продукта образовательного (издательство Баласс) регулярно приходилось искать компромисс между качеством и скоростью: часто разработчики хотят сделать круто, и это очень ценно. Но часто решение нужно уже сегодня, как говорится. Поэтому приходится часто откидывать «оптимизацию» и её продумывание до рефакторинга, потому что тратить время и деньги сейчас нецелесообразно.

Проблема в том, что оптимизация может съесть больше времени, чем будет от нее выхлоп. Если речь идет о решении, использующемся здесь и сейчас — то нет смысла особенно морочиться и оптимизировать его. Напротив — если решение используется постоянно и, тем более, очень многими людьми — то чем больше в начале продумаешь и оптимизируешь, тем лучше.

2) способность WL решать рекуррентные уравнения вообще говоря не очевидна — я сам о ней узнал чисто случайно, и примеры с рекурсивным вычислением факториала этому никак не способствуют.

Да, как и многие вещи, поэтому нужно больше листать справку)))

По-моему, это очевидный недостаток языка или его реализации конкретной версии — учитывая, что сам Леонид Шифрин постоянно твердит «используйте встроенные функции, если они есть, и не изобретайте велосипеды».....

Да, все так, но как говорится — у каждого правила есть исключение.

Вам когда нибудь нужно было хотя бы 100 чисел Фибоначчи? Мне пока нет.

Так что для 99,(сколько-то девяток)% пользователей встроенной функции хватит, как и производительности). А тем, кому нужен триллион этих чисел — можно использовать другой алгоритм или поморочиться и получить формулу)
У меня, кстати, есть один интересный пример оптимизации исключительно на символьном движке и реальной, а не гипотетической задачи. Она упоминается вскольз в статье, которая сейчас в разработке, но возможно, стоит её выделить и рассмотреть отдельно? Правда, тогда интрига из статьи пропадёт.
Можете мне скинуть, обещаю сохранить авторское право и тайну)))
Там если всё подробно расписывать, на полноценную статью потянет) А вкратце примерно так:

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

Оптимизация заключается в том, что преобразование Фурье мы делаем сразу, интегрирование заменяется делением на i ω, смещение — умножением на комплексную экспоненту, сложение остаётся сложением, масштабирование пересчитывается (разово) через решение системы уравнений. В итоге на всё про всё, включая упрощение (куда же без него) тратится лишь несколько секунд.
Вспомнил про ещё одну оптимизацию, которую делал — свёртки, когда заранее известно, что сворачиваемые функции состоят из суммы косинусов, ограниченных прямоугольной функцией. Посчитал сначала свёртку для двух косинусов с произвольными множителями, нашёл пределы для граничных случаев, приводящих к обнулению знаменателя и выделил это всё в отдельную функцию. Минуты ожидания сменились на секунды.

Да, это круто!
Просто это такая, назовем её, "научная оптимизация".
Это безусловно круто, если так получается, но очевидно это требует много таланта.
Статья же посвящена больше приемам оптимизации, которые будут работать независимо от того, насколько круто программист умеет что-то упрощать с точки зрения теории и науки.
В целом я описал свой взгляд уже выше)
Я только сейчас заметил, что неудачно выбрал форму для обезличенного обращения и тот комментарий прозвучал намного грубее, чем в него закладывалось) Прошу прощения.
Да, хочу заметить, что встроенная функция LinearRecurrence отлично справляется с рекуррентными последовательностями.

Последовательность Фибоначчи в ней будет задаваться как:

LinearRecurrence[{1, 1}, {1, 1}, n]


Эта конструкция еще примерно в 2 раза быстрее чем та, что основана на мемоизации. Особенно, если использовать приближенные начальные значения и потом их перевести в целые:

LinearRecurrence[{1, 1}, N@{1, 1}, n]
Теперь нюансы — так, как они видятся лично мне.

1) с плавающей точкой (машинной точности) с последующим округлением точно можно вычислить только первые 71 значений — затем разрядности перестанет хватать. Это неочевидное и не интуитивное ограничение — лично мне казалось, что несколько сотен уж точно в double должно поместиться.

2) условия задачи изменились и нужно вычислять не каждое значение последовательности — а через раз, два, n или с простым порядковым номером. Как для этого модифицировать параметры LinearRecurrence — непонятно.

3) нужно решить обратную задачу — найти порядковый номер элемента через его значение, заданным с некоторой погрешностью — скажем, 100000. Сделать это без аналитической функции в разы сложнее.
Вы говорите о преимуществах точной зависимости — они, конечно, бесспорны. Особенно если зависимость проста.

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

Конечно для решения того, о чем вы пишите аналитическая зависимость прекрасна, я по-моему с этим и не спорю, а подтверждаю.

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

А есть ли в Wolfram Mathematica профайлер?
Чтобы сначала написать понятно, потом посмотреть что тормозит и оптимизитовать именно это место?

Wolfram Programming Lab — бесплатная лаборатория программирования Wolfram для изучения языка Wolfram Language

А как можно использовать её бесплатно? Я посмотрел на страницу с ценами — там только платно

Only those users with full accounts are able to leave comments. Log in, please.