Левый и правый связанный список - PullRequest
Новая
       14

Левый и правый связанный список

11 голосов
/ 27 апреля 2011

Существует два очевидных способа структурировать связанный список в Mathematica, «левый»: 

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

и "правильно": 

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

Это может быть сделано с: 

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

Почему?

1 Ответ

8 голосов
/ 27 апреля 2011

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}
...