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;    

使用paircons单元格的符号具有Flatten安全工作的优点,即使列表包含Mathematica样式List,并允许您使用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秒到nestLength0.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; 我可以NestWhile通过替换Witha来从基于版本的版本获得相同的行为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循环内部的一次运行中.所以在坏的情况下会发生一些事情,以防止在同一时间内再次发生.

曾经有一段时间我熟悉了重新评估检测代码,编写了一大块.但是它被重写为版本8.所以即使在调试器中看到这种次优行为之后,对我来说这也是一个谜.我现在可以说的就是我提交了一份错误报告.

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

Daniel Lichtblau Wolfram Research

Answer 2

免责声明:以下是推测.这似乎与搜索有关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