Thursday, June 4, 2015

Examples of Different Programming Styles with Timing

This comparison of different programming styles is adapted from Roman Maeder's in his Programming in Mathematica course. Here is a List of expressions to square, including different types on numbers and an undefined symbol.

alist={a,1.1,2+3I,4,573297329847};


Functional Style


Here is the shortest solution, which works due to the function Attribute, Listable, of Power that maps Power over a List. You can add Listable to your own functions to achieve the same simplicity.

squareListListable@list_List:=list^2

squareListListable@alist
{a^2,1.21,-5+12 I,16,328669828409699917043409}

As Maeder says, it really cannot get much simpler than that. Here are two more functional-style solution. These are also compact. The first uses Table, a very powerful function that leads us to not deconstruct lists (arrays) but to think of applying a function to them as a whole. The simple squaring of each List item could be replaced with a function of arbitrary complexity.

squareFunctional@list_List:=Table[i^2,{i,list}]

Beginners are often unaware of Table's ability to iterate directly over List items, as above, without this unnecessary clutter. However, see the Timing analysis below for a surprise.

squareFunctionalWithIterator@list_List:=Table[list[[i]]^2,{i,Length@list}]

This third functional example uses Map, another powerful function that, along with Listable and Table, replaces the Do loop. A pure Function expresses the squaring operation concisely.

squareListMapped@list_List:=Map[#^2&,list]


Rule-Based Style


Programming with replacement rules is the way Mathematica itself works — Every Change is a Transformation — and rule-based functions are often very concise and easy to understand. I prefer rule-based functions over other styles.

squareRuleBasedShorter@list_List:=list/.{first___,x_,rest___}->{first,x^2,rest}


Recursive Style


Here is a recursive rule-based approach — the function calls itself and keeps marching down a 'rest' of List that keeps getting smaller. Note that flattening deeply nested Lists is a very fast operation (Log@n) whose timing you rarely need to worry about. However this recursive approach is only practical for small examples.

squareRuleRecursive@list_List:=list/.{x_,rest___}:>{x^2,squareRuleRecursive@{rest}}//Flatten

Procedural Style


While I really think which style to use is a personal decision ('de gustibus non est disputandum'), this procedural solution does seem cumbersome and old-fashioned compared to the functional and rule-based ones. But sometimes procedural functions are easier and faster to write than laboring to find more concise functional or rule-based ones.

squareProcedural@list_List:=Module[{array1={},squaresList,
listLength=Length@list},
Do[array1=Prepend[array1,0],{i,listLength}];
Do[array1[[i]]=list[[i]]^2,{i,listLength}];
Return@array1
]

Maeder cheats a bit, using Table to initialize his array, which speeds up his function considerably as you'll see in the Timing analysis.

squareProceduralMaeder@list_List:=Module[
{squaresArray,
listLength=Length@list},
(*initialize the array*)
squaresArray=Table[0,{listLength}];
Do[squaresArray[[i]]=list[[i]]^2,{i,listLength}];
Return@squaresArray
]


Timing Analysis


aLongList=Range[10^6];

The Listable function is the clear winner.

Timing[squareListListable@aLongList;]
{0.,Null}

Let's push it harder to see more of its speed advantage. It appears to be 10 times faster than its competitors below.

Timing[squareListListable@Range[10^7];]
{0.015600,Null}

Timing[squareFunctional@aLongList;]
{0.031200,Null}

Here's the surprise I mentioned. Not sure why, but using the iterator is exactly twice as fast than 'directly' iterating over List items. I'd only worry about this for functions needing optimization though.

Timing[squareFunctionalWithIterator@aLongList;]
{0.015600,Null}

Timing[squareListMapped@aLongList;]
{0.015600,Null}

It surprise me that the rule-based approach is relatively slow.

Timing[squareRuleBased@aLongList;]
{0.062400,Null}

Both the recursive and procedural approaches are very slow.

Timing[squareRuleRecursive@aLongList;]
During evaluation of In[186]:= $RecursionLimit::reclim: Recursion depth of 1024 exceeded. >>
Out[186]= {9.188459,Null}

Timing[squareProcedural@aLongList;]
$Aborted

Timing[squareProceduralMaeder@aLongList;]

{2.012413,Null}

No comments:

Post a Comment