Mathematica“链接列表”和性能
在Mathematica中，我创建了单独链接列表，如下所示：
toLinkedList[x_List] := Fold[pair[#2, #1] &, pair[], Reverse[x]];
fromLinkedList[ll_pair] := List @@ Flatten[ll];
emptyQ[pair[]] := True;
emptyQ[_pair] := False;
pair cons单元使用符号pair的优点在于，即使列表包含Mathematica样式的List ，使用Flatten安全地工作，并允许使用MakeExpression / MakeBoxes定义自定义符号，这使得一切都变得更加愉快。 为了避免使用$IterationLimit ，我编写了使用While循环或NestWhile而不是使用递归的NestWhile 。 当然，我想看看哪种方法会更快，所以我写了两个候选人，所以我可以看着他们的战斗：
nestLength[ll_pair] :=
With[{step = {#[[1, -1]], #[[-1]] + 1} &},
Last@NestWhile[step, {ll, 0}, ! emptyQ@First@# &]];
whileLength[ll_pair] :=
Module[{result = 0, current = ll},
While[! emptyQ@current,
current = current[[2]];
++result];
result];
结果非常奇怪。 我测试上长度10000的链表的功能，并且whileLength通常是约50％的速度，在约0.035秒至nestLength的0.055秒。 但是，偶尔whileLength大约需要4秒。 我认为可能会有一些缓存行为，所以我开始生成新的随机列表来检查，而whileLength在第一次运行时不一定会缓慢， 它可能需要几十次才能看到放缓，但不会再发生（至少不是我试图用每个列表进行的200次）。
可能会发生什么？
作为参考，我用于测试的功能是这样的：
getTimes[f_, n_] :=
With[{ll = toLinkedList@RandomInteger[100, 10000]},
Table[Timing[f@ll], {n}][[All, 1]]]
编辑：我忽略提及版本较早; Mathematica 8获得了这些结果。
编辑第二：当我读丹尼尔Lichtblau的答案时，我意识到我的“典型”运行时间省略了前导0.它已被修复。
编辑第三：我认为列昂尼德Shifrin是正确的关联问题与Module ; 基于NestWhile的版本，我可以With用Module替换With来获得相同的行为：
nestModuleLength[ll_pair] :=
Module[{step = {#[[1, -1]], #[[-1]] + 1} &},
Last@NestWhile[step, {ll, 0}, ! emptyQ@First@# &]];
In[15]:= Select[getTimes[nestModuleLength, 100], # > 3 &]
Out[15]= {3.797}
下面的例子给出了典型的结果。
长度为20的一个缓慢例子。
In[18]:= getTimes[whileLength, 20]
Out[18]= {0.031, 0.032, 0.031, 0.031, 0.031, 0.032, 0.031, 0.031,
0.031, 0.047, 0.032, 0.031, 0.031, 3.547, 0.047, 0.031, 0.031, 0.032,
0.031, 0.031}
我顺便注意到，除了可比较的缓慢情况之外，时间比原来的时间快了10倍。 不确定什么说明了这种差异。
没有缓慢的例子。
In[17]:= getTimes[nestLength, 20]
Out[17]= {0.047, 0.047, 0.062, 0.047, 0.047, 0.062, 0.047, 0.047,
0.047, 0.063, 0.046, 0.047, 0.047, 0.063, 0.047, 0.046, 0.047, 0.063,
0.047, 0.047}
一个缓慢的例子，长度为100。
In[19]:= getTimes[whileLength, 100]
Out[19]= {0.031, 0.031, 0.031, 0.032, 0.031, 3.594, 0.047, 0.031,
0.031, 0.031, 0.032, 0.031, 0.031, 0.031, 0.032, 0.031, 0.047, 0.031,
0.031, 0.031, 0.032, 0.031, 0.031, 0.031, 0.032, 0.047, 0.031, 0.031,
0.031, 0.032, 0.031, 0.031, 0.031, 0.032, 0.031, 0.031, 0.047, 0.031,
0.031, 0.032, 0.031, 0.031, 0.031, 0.032, 0.031, 0.031, 0.047, 0.031,
0.032, 0.031, 0.031, 0.031, 0.032, 0.031, 0.031, 0.047, 0.031, 0.031,
0.032, 0.031, 0.031, 0.031, 0.032, 0.031, 0.047, 0.031, 0.031, 0.032,
0.031, 0.031, 0.031, 0.032, 0.031, 0.031, 0.031, 0.032, 0.046, 0.032,
0.031, 0.031, 0.031, 0.032, 0.031, 0.031, 0.047, 0.031, 0.032, 0.031,
0.031, 0.031, 0.032, 0.031, 0.047, 0.031, 0.031, 0.031, 0.032, 0.031,
0.031, 0.031}
Mathematica不完美地实现了所谓的“无限评估”。 也就是说，表达式会重新评估直到它停止改变。 为了使这个过程合理快速，有各种优化尝试尽可能短路过程。
在某些情况下，这可能很难辨别（由于类似于散列冲突的效应），并且可能不必要地重新评估表达式。 深度嵌套的表达式往往是最糟糕的情况。 我们还有更多的代码，即使在发生碰撞的情况下也可以解决这些问题。
在这个例子中的罪魁祸首正是这个代码，试图迅速确定表达式是否需要重新评估。 这是特殊的，但可能是一个线索（对某人），在While循环内最多发生一次这种情况。 因此，在坏情况下发生的事情可以防止在同一时间内再次发生。
有一段时间我对重新评估检测代码很熟悉，写了一大堆代码。 但是它被重写为版本8.所以即使在调试器中看到这种不理想的行为，这对我来说也是一个谜。 关于我现在可以说的一切，就是我提交了一个错误报告。
正如Leonid Shifrin所观察到的，具有HoldAllComplete属性的符号不受此问题影响。 所以使用这个属性对于这种类型的代码可能是有益的。
Daniel Lichtblau Wolfram Research
免责声明：以下是推测。 这似乎与搜索UpValues 。 它看起来像已经为全局变量进行了优化（以便系统可以跳过这一步，当它可以确定它可以做到这一点），但不是Module生成的本地变量。 为了测试这个，分配HoldAllComplete属性进行pair ，效果消失（从那时起， UpValues不会被检查为current ）：
SetAttributes[pair, HoldAllComplete];
In[17]:= ll = toLinkedList@RandomInteger[100, 10000];
Max[Table[Timing[whileLength[ll]], {1000}][[All, 1]]]
Out[18]= 0.047
HTH
似乎它与模块本地符号内存管理有关。
我将展示一些运行的时序系列。 每次运行当然会给出一个独特的绘图，但我在运行中检查了“一致性”。 看：
whileLength[l2_pair] :=
Module[{result = 0}, current = l2;
While[! emptyQ@current, current = current[[2]];
++result];
result];
给出以下时序系列：
虽然只使用全局符号：
whileLength[l2_pair] :=
Module[{}, result = 0; current = l2;
While[! emptyQ@current, current = current[[2]];
++result];
result];
得到：
链接地址: http://www.djcxy.com/p/35569.html