Оптимизация основного цикла Mathematica

Question

Добрый день,

Читая эту ветку о производительности сопоставления с образцом и функциях в Mathematica Я был впечатлен Идеей Тимо по оптимизацииоценка выражений:

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

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

Answer 1

Как именно должна быть построена такая таблица диспетчеризации?

Скажем, у вас есть граф (сеть), состоящий из n вершин в цикле:

In[1] := rules =
           With[{n = 1000},
             Table[ToString@i -> ToString@Mod[i + 1, n],
               {i, 0, n - 1}]];

Вы хотите пройти по графу, применив эти правила перезаписи к начальной вершине. Вы можете выполнить один шаг с помощью i /. rules, но при этом выполняется линейный поиск по rules, пытаясь найти Rule с lhs, который соответствует выражению i. Поэтому применение правил много раз происходит медленно:

In[2] := Nest[# /. rules &, 0, 10000] // AbsoluteTiming

Out[2] = {1.7880482, 0}

Mathematica Dispatch позволяет нам предварительно вычислить хеш-таблицу, которая превращает линейный поиск в поиск с постоянным временем:

In[3] := dispatch = Dispatch[rules];

Многократное применение таблицы диспетчеризации приводит к получению одинаковых порядков ответов быстрее:

In[4] := Nest[# /. dispatch &, 0, 10000] // AbsoluteTiming

Out[4] = {0.0550031, 0}

В каких случаях такой подход рекомендуется?

Когда:

• Вы делаете много переписываний с одним и тем же набором правил перезаписи, и

• Набор правил перезаписи содержит не менее 30 правил с постоянными шаблонами lhs, т.е. составленными только из символов, последовательностей и литералов.

Как это действительно работает?

Он просто создает хеш-таблицу с постоянными шаблонами в качестве ключей.

Существуют ли другие способы оптимизации основного цикла?

Наиболее эффективный общий подход - переписать правила на другом языке. В частности, языки семейства ML (SML, OCaml и F #) имеют очень эффективные компиляторы сопоставления с образцом и сборщики мусора, поэтому они могут переписывать термины гораздо быстрее, чем переписчик общего назначения Mathematica.

Answer 2

Чтобы сделать это, сначала вы должны быть в состоянии рассчитать зависимости для вашего символа (ов). Пакет для этого есть в последнем выпуске журнала Mathematica Journal, который теперь бесплатно доступен онлайн. Вот URL: http://www.mathematica -journal.com / issue / v6i1 / . См. Статью «Силовое программирование: анализ зависимостей».

Вот рабочий пример:

In[1]:= <<"/path/to/DEPEND.MA"

In[2]:= $ContextPath

Out[2]= {DependencyAnalysis`,PacletManager`,WebServices`,System`,Global`}

In[3]:= f[x_]:=x x

In[4]:= g[x_]:=x+1

In[5]:= h[x_]:=f[x]+g[x]

In[6]:= i[x_]:=f[g[x]]

In[7]:= DependsOn[g][[2]]

Out[7]= {Blank,Pattern,Plus,x}

In[8]:= DownValues@@@DependsOn[g][[2]]

Out[8]= {{},{},{},{}}

In[9]:= getDownValues[s_Symbol]:=DownValues[s]

In[10]:= getDownValues[s_HoldForm]:=getDownValues@@s

In[11]:= getDownValues[s_]:={}

In[12]:= hasDownValues[x_]:=getDownValues[x]=!={} 

In[13]:= ruleListEntries[x_List]:=Union[Union@@ruleListEntries/@x,{x}]

In[14]:= ruleListEntries[x_]:=Select[Union[DependsOn[x][[2]],{x}],hasDownValues]

In[15]:= ruleListEntries[f]

Out[15]= {f}

In[16]:= ruleListEntries[g]

Out[16]= {g}

In[17]:= ruleListEntries[h]

Out[17]= {h,f,g}

In[18]:= ruleListEntries[i]

Out[18]= {i,f,g}

In[19]:= dispatch=getDownValues/@ruleListEntries[i]//Flatten//Union//Dispatch

Out[19]= {HoldPattern[f[x_]]:>x x,HoldPattern[g[x_]]:>x+1,HoldPattern[i[x_]]:>f[g[x]]}

In[20]:= i[x]

Out[20]= (1+x)^2

In[21]:= HoldForm[i[x]]//.dispatch

Out[21]= (x+1) (x+1)

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