Mathematica的“链表”和性能

Question

在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单元的优点在于，即使列表中包含Mathematica风格的Lists，也可以安全地使用Flatten函数，并且允许您使用MakeExpression / MakeBoxes定义自定义符号，这使得一切更加愉快。为了避免必须搞乱$IterationLimit，我编写了使用While循环或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通常比nestLength快约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得到的。

第二次编辑： 当我阅读Daniel Lichtblau的回答时，我意识到我的“典型”运行时间漏掉了一个前导0。已经修复了。

第三次编辑： 我认为Leonid Shifrin正确地将问题与Module相关联；通过用Module替换With，我可以从基于NestWhile的版本中获得相同类型的行为：

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}

- Pillsy

---

开发人员的PackedArrayQ可能是相关的。 - Yaroslav Bulatov

@Yaroslav Bulatov：我看不出为什么紧凑数组会有关系，因为除了由RandomInteger生成的初始List之外，没有任何东西应该被压缩，而这个List立即被转换成类似树形的表达式。 - Pillsy

你使用的是版本7还是8？无论如何，我认为你已经发现了评估行为中的一个漏洞或至少是软点。 - Daniel Lichtblau

我不能为Module负责 - @belisarius是第一个建议它是罪魁祸首的人。 - Leonid Shifrin

这并不是 With 或 Module 本身的问题（我甚至认为我在 Block 中也复制了这个问题）。问题在于符号之间存在冲突，这会让求值器误以为需要检查表达式是否需要重新评估。 - Daniel Lichtblau

顺便说一句，将此代码天真地翻译成F#比Mathematica更短，速度快了300到30,000倍：https://dev59.com/YW025IYBdhLWcg3wSj8q#8286376 - J D

Answer 1

下面的示例给出了典型的结果。

一个长度为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循环中最多发生一次。因此，在坏情况下发生了某些事情，阻止了在同一个While内部的重复。

曾经我熟悉重新评估检测代码，写了其中一部分。但它已经在8版本中被重写。因此，即使在调试器中看到这种次优行为，对我来说仍然是一个谜。目前我能说的就是我提交了一个bug报告。

正如Leonid Shifrin所观察到的，具有HoldAllComplete属性的符号免疫这个问题。因此，在这种类型的代码中使用该属性可能是有益的。

Daniel Lichtblau Wolfram Research

- Daniel Lichtblau

---

只是让你知道。我试图在 Workbench 下运行并对其进行分析以重现这种行为。但它跑得非常顺畅！ - Dr. belisarius

@belisarius 这是8.0版本吗？理论上可能会有所不同。除此之外，我感到困惑。（不确定确切含义，但我怀疑它与被一只奇怪的牛打败有关。至少有些日子是这样的感觉。）另外，如果您更改了事物的名称，例如pair-->flair，那么可能会导致冲突消失。 - Daniel Lichtblau

@belisarius 这可能会引发不良行为。在 getTimes 中将最后一行更改为 Table[Update[]; Timing[f@ll], {n}][[All, 1]]。 - Daniel Lichtblau

是的，版本8。我会尝试Update[]这个东西，并带回结果。 - Dr. belisarius

Answer 2

免责声明：以下是一种推测。似乎与寻找UpValues有关。看起来这已经针对全局变量进行了优化（因此，当系统确定它可以跳过此步骤时，它会这样做），但并非针对由Module生成的局部变量。为了测试这一点，请将HoldAllComplete属性分配给pair，那么效果就消失了（因为此时不检查current的UpValues）：

SetAttributes[pair, HoldAllComplete];

In[17]:= ll = toLinkedList@RandomInteger[100, 10000];
Max[Table[Timing[whileLength[ll]], {1000}][[All, 1]]]

Out[18]= 0.047

HTH

- Leonid Shifrin

---

自那时起，UpValues 不会被检查为当前值；您能详细说明一下吗？ - acl

@acl: 当求值器遇到表达式 f[a] 且 f 具有 HoldAllComplete 属性时，不仅 a 在 f 之前不会被求值（那么 a 的结果完全取决于 f 的规则），而且与 a 相关的 UpValues 不会被检查，但当 f 具有 HoldAll 时则会被检查。我并不完全确定这是否在此起到了作用，但赋值的右侧看起来像是 Part[pair[num,pair[..]],2]。当求值 Part 时，会对 pair[___,element,___] 形式的 UpValues 进行求值，但如果 pair 具有 HoldAllComplete 属性，则不会进行求值。 - Leonid Shifrin

@acli：这在3版本中被称为“原地”列表修改问题，但似乎在后来的版本中已经进行了优化（David Wagner在他的书第7章第211页中对此进行了讨论）。我猜测，用于原地列表（表达式）修改的优化并没有涵盖（或不完全涵盖）由Module生成的局部变量的情况。正如我所说，我可能是错的，这只是一个猜测。 - Leonid Shifrin

Answer 3

看起来这与模块本地符号内存管理有关。

我将展示一些运行的时间序列。每次运行都会生成一个独特的图表，但我已经检查了各个运行之间的“一致性”。请看：

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];

给出：

- Dr. belisarius