左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右鏈表，替換速度

回答

相關問題