Friday, April 11, 2014

An Advanced Predicate and Analysis of How It Works with Trace and Timing

Wagner gives a different version of allodd@x that is more efficient than the one shown here. This function stops testing as soon as it finds a number that is not odd. Contrary to his predisposition, Wagner uses a procedural loop, "de-constructing," as he calls it, the List to operate on its Parts.

In[269]:= allOddProcedural@aList_List:=Module[{i},
For[i=1,i<=Length@aList,i++,If[!OddQ[aList[[i]]],Break[]]];i>Length@aList]

But I bet OddQ is Listable and therefore its C compilation would be much faster than the For loop. First let's compare the Wagner allOddQ from above with his procedural one.

Wagner's function Breaks after OddQ returns False when testing the third argument, 6 (near the end of the Trace). Note the 100-fold difference in Timing!

In[275]:= list2={3,5,6,7};

In[276]:= allOdd@list2//Trace

Out[276]= {{list2,{3,5,6,7}},allOdd[{3,5,6,7}],Length[Select[{3,5,6,7},OddQ]]==Length[{3,5,6,7}],{{Select[{3,5,6,7},OddQ],{OddQ[3],True},{OddQ[5],True},{OddQ[6],False},{OddQ[7],True},{3,5,7}},Length[{3,5,7}],3},{Length[{3,5,6,7}],4},3==4,False}

In[277]:= allOddProcedural@list2//Trace

Out[277]= {{list2,{3,5,6,7}},allOddProcedural[{3,5,6,7}],Module[{i$},For[i$=1,i$<=Length[{3,5,6,7}],i$++,If[!OddQ[{3,5,6,7}[[i$]]],Break[]]];i$>Length[{3,5,6,7}]],{For[i$41099=1,i$41099<=Length[{3,5,6,7}],i$41099++,If[!OddQ[{3,5,6,7}[[i$41099]]],Break[]]];i$41099>Length[{3,5,6,7}],{For[i$41099=1,i$41099<=Length[{3,5,6,7}],i$41099++,If[!OddQ[{3,5,6,7}[[i$41099]]],Break[]]],{i$41099=1,1},{{i$41099,1},{Length[{3,5,6,7}],4},1<=4,True},{{{{{i$41099,1},{3,5,6,7}[[1]],3},OddQ[3],True},!True,False},If[False,Break[]],Null},{i$41099++,{i$41099,1},{i$41099=2,2},1},{{i$41099,2},{Length[{3,5,6,7}],4},2<=4,True},{{{{{i$41099,2},{3,5,6,7}[[2]],5},OddQ[5],True},!True,False},If[False,Break[]],Null},{i$41099++,{i$41099,2},{i$41099=3,3},2},{{i$41099,3},{Length[{3,5,6,7}],4},3<=4,True},{{{{{i$41099,3},{3,5,6,7}[[3]],6},OddQ[6],False},!False,True},If[True,Break[]],Break[]}},{{i$41099,3},{Length[{3,5,6,7}],4},3>4,False},False},False}

In[262]:= list1=Range[1,10^7,2];

Timing[#@list1]&/@{allOddProcedural,allodd}

{{9.297660,True},{0.109201,<<1>>}}

Why Use Built-in Functions? They're Already Written, De-bugged, and Fast

Now let's try my premise - first, OddQ is Listable as I thought.

In[260]:= Attributes@OddQ

Out[260]= {Listable,Protected}

Let's write the simple function:

In[279]:= allOddFunctional@aList_List:=If[!OddQ@aList,i>Length@aList]

In[280]:= Timing[allOddFunctional@list1]

Out[280]= {0.093601,<<1>>}

allOddFunctional is 10X faster than Wagner's procedural function, even though it appears to check every argument:

In[281]:= allOddFunctional@list2//Trace

Out[281]= {{list2,{3,5,6,7}},allOddFunctional[{3,5,6,7}],If[!OddQ[{3,5,6,7}],i>Length[{3,5,6,7}]],{{OddQ[{3,5,6,7}],{OddQ[3],OddQ[5],OddQ[6],OddQ[7]},{OddQ[3],True},{OddQ[5],True},{OddQ[6],False},{OddQ[7],True},{True,True,False,True}},!{True,True,False,True}},If[!{True,True,False,True},i>Length[{3,5,6,7}]]}

The lesson is simply that built-in functions are almost always faster than ones we make if for no other reason than they are compiled into C.

Here Wagner shows the use of While instead of For to stop when it finds an odd number.

allodd@aList_List:=Module[{i=1},While[i<=Length@aList&&OddQ@aList[[i]],i++];i>Length@aList]

Here is a Dropbox link to Wagner's book. High kudos to "Mr Wizard Todd" for asking McGraw-Hill for the right to distribute Wagner's out-of-print book. Here's his post on the StackExchange Mathematica forum.

https://www.dropbox.com/s/kllwg6y44p8va5g/Wagner%20All%20Parts-RC.pdf

Here is a link to a compressed file: http://www.verbeia.com/mathematica/PowerProgMa.zip


1 comment:

  1. Im grateful for the blog.Really looking forward to read more. Cool.
    Mathematica

    ReplyDelete