Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз

Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз Статьи


Картинка к вебинару и посту взята не просто так: в определенном смысле символьное ядро Wolfram Language можно сравнить с Таносом — если бы его мощь была бы направлена в правильное русло, он мог бы стать самым мощным и полезным "добряком". Так же и с символьным ядром Wolfram — его чудовищную мощь нужно правильно использовать, а если это делать не так, оно может стать настоящим "злом", замедляющим все очень сильно. Начинающие разработчики не знают многих важнейших парадигм, идей и принципов языка Wolfram Language, пишут код, который на самом деле дико неэффективен и после этого разочаровываются, хотя тут нет вины Wolfram Language. Эту ситуацию призвана исправить эта статья.

Мне довелось работать с Wolfram Language начиная с (уже довольно далекого) 2005 года (тогда еще была версия Mathematica 5.2, сейчас уже 12-я). За эти почти 15 лет произошло очень много: добавились тысячи новых встроенных функций и областей, в которых они работают (машинное обучение, точная геометрия, работа с аудио, работа в вебе, облачные возможности, глубокая поддержка единиц измерения, интеграция с базами данных Wolfram|Alpha, географические вычисления, поддержка работы с CUDA, Python, распараллеливание операций и многое многое другое), появились новые сервисы — облако Wolfram Cloud, широко известная система вычислительных значний Wolfram|Alpha, репозиторий функций, репозиторий нейросетей и пр.

За эти годы я применял Wolfram Language очень много (да, ранее, по сути, он назывался Mathematica, до того, как Стивен Вольфрам не решил выделить язык и сделать его общим для целой плеяды своих продуктов) и в разных областях: довелось делать модель продаж для фармацевтической компании; создавать парсеры и автоматические генераторы альбомов о фильмах для индустрии проката кино (когда они еще только зарождались); применять активно в науке (работы по химии и физике твердого тела и теории разрушения); разрабатывать прототипы обучающих систем для платформ отечественного школьного и вузовского образования и ведущих компаний и издательств на этом рынке в России.

Записи некоторых моих выступлений на MBLT DEV и конференциях Wolfram

Это, а вместе с тем то, что я уже несколько лет руковожу своей студией разработки, в которой мы применяем помимо Wolfram Language много чего: JavaScript, Python, Java, PHP и др. — дало мне возможность оценить язык Wolfram глубоко и понять области, в которых ему, пожалуй, особенно нет равных.

В этой статье, которая является компиляцией моего личного опыта и опыта потрясающего разработчика, который сделал очень много для ядра Wolfram Language — Леонида Шифрина (см., скажем, ответ к вопросу "Performance tuning in Mathematica?" — часть этой статьи является её адаптированным и расширенным переводом) — мне хотелось бы развеять мифы относительно скорости языка Wolfram Language — ведь часто разработчики просто, прошу прощения за прямоту, не умеют (не знают) как эффективно использовать его возможности.

Разработчики часто применяют неэффективные конструкции, не используют потрясающие возможности, вроде: распараллеливания, компиляции кода в C или байт-код Wolfram Language, интеграции с CUDA, другими языками вроде Java и C (да, можно подгружать код на этих языках прямо в Wolfram-код).

Это в целом неудивительно, ведь Wolfram Language дает уникальную свободу разработки. Вот, скажем, набор примеров, показывающий 15 способов задать факториал (обратите внимание, как сильно отличается время вычисления функций — показано в какое количество раз оно больше, чем у встроенной функции Factorial):

