优化 Mathematica 的主循环

Question

美好的一天，

阅读这个关于模式性能的主题 Mathematica 中的匹配和函数Timo 关于优化表达式求值的想法：

我有时构建了一个 所有功能的调度表 I 需要并手动将其应用到我的 起始表达。这提供了一个 速度显着高于正常速度 评价为 Mathematica 中没有的 需要解析内置函数 反对我的表达。

究竟应该如何构建这样的Dispatch表？在什么情况下会推荐这种方法？它到底如何运作？还有其他优化主循环的方法吗？

Answer 1

为此，首先您需要能够计算符号的依赖性。 Mathematica Journal 的过刊中提供了一个可以实现此目的的软件包，该期刊现已在线免费提供。这是网址： http://www.mathematica-journal.com/issue/v6i1/< /a>.请参阅文章“Power 编程：依赖性分析”。

这是一个有效的示例：

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，因此这仅对于将表达式简化为仅包含内置符号有用。

Answer 2

这样的调度表到底应该如何构建？

假设您有一个由 n 个循环顶点组成的图（网络）：

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

您希望通过将这些重写规则应用于初始顶点来遍历该图。您可以使用 i / 执行单个步骤。但这是对 rules 进行线性搜索，试图找到 lhs 与表达式 i 匹配的 Rule。因此多次应用规则是很慢的：

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 的通用重写器更快地重写术语。