Насколько я понимаю, первый подход является чем-то эквивалентным макросу lisp и, по моему опыту, предпочтителен из-за более краткого синтаксиса.
Не совсем.Mathematica является переписчиком терминов, как и макросы Lisp.
Итак, у меня есть два вопроса, есть ли разница в производительности между выполнением функций и подходом сопоставления с шаблоном / макроса?
Да.Обратите внимание, что вы никогда не выполняете «функции» в Mathematica.Вы просто применяете правила перезаписи, чтобы изменить одно выражение на другое.
Рассмотрите возможность сопоставления функции Sqrt с упакованным массивом чисел с плавающей запятой.Самое быстрое решение в Mathematica - применить функцию Sqrt непосредственно к упакованному массиву, потому что она реализует именно то, что нам нужно, и оптимизирована для этого особого случая:
In[1] := N@Range[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 создает 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 # .