Разница между функциями и сопоставлением шаблонов в Mathematica

Ответ 1

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

Из этого следует, что чем меньше раз вам приходится проходить список правил, тем быстрее оценка. Посмотрите, что происходит с помощью Trace (используя gdelfino функцию g и h)

In[1]:= [email protected](#*#)&@x
Out[1]= {x x,x^2}
In[2]:= [email protected]@x
Out[2]= {g[x],x x,x^2}
In[3]:= [email protected]@x
Out[3]= {{h,Function[{x},x x]},Function[{x},x x][x],x x,x^2}

становится понятно, почему анонимные функции быстрее всего, и почему использование Function вводит дополнительные накладные расходы по простой SetDelayed. Я рекомендую посмотреть отличную книгу Леонида Шифрина , где эти понятия объясняются в деталях.

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

Ответ 2

Я понимаю, что первый подход является чем-то эквивалентным макросу lisp, и по моему опыту предпочтение отдается более сжатому синтаксису.

Не совсем. Mathematica - это термин переписывающий, как и макросы lisp.

Итак, у меня есть два вопроса: существует ли разница в производительности между выполнением функций по сравнению с методом сопоставления шаблонов/макросов?

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

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

In[1] := [email protected][100000];

In[2] := Sqrt[xs]; // AbsoluteTiming

Out[2] = {0.0060000, Null}

Мы могли бы определить глобальное правило перезаписи, которое имеет термины вида sqrt[x], переписанные на sqrt[x], так что вычисляется квадратный корень:

In[3] := Clear[sqrt];
         sqrt[x_] := Sqrt[x];
         Map[sqrt, xs]; // AbsoluteTiming

Out[3] = {0.4800007, Null}

Обратите внимание, что это ~ 100 × медленнее предыдущего решения.

В качестве альтернативы мы могли бы определить глобальное правило перезаписи, которое заменяет символ Sqrt на лямбда-функцию, которая вызывает Sqrt:

In[4] := Clear[sqrt];
         sqrt = Function[{x}, Sqrt[x]];
         Map[sqrt, xs]; // AbsoluteTiming

Out[4] = {0.0500000, Null}

Обратите внимание, что это ~ 10 × быстрее, чем предыдущее решение.

Почему? Поскольку медленное второе решение ищет правило перезаписи sqrt[x_] :> Sqrt[x] во внутреннем цикле (для каждого элемента массива), тогда как быстрое третье решение разыскивает значение Function[...] символа Sqrt один раз, а затем применяет эту лямбда многократно. Напротив, самым быстрым первым решением является цикл, вызывающий Sqrt, написанный на C. Таким образом, поиск глобальных правил перезаписи чрезвычайно дорог, и переписывание терминов является дорогостоящим.

Если да, то почему Sqrt когда-либо быстро? Вы можете ожидать замедление 2 × вместо 10 ×, потому что мы заменили один поиск для Sqrt двумя поисками для Sqrt и Sqrt во внутреннем цикле, но это не так, потому что Sqrt имеет особый статус быть встроенной функцией, которая будет сопоставляться в ядре самого переписывающего терминатора Mathematica, а не через глобальную таблицу перезаписи общего назначения.

Другие люди описали гораздо меньшие различия в производительности между подобными функциями. Я считаю, что различия в производительности в этих случаях - лишь незначительные различия в точном внедрении внутренних компонентов Mathematica. Самая большая проблема с Mathematica - глобальная таблица перезаписи. В частности, именно здесь Mathematica расходится с традиционными переводчиками на уровне терминов.

Вы можете много узнать о производительности Mathematica, написав мини-решения Mathematica. В этом случае вышеупомянутые решения могут быть скомпилированы (например) F #. Массив может быть создан следующим образом:

> let xs = [|1.0..100000.0|];;
...

Встроенная функция Sqrt может быть преобразована в замыкание и задана функции map следующим образом:

> Array.map sqrt xs;;
Real: 00:00:00.006, CPU: 00:00:00.015, GC gen0: 0, gen1: 0, gen2: 0
...

Это занимает 6 мс, как Sqrt[xs] в Mathematica. Но этого следует ожидать, потому что этот код был JIT, скомпилированный до машинного кода .NET для быстрой оценки.

Поиск правил перезаписи в глобальной таблице перезаписи Mathematica аналогичен поиску закрытия в словаре с ключом по имени его функции. Такой словарь можно построить таким образом в F #:

> open System.Collections.Generic;;
> let fns = Dictionary<string, (obj -> obj)>(dict["sqrt", unbox >> sqrt >> box]);;

Это похоже на структуру данных DownValues в Mathematica, за исключением того, что мы не выполняем поиск нескольких результирующих правил для первого, совпадающего с аргументами функции.

Затем программа становится:

> Array.map (fun x -> fns.["sqrt"] (box x)) xs;;
Real: 00:00:00.044, CPU: 00:00:00.031, GC gen0: 0, gen1: 0, gen2: 0
...

Обратите внимание, что мы получаем аналогичное ухудшение производительности 10 × из-за поиска хэш-таблицы во внутреннем цикле.

Альтернативой было бы сохранить DownValues, связанный с символом в самом символе, чтобы избежать поиска в хеш-таблице.

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

> type expr =
    | Float of float
    | Symbol of string
    | Packed of float []
    | Apply of expr * expr [];;

Обратите внимание, что Packed реализует упакованные списки Mathematica, т.е. распакованные массивы.

Следующая функция init создает a List с элементами n, используя функцию f, возвращая Packed, если каждое возвращаемое значение было Float или более общим Apply(Symbol "List", ...) в противном случае:

> let init n f =
    let rec packed ys i =
      if i=n then Packed ys else
        match f i with
        | Float y ->
            ys.[i] <- y
            packed ys (i+1)
        | y ->
            Apply(Symbol "List", Array.init n (fun j ->
              if j<i then Float ys.[i]
              elif j=i then y
              else f j))
    packed (Array.zeroCreate n) 0;;
val init : int -> (int -> expr) -> expr

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

> let rec rule = function
    | Apply(Symbol "Sqrt", [|Float x|]) ->
        Float(sqrt x)
    | Apply(Symbol "Map", [|f; Packed xs|]) ->
        init xs.Length (fun i -> rule(Apply(f, [|Float xs.[i]|])))
    | f -> f;;
val rule : expr -> expr

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

Наша программа теперь может быть определена и исполнена нашим пользовательским перезаписью терминов:

> rule (Apply(Symbol "Map", [|Symbol "Sqrt"; Packed xs|]));;
Real: 00:00:00.049, CPU: 00:00:00.046, GC gen0: 24, gen1: 0, gen2: 0

Мы восстановили производительность Map[Sqrt, xs] в Mathematica!

Мы даже можем восстановить производительность Sqrt[xs], добавив соответствующее правило:

| Apply(Symbol "Sqrt", [|Packed xs|]) ->
    Packed(Array.map sqrt xs)

Я написал статью о термине переписывания в F #.

Ответ 3

Некоторые измерения

Основываясь на ответе @gdelfino и комментариях @rcollyer, я сделал эту небольшую программу:

j = # # + # # &;
g[x_] := x x + x x ;
h = Function[{x}, x x + x x ];


anon = Table[Timing[Do[ # # + # # &[i], {i, k}]][[1]], {k, 10^5, 10^6, 10^5}];
jj   = Table[Timing[Do[ j[i],           {i, k}]][[1]], {k, 10^5, 10^6, 10^5}];
gg   = Table[Timing[Do[ g[i],           {i, k}]][[1]], {k, 10^5, 10^6, 10^5}];
hh   = Table[Timing[Do[ h[i],           {i, k}]][[1]], {k, 10^5, 10^6, 10^5}];

ListLinePlot[ {anon,   jj,    gg,   hh}, 
 PlotStyle -> {Black, Red, Green, Blue},
 PlotRange -> All]

Результаты, по крайней мере для меня, очень удивительны:

Любые объяснения? Не стесняйтесь редактировать этот ответ (комментарии - беспорядок для длинного текста)

Изменить

Протестировано с помощью функции тождества f [x] = x, чтобы изолировать синтаксический анализ от фактической оценки. Результаты (одинаковые цвета):

Примечание: результаты очень похожи на этот график для постоянных функций (f [x]: = 1);

Ответ 4

Сравнение шаблонов выглядит быстрее:

In[1]:= g[x_] := x*x
In[2]:= h = Function[{x}, x*x];

In[3]:= Do[h[RandomInteger[100]], {1000000}] // Timing
Out[3]= {1.53927, Null}

In[4]:= Do[g[RandomInteger[100]], {1000000}] // Timing
Out[4]= {1.15919, Null}

Совпадение шаблонов также более гибко, так как позволяет перегрузить определение:

In[5]:= g[x_] := x * x
In[6]:= g[x_,y_] := x * y

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

In[7]:= k[x_] = Compile[{x}, x*x]
In[8]:= Do[k[RandomInteger[100]], {100000}] // Timing
Out[8]= {0.083517, Null}

Ответ 5

Вы можете использовать функцию recordSteps в предыдущем answer, чтобы узнать, что Mathematica действительно выполняет с функциями. Он относится к нему так же, как и любой другой Голова. IE, предположим, что у вас есть следующие

f = Function[{x}, x + 2];
f[2]

Сначала он преобразует f [2] в

Function[{x}, x + 2][2]

На следующем шаге x+2 преобразуется в 2+2. По существу, оценка "Function" ведет себя как приложение правил сопоставления шаблонов, поэтому не должно удивлять, что это не быстрее.

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