wolfram-mathematica - Mathematica "linked lists"和性能

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对于缺点细胞具有 Flatten的优势即使列表包含 Mathematica 样式 List 也能安全工作s，并允许您使用 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 上测试了函数通常快约 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's answer ，我意识到我的“典型”运行时间省略了前导 0。它已被修复。

编辑第三个:我想 Leonid Shifrin将问题与 Module 相关联是正确的;我可以从 NestWhile 得到同样的行为通过替换 With 基于的版本与 Module :

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}

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 中被重写了。因此，即使在调试器中看到这种次优行为后，对我来说仍然是个谜。我现在只能说我提交了一个错误报告。

正如 Leonid Shifrin 所观察到的，具有 HoldAllComplete 属性的符号不受此问题的影响。因此，使用该属性可能对此类代码有益。

丹尼尔·利希布劳
Wolfram 研究