左VS右链表，替换速度

有两个明显的方法可以构建数学链表，“左”：左VS右链表，替换速度

{1, {2, {3, {4, {5, {6, {7, {}}}}}}}}

和“右”：

{{{{{{{{}, 7}, 6}, 5}, 4}, 3}, 2}, 1}

这些都可以

toLeftLL = Fold[{#2, #} &, {}, [email protected]#] & ; 

toRightLL = Fold[List, {}, [email protected]#] & ;

如果我使用这些，并做了简单的ReplaceRepeated通过链表走，我得到drasti：与制造cally不同Timing结果：

r = Range[15000]; 
left = [email protected]; 
right = [email protected]; 

Timing[i = 0; left //. {head_, tail_} :> (i++; tail); i] 
Timing[i = 0; right //. {tail_, head_} :> (i++; tail); i] 

(* Out[6]= {0.016, 15000} *) 

(* Out[7]= {5.437, 15000} *)

为什么？

来源

2011-04-27 Mr.Wizard

我想这可能是因为尾部调用优化速度更快。 – Andrey 2011-04-27 00:29:32

选择这个：http://stackoverflow.com/questions/4481301/tail-call-optimization-in-mathematica – Andrey 2011-04-27 00:33:49

@Mr。向导：你可以分解你的'RuleDelayed'的RHS。虽然我觉得我可以看到它是如何遍历列表的，但这并不完全清楚。另外，如果我用尾巴+ tail替换RHS中的'tail'，我得到一个错误：'$ RecursionLimit :: reclim：超过256的递归深度。 >>'并且需要中止。为什么没有找到“tail-tail + tail = tail”并返回与以前相同的结果？ – abcd 2011-04-27 01:44:16

ReplaceRepeated使用SameQ来确定何时停止应用规则。

当SameQ比较两个列表时，它检查长度，如果相同，则将SameQ应用于第一个元素到最后一个元素。在left的情况下，第一个元素是一个整数，所以很容易检测到不同的列表，而right列表中的第一个元素是深度嵌套的表达式，所以它需要遍历它。这是缓慢的原因。

In[25]:= AbsoluteTiming[ 
Do[Extract[right, ConstantArray[1, k]] === 
    Extract[right, ConstantArray[1, k + 1]], {k, 0, 15000 - 1}]] 

Out[25]= {11.7091708, Null}

现在用的比较：

In[31]:= Timing[i = 0; right //. {tail_, head_} :> (i++; tail); i] 

Out[31]= {5.351, 15000}

编辑在回答选项Mr.Wizard的问题，加快这。一个人应该写一个自定义相同的测试。 ReplaceRepeated不提供这样的选项，所以我们应该用 FixedPoint和 ReplaceAll：

In[61]:= Timing[i = 0; 
FixedPoint[(# /. {tail_, _} :> (i++; tail)) &, right, 
    SameTest -> 
    Function[ 
    If[ListQ[#1] && ListQ[#2] && 
     Length[#1] == 
     Length[#2], (#1 === {} && #2 === {}) || (Last[#1] === 
     Last[#2]), #1 === #2]]]; i] 

Out[61]= {0.343, 15000}

EDIT2：更快尚未：

In[162]:= Timing[i = 0; 
NestWhile[Function[# /. {tail_, head_} :> (i++; tail)], right, 
    Function[# =!= {}]]; i] 

Out[162]= {0.124, 15000}

来源

2011-04-27 02:55:34 Sasha

你为什么认为这里涉及'SameQ'？打开'SameQ'的跟踪不会显示任何调用：'On [sameQ];'。 – 2011-04-27 03:04:22

'在[SameQ]上'只会显示对'SameQ'符号的评估。当确定'ReplaceRepeated'应该终止时，'ReplaceRepeated'不会调用求值器的效率。 – Sasha 2011-04-27 03:09:44

这就是我所说的作者答案 – 2011-04-27 03:40:26

左VS右链表，替换速度

回答

相关问题