बनाम राइट लिंक्ड सूची वाम, बदलें गति

Question

वहाँ दो स्पष्ट तरीके मेथेमेटिका में एक लिंक्ड सूची की संरचना करने, "छोड़" कर रहे हैं:

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

और "सही":

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

ये हो सकता है

drasti

toLeftLL = Fold[{#2, #} &, {}, Reverse@#] & ; 

toRightLL = Fold[List, {}, Reverse@#] & ; 

अगर मैं इन का उपयोग, और एक सरल ReplaceRepeated कर लिंक्ड सूची के माध्यम से चलने के लिए, मैं मिलता है: के साथ बनाया बड़ी सफाई अलग Timing परिणाम:

r = Range[15000]; 
left = toLeftLL@r; 
right = toRightLL@r; 

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} *) 

क्यों?

Answer 1

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}