相关疑难解决方法(0)

在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次运行).

可能会发生什么？

作为参考,我用于测试的功能是这样的: …