Код
In[1]:=
Module[{st, stInput, data, systemFunction}, 
st=Style[#, FontFamily->"Arial", Gray, FontSize->14]&;

SetAttributes[stInput, HoldAll];

stInput[code_]:=(Clear[f];

code;

{Style[HoldForm@code, "Input", FontSize->14, Background->None], code;

RepeatedTiming[f[9];

, 2][[1]]});

data=Flatten/@{
{st@"Ядро Wolfram", stInput[f=Factorial]}, 
{"", stInput[f[n_]:=n!]}, 
{st["Правила замены"], stInput[f[n_]:=n f[n-1];

f[1]=1]}, 
{st["Процедурный"], stInput[f[n_]:=Module[{t=1}, Do[t=t*i, {i, n}];

t]]}, 
{"", stInput[f[n_]:=Module[{t=1, i}, For[i=1, i<=n, i++, t*=i];

t]]}, 
{st["На списках (массивах)"], stInput[f[n_]:=Apply[Times, Range[n]]]}, 
{"", stInput[f[n_]:=Fold[Times, 1, Range[n]]]}, 
{st["Рекурсивный"], stInput[f[n_]:=If[n==1, 1, n*f[n-1]]]}, 
{st["Функциональный"], stInput[f=If[#1==1, 1, #1*#0[#1-1]]&]}, 
{"", stInput[f[n_]:=Fold[#2[#1]&, 1, Array[Function[t, #t]&, n]]]}, 
{st["Конструктивный"], stInput[f[n_]:=Length[Permutations[Range[n]]]]}, 
{st["Правила замены (шаблоны)"], stInput[f[n_]:=First[{1, n}//.{a_, b_/;

b>0}:>{b*a, b-1}]]}, 
{st["На строках"], stInput[f[n_]:=StringLength[Fold[StringJoin[Table[#1, {#2}]]&, "A", Range[n]]]]}, 
{st["Математический"], stInput[f[n_]:=Gamma[n+1]]}, 
{"", stInput[f[n_]:=Product[i, {i, n}]]}
};

systemFunction=data[[1, 3]];

Framed[#, Background->White, FrameMargins->5, FrameStyle->None]&@Grid[{Style[st[#], Bold]&/@{"Парадигма", "Код", "Медленнее встроенной\nфункции,  раз"}}~Join~({#[[1]], #[[2]], st[Round[#[[3]]/systemFunction, 1/10]//N]}&/@data), 
Alignment->{{Center, Left, Left}, Center}, 
Dividers->{None, {None, {LightGray}, None}}, Background->{None, {LightOrange, None}}
]]
Out[1]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз

Эта статья призвана помочь вам писать красивый и эффективный код, который будет работать ни чуть не медленнее, чем, скажем, в популярном Python. Знания этих принципов и приемов позмоляет писать код на Wolfram Language, который будет не особо медленнее кода на C, но за счет широты языка разработку вести в нем намного быстрее и проще.

В конце статьи вы найдете ссылки на полезные ресурсы для изучения языка Wolfram Language.

Поскольку Wolfram Language (Mathematica и другие системы, основанные на нем) — символьный язык программирования, который имеет символьный вычислительный движок, гораздо более общий, чем, скажем, в том же Matlab (Sympy, Maxima, Maple и пр.), неудивительно, что настройка производительных вычислений в нем иногда бывает более сложной. Существует, однако, множество техник, но все они сводятся, в основном, к главному принципу, который звучит так:

Избегайте полного цикла символьных вычислений в Wolfram Language, насколько это возможно.

1. Базовые принципы

1.1. Применяйте везде, где это возможно, встроенные функции

Так как они реализованы непосредственно в ядре Wolfram на низкоуровневых языках (С и Java), они обычно (но не всегда!) намного быстрее, чем созданные вами функции для решения той же задачи. Чем более специализированную функцию для конкретной задачи вы применяете, тем выше шансы, что вы ускорите код.

In[2]:=
ClearAll[data];

data=RandomReal[1, {10^6, 2, 2}];
In[3]:=
compareTiming[{Map[Flatten, data], Flatten[data, {{1}, {2, 3}}]}]
Out[3]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз

1.2. Используйте функциональное программирование (Map /@, Apply @@ и им подобные)

Также используйте чистые функции (лямбда-исчисление) на основе нотации #-&, когда это возможно — они, как правило, быстрее, чем функции функции с именованными аргументами (на основе Function) или функции, основанные на правилах замены (особенно для функций, не требующих интенсивных вычислений, которые применяются к большим спискам).

In[4]:=
ClearAll[data];

data=Range[1, 10^6];
In[5]:=
compareTiming[{f[x_]:=x^2;

Table[f[i], {i, data}], Map[#^2&, data]}]
Out[5]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз

1.3. Используйте структурные и векторизованные операции

Применяйте Transpose, Flatten, Partition, Part и т. п. — они быстрее, чем функциональные.

In[6]:=
ClearAll[data];

data=RandomReal[1, {10^5, 2}];
In[7]:=
compareTiming[{{#[[1]], #[[2]]^2}&/@data, Transpose[{#1, #2^2}&@@Transpose[data]]}]
Out[7]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз

1.4. Избегайте использования процедурного стиля программирования

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

In[8]:=
ClearAll[fibonacci, f];
In[9]:=
compareTiming[{fibonacci={1, 1};

n=3;

While[n<=20000, AppendTo[fibonacci, fibonacci[[n-1]]+fibonacci[[n-2]]];

n++];

fibonacci, f[1]=1;

f[2]=1;

f[n_]:=f[n]=f[n-1]+f[n-2];

f/@Range[20000]}]
Out[9]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз

2. Используйте машинную точность, всегда, когда это возможно

В большинстве языков программирования просто нет таких понятий, как точные константы, вроде 6/47 или каких бы то ни было символьных выражений. Поэтому применяя их нужно быть аккуратным и понимать, как работает процесс вычислений, чтобы не использовать абсолютную точность, когда это не нужно.

2.1. Не применяйте абсолютную точность там, где это не нужно

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

In[10]:=
compareTiming[{data=Table[{x, Sin[x]/Gamma[x]}, {x, 0, 10, 1/100}];

ListPlot[data], data=Table[{x, Sin[x]/Gamma[x]}, {x, 0, 10, 1/100.}];

ListPlot[data]}]
Out[10]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз

В примере выше изменено только одно место — 100 заменено на 100. — первое число имеет абсолютную точность, а второе — машинную. Но от этого вычисления ускорились в 4 раза! Вот, собственно, как выглядят данные.

In[11]:=
Table[{x, Sin[x]/Gamma[x]}, {x, 0, 10, 1/2}]
Table[{x, Sin[x]/Gamma[x]}, {x, 0, 10, 1/2.}]
Out[11]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз
Out[12]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз

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

2.2. Применяйте машинную точность до символьных преобразований

Также нужно помнить, что по умолчанию система делает все символьно и это может занять много времени. Скажем, вы хотите решить уравнение \(ax^3+bx+c=0\) при заданном наборе значений a, b, c. Вы можете сделать вот так:

In[13]:=
Solve[a x^3+b x+c==0, x]/.{a->1.23, b->3.45, c->2.6}
Out[13]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз

И вы удивитесь, почему чуть иначе написанный код будет быстрее в 15 раз:

In[14]:=
compareTiming[{Solve[a x^3+b x+c==0, x]/.{a->1.23, b->3.45, c->2.6}, Solve[a x^3+b x+c==0/.{a->1.23, b->3.45, c->2.6}, x]}]
Out[14]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз

Все дело как раз в том, что в первом примере Wolfram Language сначала ищет точное решение и затем подставляет в него численные значения коэффициентов:

In[15]:=
Solve[a x^3+b x+c==0, x]
Out[15]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз
In[16]:=
Solve[a x^3+b x+c==0, x]/.{a->1.23, b->3.45, c->2.6}
Out[16]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз

Во втором случае ищется решение сразу численными методами:

In[17]:=
a x^3+b x+c==0/.{a->1.23, b->3.45, c->2.6}
Out[17]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз
In[18]:=
Solve[a x^3+b x+c==0/.{a->1.23, b->3.45, c->2.6}, x]
Out[18]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз

2.3. Не мешайте числа с разной точностью

Если в вашем списке есть числа с разной точностью — он автоматически будет распакован и будет работать в сотни раз медленнее (см. ниже про упакованные массивы). Приводите числа к одинаковой точности с помощью таких функций как N, Rationalize, Round, Floor, Ceiling, SetPrecision, SetAccuracy.

3. Компиляция, листабилити, распараллеливание и CUDA

3.1. Помните про листабилити

Листабилити (Listability) — это применение функции к массиву, каждому её элементу автоматически. Так как в Wolfram Language массивы называются List — отсюда название. В принципе, можно назвать также это векторизацией.

Помните, что многие встроенные функции листабильны, а значит применение их к большим спискам предпочтительнее применения конструкций вроде Map или циклов.

In[19]:=
ClearAll[data];

data=RandomReal[{-Pi, Pi}, 10^7];
In[20]:=
compareTiming[{Sin/@data, Sin[data]}]
Out[20]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз

3.2. Используйте компиляцию на основе Compile

Используйте компиляцию всегда, когда это возможно. Применяйте компиляцию в C-код (для этого потребуется доустановить компилятор, можно установить Visual C++ Build Tools 2017 — подробнее о том, как это сделать, см. здесь). Делайте ваши компилированные функции листабельными (RuntimeAttributes) и распараллеленными (Parallelization).

In[21]:=
ClearAll[data];

data=Range[-50, 50, 0.001];

Оригинальная функция:

In[22]:=
fNotCompiled=Function[{x}, Block[{sum=1.0, inc=1.0}, Do[inc=inc*x/i;

sum=sum+inc, {i, 100}];

sum]];

Фунция, скомпилированная в байт-код Wolfram Language (JIT-компиляция) (далее будем ее называть JIT-функция)

In[23]:=
fJITCompiled=Compile[{{x}}, Block[{sum=1.0, inc=1.0}, Do[inc=inc*x/i;

sum=sum+inc, {i, 100}];

sum]];

JIT-функция с возможностью распараллеливания:

In[24]:=
fJITCompiledParallelized=Compile[{{x}}, Block[{sum=1.0, inc=1.0}, Do[inc=inc*x/i;

sum=sum+inc, {i, 100}];

sum], Parallelization->True];

JIT-функция с листабилити:

In[25]:=
fJITCompiledListable=Compile[{{x}}, Block[{sum=1.0, inc=1.0}, Do[inc=inc*x/i;

sum=sum+inc, {i, 100}];

sum], RuntimeAttributes->{Listable}];

JIT-функция с листабилити и распараллеливанием:

In[26]:=
fJITCompiledListableParallelized=Compile[{{x}}, Block[{sum=1.0, inc=1.0}, Do[inc=inc*x/i;

sum=sum+inc, {i, 100}];

sum], Parallelization->True, RuntimeAttributes->{Listable}];

Фунция, скомпилированная в код C (остальные аналогично):

In[27]:=
fСCompiled=Compile[{{x}}, Block[{sum=1.0, inc=1.0}, Do[inc=inc*x/i;

sum=sum+inc, {i, 100}];

sum], CompilationTarget->"C"];
In[28]:=
fСCompiledParallelized=Compile[{{x}}, Block[{sum=1.0, inc=1.0}, Do[inc=inc*x/i;

sum=sum+inc, {i, 100}];

sum], CompilationTarget->"C", Parallelization->True];

fСCompiledListable=Compile[{{x}}, Block[{sum=1.0, inc=1.0}, Do[inc=inc*x/i;

sum=sum+inc, {i, 100}];

sum], CompilationTarget->"C", RuntimeAttributes->{Listable}];

fСCompiledListableParallelized=Compile[{{x}}, Block[{sum=1.0, inc=1.0}, Do[inc=inc*x/i;

sum=sum+inc, {i, 100}];

sum], CompilationTarget->"C", Parallelization->True, RuntimeAttributes->{Listable}];

Теперь посмотрим на все варианты (по сути одной и той же функции!) работы функции и её разных компилированных версий. Как видно, ускорение просто от оборачивания функции и использования компиляции в C ускоряет её более чем в 50 раз!

In[31]:=
compareTiming[
{fNotCompiled/@data, 
fJITCompiled/@data, 
fJITCompiledListable@data, 
fJITCompiledParallelized/@data, 
fJITCompiledListableParallelized@data, 
fСCompiled/@data, 
fСCompiledListable@data, 
fСCompiledParallelized/@data, 
fСCompiledListableParallelized@data}]
Out[31]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз

Когда вы применяете Compile может случиться так, что компилированная функция имеет "утечки", когда часть вычислений перестает быть компилированной. Примеры борьбы с этим явлением вы можете найти в MathGroup.

3.3. Применяйте векторизированные операции внутри Compile

Когда это возможно, используйте векторизованные операции (UnitStep, Clip, Sign, Abs и т. д.) внутри компилированной функции, создаваемой с помощью Compile, чтобы реализовать конструкции "векторизованного порядка выполнения (блок-схемы)", такие как If, чтобы избежать явных циклов (по крайней мере, в самых глубоковложенных циклах) внутри Compile. Это может дать вам скорость уже не байт-кода Wolfram Language, а почти родную скорость C во многих случаях.

In[32]:=
f1Compiled=Compile[{{x, _Real}}, SeedRandom[1];

Block[{data}, data=RandomReal[{-x, x}, 10^5];

Table[If[data[[i]]>0, 1, 0], {i, 1, Length[data]}]], CompilationTarget->"C", Parallelization->True];

f2Compiled=Compile[{{x, _Real}}, SeedRandom[1];

Block[{data}, data=RandomReal[{-x, x}, 10^5];

UnitStep@data], CompilationTarget->"C", Parallelization->True];
In[34]:=
compareTiming[{f1Compiled@10, f2Compiled@10}]
Out[34]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз

3.4. Распараллеливание

Применяйте распараллеливание — для базовых нужд оно крайне просто реализовано, хотя есть множество настроек. Для начала просто запомните, главные функции: Parallelize, ParallelMap, ParallelTable.

In[35]:=
compareTiming[{Table[Solve[Sin[n x+n^2]==0, x], {n, 1, 100}], ParallelTable[Solve[Sin[n x+n^2]==0, x], {n, 1, 100}]}]
Out[35]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз

3.5. CUDA, OpenCL — вычисления с помощью графических процессоров (видеокарт)

Вы можете писать программы, основанные на технологиях CUDA и OpenCL. Производительность этих программ, естественно, будет соответствующей. Также можно использовать готовые программы на этих языках.

4. Имейте ввиду, что списки ({...} или List) реализованы в Wolfram Language, как массивы

4.1. Выделяйте большие списки, чтобы обрабатывать их "целиком", как описано выше.

Если у вас есть необходимость обрабатывать списки разного размера и содержимого, то особенно аккуратно нужно относиться к большим спискам. Иногда, список из 100-1000 элементов тоже может быть большим, например, если его элементами являются объекты XMLObject, получающиеся от импорта веб-страниц, каждый из которых весит килобайты, сотни килобайт или даже мегабайты.

4.2. Избегайте применять Append, Prepend, AppendTo и PrependTo в циклах

Не стоит применять функции Append, Prepend, AppendTo and PrependTo в циклах, для создания списков и т. п. — так как они создают копию всего списка, чтобы добавить единственный элемент, что приводить к квадратичной, а не линейной сложности конструирования списков.

In[36]:=
compareTiming[{list={};

n=1;

While[n<=10000, list=Append[list, n++]];

list, Range[1, 10000]}]
Out[36]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз

4.3. Используйте связанные списки

Применяйте "связанные списки" (конструкции, типа {1,{2,{3,{}}}}) вместо "плоских" списков (типа {1,2,3,4}) для накопления элементов списка в программах.

Простая конструкция для накопления элементов выглядит так: A = {new element, A}.

Так как A — это ссылка, отдельное присваивание осуществляется за одинаковое время.

In[37]:=
compareTiming[{list1={};

Table[If[PrimeQ[i], list1=list1~Join~{i}], {i, 1, 100000}];

list1, list2={};

Table[If[PrimeQ[i], list2={list2, i}], {i, 1, 100000}];

Flatten@list2}]
Out[37]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз

4.4. Сопоставление по шаблону в последовательности шаблонов

Не забывайте о том, что сопоставление по шаблону (Pattern matching) для шаблонов, задающих последовательность выражений (__ BlankSequence и ___ BlankNullSequence) также основывается на том, что последовательности (Sequence) являются массивами. Таким образом, скажем, правило {fst_,rest___}:>{f[fst],g[rest]} скопирует весь список и только потом будет применяться. В частности, не используйте рекурсию таким образом, который может выглядеть естественным в других языках. Если вы хотите использовать рекурсию в списках, сначала преобразуйте свои списки в связанные списки (см. выше).

5. Избегайте неэффективные шаблоны. Создавайте их правильно.

Для того, чтобы лучше понимать, что такое шаблоны (Patterns) в Wolfram Language рекомендую посмотреть мой урок:

5.1. Используйте аккуратно правила замены

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

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

Хорошим примером является сортировка элементов:

list //. {left___, x_, middle__, y_, right__} /; x > y :> {left, y, middle, x, right};

Незабывайте о SequenceCases, SequencePosition, SequenceCount, SequenceReplace, специально оптимизированных для работы с массивами, которые появились в версии 10.1 языка Wolfram.

5.2. Структуры данных и сопоставитель шаблонов

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

In[38]:=
ClearAll[data];

data=RandomInteger[{0, 100}, {10^6, 2}];
In[39]:=
compareTiming[{data/.{p:({x_/;

x>90&&PrimeQ[x], y_/;

y>34})/;

x^2+y^2>1000:>p, t:{_, _}:>Nothing}, ((data/.{_, y_/;

y<=34}:>Nothing)/.{x_/;

(x<=90||Not[PrimeQ[x]]), _}:>Nothing)/.({x_, y_}/;

x^2+y^2<=1000)->Nothing, 
Cases[Cases[Cases[data, {x_/;

x>90&&PrimeQ[x], _}], {_, y_/;

y>34}], {x_, y_}/;

x^2+y^2>1000]}]
Out[39]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз

5.3. Используйте аккуратно правила замены

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

In[40]:=
ClearAll[data];

data=RandomSample[{##}]&@@@Transpose[{RandomInteger[{0, 100}, 10^5], RandomReal[{0, 100}, 10^5]}];
In[41]:=
compareTiming[{Cases[data, {_Integer, x_/;

Sin[x]<FractionalPart[x]}], Module[{preData, seconds}, preData=Cases[data, {_Integer, _}];

seconds=Developer`ToPackedArray[preData[[;;, 2]]];

Pick[preData, UnitStep[FractionalPart[seconds]-Sin[seconds]], 1]]}]
Out[41]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз

6. Работа со списками

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

Одна универсальная встроенная функция, которая не создает копии списка (или выражения), а изменяет исходное выражение и не имеет этой проблемы — это [[...]] (Part).

6.1. Аккуратно применяйте функции, модифицирующие списки

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

In[42]:=
compareTiming[{NestWhile[Drop[#, 1]&, Range[1000], (Length[#]>10)&], Drop[Range[1000], 990]}]
Out[42]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз

6.2. Расширенный функционал Part

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

Простейший пример выглядит так:

In[43]:=
list={1, 2, 3, 4, 5};

list[[{1, 3}]]=list[[{4, 1}]];

list
Out[45]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз

Вот простой пример — изменить элементы списка в соответствии с заданным порядком:

In[46]:=
ClearAll[list1, list2];

list1=Range[1000000];

list2=list1;

newArrangement=RandomSample[list1];
In[50]:=
compareTiming[{list1=Table[list1[[i]], {i, newArrangement}];

list1, 
list2=list2[[newArrangement]];

list2}]
Out[50]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз

6.3. Используйте Extract

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

In[51]:=
ClearAll[list1, list2];

list=Range[10000000];

elems=RandomInteger[{1, 10000000}, 10000];
In[54]:=
compareTiming[{Table[list[[elems[[i]]]], {i, 1, Length@elems}], 
Extract[list, List/@elems]}]
Out[54]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз

7. Используйте эффективные встроенные форматы данных

7.1. Упакованные массивы

Для того, чтобы упаковать массив его достаточно обернуть в Developer`ToPackedArray. Чтобы проверить упакованность массива служит функция Developer`PackedArrayQ.

In[55]:=
ClearAll[data];

data=RandomInteger[{0, 1}, 10^6];

dataUnPacked=data~Join~{1.};

dataPacked=Developer`ToPackedArray[N[data]~Join~{1.}];
In[58]:=
compareTiming[{Total[dataUnPacked], Total[dataPacked]}]
Out[58]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз

7.2. Разреженные массивы

Безусловно, если ваша матрица разреженная, то, безусловно, держать её в памяти и обращаться к ней становится неэффективным. Для работы с такими объектами существует функция SparseArray.

In[59]:=
sparseArray=SparseArray[RandomInteger[{1, 100}, {100, 2}]->RandomReal[{0, 10}, 100], {100, 100}];

notSparseArray=Normal@sparseArray;

compareTiming[{Det@notSparseArray, Det@sparseArray}]
Out[61]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз

7.3. Хеш-таблицы

Начиная с версии 10 в Wolfram Language появились неизменяемые ассоциативные массивы , которые называются ассоциациями <|...|> (Association).

Тот факт, что они неизменяемы, не мешает им эффективно вставлять и удалять пары ключ-значение ("дешевые копии", отличающиеся от исходной ассоциации наличием или отсутствием данной пары ключ-значение). Они представляют собой идиоматические ассоциативные массивы в Wolfram Language и имеют очень хорошие характеристики производительности.

In[62]:=
assoc=<|a->1, b->2, c->3, d->4, e->5|>;
In[63]:=
assoc[d]+assoc[a]
Out[63]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз

Также не забывайте про Dataset — это объект, который можно назвать внутренним форматом базы данных языка Wolfram Language.

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

8. Применяйте кэширование, ленивые вычисления и динамическое программирование

8.1. Кеширование значений функций (мемоизация) и выгрузка определений функций на жесткий диск

Оно крайне просто реализовано в Wolfram Language и может сохранить вам просто астрономическое количество времени.

Простейший принцип работы выглядит так: вместо конструкции f[x_]:=functionBody используется f[x_]:=f[x]=functionBody — при этом функция не просто вычисляет значение при заданном значении аргумента, но и запоминает его. Поэтому вычисления требуются 1 раз, после этого их можно использовать и, если нужно, выгрузить на жесткий диск с помощью Save или DumpSave.

In[64]:=
ClearAll[f1, f2];

f1[x_]:=(Pause[0.1];

x^2);

f2[x_]:=f2[x]=(Pause[0.1];

x^2);

compareTiming[{f1/@{1, 1, 1, 1, 1}, f2/@{1, 1, 1, 1, 1}}]
Out[67]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз

8.2. Замыкания (closures)

Wolfram Language позволяет реализовать более сложные версии мемоизации, где вы можете определить функции (замыкания) непосредственно во время их выполнения, которые будут использовать некоторые предварительно вычисленные части в своих определениях и, следовательно, будут быстрее.

In[68]:=
ClearAll[f1, f2]
In[69]:=
f1[x_]:=(y/.Solve[y^2+x y+x==0, y]);
In[70]:=
Module[{solution=FullSimplify@Solve[y^2+x y+x==0, y]}, 
f2[xValue_]:=(y/.solution)/.x->xValue];
In[71]:=
compareTiming[{Table[f1[x], {x, 0, 100}], Table[f2[x], {x, 0, 100}]}]
Out[71]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз

8.3. Ленивые вычисления

Ленивые или отсроченные вычисления реализуются в Wolfram Language через конструкции := (SetDelayed), а для правил замены через :> (RuleDelayed). Они являются "естественными" для языка и позволяют вызывать функции, только когда они нужны и не вычислять их заранее, в отличие от заданий с помощью = (Set) и -> (Rule). Однако, важно понимать разницу и применять каждый тип верно.

In[72]:=
ClearAll[f1, f2]
In[73]:=
f1[x_]:=(y/.FullSimplify[Solve[y^2+x y+x==0, y]]);
In[74]:=
f2[x_]=(y/.FullSimplify[Solve[y^2+x y+x==0, y]]);
In[75]:=
compareTiming[{Table[f1[x], {x, 0, 100}], Table[f2[x], {x, 0, 100}]}]
Out[75]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз

9. Прочие замечания

9.1. Используйте сцепку функций Reap + Sow для сбора данных в процессе вычислений

Reap и Sow обеспечивают эффективный способ сбора промежуточных результатов, причем их можно "помечать" тэгами, для сбора необходимых результатов. Эти команды также хорошо сочетаются с функциональным программированием.

9.2. Все есть символьная констукция

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

In[76]:=
FullForm[{{1, 2}, {3, {4}}, {{5}}}]
Out[76]//FullForm=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз
In[77]:=
FullForm[Hold[x5+y2+1/z+4/2]]
Out[77]//FullForm=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз

9.3. Дуализм позиции и элемента

Часто вы можете написать более быстрые функции для работы с позициями элементов, а не с самими элементами, поскольку позиции являются целыми числами (для плоских списков). Это может дать вам ускорение на порядок даже по сравнению со встроенными функциями.

9.4. Отключите $HistoryLength

По умолчанию Wolfram Language помнит все вычисления, сделанные в текущей сессии. Это может сильно мешать работы и контролируется параметром $HistoryLength.

Преимущества языка Wolfram Language в скорости разработки

Мы подробно обсудили технические детали — как применяя те или иные приёмы ускорить код, или сразу писать его эффективным. Однако, есть одна важная сторона разработки на Wolfram Language, которая остается обычно незамеченной: высокая скорость разработки и прототипирования.

Дело в том, что внутри систем, таких как Wolfram Mathematica, Wolfram Cloud, Wolfram One и пр. реализована интерактивная среда разработки, которую вы можете кастомизировать под себя и делать то, что можно назвать "интерактивной книгой". Скажем эта статья изначально написана на Wolfram Language в Wolfram Mathematica, после не особенно сложный обработчик конвертирует документ, который готов полностью для публикации в моем блоге и здесь, на Хабре. Он делает все: готовит и выгружает иллюстрации на сервер, сохраняет документ в некскольких форматах, с учетом разницы платформ и пр.

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

Если коротко, то можно отметить следующие ключевые возможности, благодаря которым разработка на Wolfram Language экономит массу времени на разработке:

  • Гигантское количество встроенных функций, покрывающих очень много областей (от символьной математики (интегралов, рядов, доказательства теорем и геометрии) до географических вычислений или создания облачных сервисов). Для того, чтобы оценить этот функционал — просто откройте документацию и поизучайте её хотя бы минут 15, вы убедитесь в этом сами.

    На картинке ниже показаны области, в которых работает Wolfram Language вместе с количеством функций, которые относятся к этой области. Всего на данный момент (в версии 12.0) доступно 5436 функций из 188 областей. Под картинкой в спойлере вы можете посмотреть их перечисление по областям.

In[78]:=
data=SortBy[#, -Length[#]&]&@GroupBy[Flatten[Thread/@EntityValue[WolframLanguageData[], {"name"EntityProperty["WolframLanguageSymbol", "Name"]"EntityProperty[\"WolframLanguageSymbol\",  \"Name\"]"EntityProperty, "functionality areas"EntityProperty["WolframLanguageSymbol", "FunctionalityAreas"]"EntityProperty[\"WolframLanguageSymbol\",  \"FunctionalityAreas\"]"EntityProperty}], 1], Last, Sort[#[[;;, 1]]]&];
In[79]:=
Framed[Labeled[Style["Области применения Wolfram Language и количество функций,  относящихся к ним\n", 30, FontFamily->"Intro Regular"], #], Background->GrayLevel[0.95], FrameMargins->5, FrameStyle->None]&@WordCloud[KeyValueMap[{StringRiffle[StringCases[#1, RegularExpression["[A-Z][a-z]+"]]/."Symbols"->"", " "]<>" ("<>ToString[Length@#2]<>")", N@Length@#2}&, data], ImageSize->{1200, 800}, Background->GrayLevel[0.95], WordOrientation->{{-Pi/4, 0, Pi/4}}, MaxItems->All, WordSpacings->3, FontFamily->"Intro Regular"]
Out[79]=
Краеугольные камни уничтожения медленного кода в Wolfram Language: ускоряем код в десятки, сотни и тысячи раз
In[80]:=
Export[FileNameJoin[{NotebookDirectory[], "fileNames.nb"}], Notebook@Flatten@KeyValueMap[{Cell[#1<>" ("<>ToString[Length[#2]]<>")", "Title"], Cell[BoxData@ToBoxes@Row[Map[Hyperlink[#, "http://reference.wolfram.com/language/ref/"<>#<>".html"]&, #2], ",  "], "Text"]}&, data]];

Вспомогательные конструкции

In[81]:=
ClearAll[timing];

SetAttributes[timing, HoldAll];

timing[expr_]:=(ClearSystemCache[];

AbsoluteTiming[expr]);
In[84]:=
ClearAll[compareTiming];

SetAttributes[compareTiming, HoldAll];

compareTiming[expr_List, OptionsPattern[{"OrderQ"->True}]]:=Module[{t, v, c1, c2, holdExpr, colorF, order, rescale}, 
colorF=Blend[{ColorSwatchGraphicsFontCapHeightRGBColor[19255, 167255, 107255]DeployedRGBColorValueSelectorClosingActionsSelectionDepartureParentChangedEvaluatorQuitPreemptive, ColorSwatchGraphicsFontCapHeightRGBColor[1, 101255, 47255]DeployedRGBColorValueSelectorClosingActionsSelectionDepartureParentChangedEvaluatorQuitPreemptive}, #]&;

holdExpr=ReleaseHold@Map[HoldForm, HoldForm@expr, {2}];

{t, v}=Transpose[timing[ReleaseHold[#]]&/@holdExpr];

order=If[OptionValue["OrderQ"], Reverse[Ordering[t]], Range[1, Length[expr]]];

t=t[[order]];

rescale=Evaluate[Rescale[#, MinMax[t], {0, 1}]]&;

v=v[[order]];

holdExpr=holdExpr[[order]];

If[Length[DeleteDuplicates[v]]>1, Echo["Возможно неодинаковый результат работы программ"]];

Framed[Grid[{{Style[#, Bold]&@"Сравнение скорости работы программ на языке Wolfram Language"}, 
{Grid[{{"Код", "Время,  с"}}~Join~Table[{Style[holdExpr[[ind]], "Input", Background->Transparent], t[[ind]]}, {ind, 1, Length[expr]}], Alignment->{{Left, Center}, {Center, Center}}, Dividers->White, Background->{None, {LightGray}~Join~(colorF@*rescale/@t)}, ItemSize->{{30, 8}, Automatic}]}, 
If[Length[expr]==2, {Row[{"Код ускорен в ", Style[Round[Max[t]/Min[t], 1/100]//N, Bold], " раз"}]}, {Row[{"Максимальное ускорение кода ", Style[Round[Max[t]/Min[t], 1/100]//N, Bold], " раз"}]}], 
{Graphics[
Table[{Opacity[0.6], colorF@*rescale@t[[ind]], Rectangle[{0, 1-ind-0.2(ind-1)}, {t[[ind]], 2-ind-0.2(ind-1)}]}, {ind, 1, Length[expr]}], 
ImageSize->{500, Automatic}, PlotRange->{{0, Max[t]}, {1.2(1-Length[expr]), 1}}, AspectRatio->1/(9-Length[expr]/2), 
Axes->False, Ticks->{Automatic, None}, FrameTicks->{All, None}, 
GridLines->{Automatic, None}, Background->White, PlotRangePadding->0, Frame->True, FrameLabel->{{None, None}, {"Время,  с", None}}]}
}, 
ItemStyle->Directive[FontSize -> 14, FontFamily->"Open Sans Light"]], Background->White, FrameStyle->None]];

Оценить статью
Блог о Wolfram Mathematica

Оставить комментарий

avatar
  Подписаться  
Уведомление о