Programming for speed

In the cells below I give some rules of thumb that enhance the speed of Mathematica programs.

Use Look Up Tables

When you have values for (f) defined for specific values such as
f[1]=y1;
f[2]=y2;
f[3]=y3;
  ...
Mathematica can evaluate something like f[2] with great speed even if the definitions more complicated than integers. The speed of evaluation is very fast for definitions that are free of patterns such as x_ or {x_,y_}. I refer to storage of function values for specific arguments as a look up table.

For example you could define a new version of Prime that evaluates over a certain range of large integers much faster than the built-in Prime function. The next cell defines MyPrime which uses Prime for n<5000000000, and has explicit values stored for 5000000000<n<5000000010. Finally I felt it would be appropriate to first try the rule for 5000000000<n<5000000010 so I rearrange the list of DownValues. The output below shows the resulting list of definitions.

ClearAll[MyPrime]MyPrime[n_Integer?(#<5000000000&)]:=Prime[n]&IndentingNewLine;Evaluate[MyPrime/@Range[5000000000,5000000010]]=
Table[Prime[n],{n,5000000000,5000000010}];
DownValues[MyPrime]=RotateRight[DownValues[MyPrime],1]

{HoldPattern[MyPrime[n_Integer?(#1<5000000000&)]]:>Prime[n],HoldPattern[MyPrime[5000000000]]:>122430513841,HoldPattern[MyPrime[5000000001]]:>122430513847,HoldPattern[MyPrime[5000000002]]:>122430513857,HoldPattern[MyPrime[5000000003]]:>122430513913,HoldPattern[MyPrime[5000000004]]:>122430513923,HoldPattern[MyPrime[5000000005]]:>122430513971,HoldPattern[MyPrime[5000000006]]:>122430514049,HoldPattern[MyPrime[5000000007]]:>122430514069,HoldPattern[MyPrime[5000000008]]:>122430514091,HoldPattern[MyPrime[5000000009]]:>122430514123,HoldPattern[MyPrime[5000000010]]:>122430514181}

Now in the next cell I do the same thing with explicit values stored for 5000000000<n<5000010000, but display of the list of rules is suppressed because it's very long. You should be patient when the next cell is evaluated because it takes several minutes.

ClearAll[MyPrime]MyPrime[n_Integer?(#<5000000000&)]:=Prime[n]&IndentingNewLine;Evaluate[MyPrime/@Range[5000000000,5000010000]]=
Table[Prime[n],{n,5000000000,5000010000}];&IndentingNewLine;DownValues[MyPrime]=RotateRight[DownValues[MyPrime],1];

Once the definitions for MyPrime are stored a list of primes can be made with the next cell almost instantly.

Table[MyPrime[n],{n,5000000000,5000000400}]

An  implementation with more sensible use of memory would only store explicit definitions of MyPrime for say 5000000500, 50000001000, 5000001500, 5000002000, ... and would evaluate Nest[NextPrime,MyPrime[50000001000],43] to determine MyPrime[50000001043]. I didn't do that here because my purpose here is to demonstrate how fast the lookup table is.

Often times look-up table are created on the fly using definitions of the form:
f[x_]:=f[x]=expr
This can result in efficient programs if (f) needs to be evaluated many times for the same argument.

Use functional programming

The tools of functional programming include:
   Map  MapAt  Thread  Apply  MapThread  MapAll  MapIndexed  Fold  FixedPoint  Nest  NestWhile
   FoldList  FixedPointList  NestList  NestWhileList  Scan  Inner  Outer  Distribute.
Each of these are often an important part of very efficient programs.

Other functional programming tools available are:
    ComposeList, Composition  Operate  Through.
These other functional programming features are also efficient, but seldom needed in practice.

No examples of the functions listed above are provided here, but many of them have a devoted section in this notebook

Use pure functions

In the next cell three similar functions are defined . The function f1 is defined with a named pattern while pure functions are used to define f2 and f3. We see the implementation defined with pure functions run much faster than the definition defined with a named pattern.

ClearAll[lst,f1,f2,f3];SetAttributes[{f1,f2,f3},Listable]; f1[x_]=3x+5;f2=Function[x,4 x+6];f3=6#+13&;&IndentingNewLine;lst1=Range[5*10^5];

f1[lst1];//Timing

{16.3599999999999` Second,Null}

f2[lst1];//Timing

{0.9900000000000091` Second,Null}

f3[lst1];//Timing

{0.32999999999992724` Second,Null}

Use linked lists instead of adding to a list

The most straight forward way of adding to a list uses PrependTo or AppendTo as in the next cell. There are a number of other ways you could effectively do the same thing but they are all very slow for making long lists. As an example consider the program in the next cell which makes a list by prepending values.

lst1={};Do[(y=Sin[20.0 t];If[Positive[y],PrependTo[lst1,y]];),&IndentingNewLine;{t,0,10^4}]//Timing

{4.3400000000001455` Second,Null}

The faster way to build the list in the previous cell is to make a linked list which looks like  
{... ,y4,{y3,{y2,{y1}}}} instead of {...  ,y4,y3,y2,y1} as returned by the program in the previous cell. Flatten can then be used to convert the linked list into a flattened list.

lst2={};Do[(y=Sin[20.0 t];If[Positive[y],lst2={y,lst2}];),&IndentingNewLine;{t,0,10^4}]//Timing

{0.44000000000005457` Second,Null}

lst1==Flatten[lst2]

True

However a temporary head is needed if you want to quickly build up a list such as
{... ,{x4,y4},{x3,y3},{x2,y2},{x1,y1}}. In that case an expression with the form
h[{x4,y4},h[{x3,y3},h[{x2,y2},h[x1,y2]]]] can be built-up. Then you can get the desired result by flattening the nested list and changing the head (h) to List. This is done in the next two cells.

lst2=h[];Do[(y=Sin[20.0 t];If[Positive[y],lst2=h[{t,y},lst2]];),&IndentingNewLine;{t,0,12}]&IndentingNewLine;lst2

h[{12,0.9454451549211168`},h[{11,0.08839871248753149`},h[{8,0.21942525837900473`},h[{7,0.9802396594403116`},h[{6,0.5806111842123143`},h[{2,0.7451131604793488`},h[{1,0.9129452507276277`},h[]]]]]]]]

lst2=Flatten[lst2]/.h->List

{{12,0.9454451549211168`},{11,0.08839871248753149`},{8,0.21942525837900473`},{7,0.9802396594403116`},{6,0.5806111842123143`},{2,0.7451131604793488`},{1,0.9129452507276277`}}

Don't compute the same thing over and over

Often times one needs to have an understanding of the evaluation process to know when things are computed over and over. An example of this point is given in the section on Set versus SetDelayed which is copied below.

Alan Hayes provided an example where (  func[x_]=  ) instead of  
( func[x]:=  ) should be used.  If ( func[x_]:=  ) was used in this example the least squares fit would be computed  again for every value of (x) when we evaluate something like
Plot[curve[t],{t,0,π/3}].

Use the simplest form possible

Some Mathematica functions are special cases of other functions. An example of this is Range which is a special case of Table. Hence Range will make a list in the next cell faster than Table would.

slow=Table[i,{i,5000}];fast=Range[5000];

Lots of Mathematica functions have multiple forms available. In many cases simpler forms are available which are special cases of more general forms. Hence Table runs faster in the next cell when an iterator isn't used.

slow=Table[Random[],{i,10^5}];fast=Table[Random[],{10^5}];

Minimize the number of expressions the kernel must evaluate

Ensuring that a program needs to evaluate the fewest number of expressions is an important part of minimizing the time a program needs to evaluate. For example the Dot product of two vectors evaluates much faster when the built in Dot function is used in the next cell.

Another example (which only works in Version 4) is given in the next cell where the slow method of making a list needs to evaluate Part 12 times, but the fast method does the same thing in one application of Take.

Clear[x,lst];lst=x Range[70];slow=Table[Part[lst,3 n],{n,1,12}];fast=Take[lst,{3,50,3}]

{3 x,6 x,9 x,12 x,15 x,18 x,21 x,24 x,27 x,30 x,33 x,36 x,39 x,42 x,45 x,48 x}

Still another example (which only works in Version 4) is given in the next cell where the slow method maps First onto each element of data, but the fast method does the same thing with one application of Part. When the slow method is used First must be evaluated over and over.

{1,4,7,10,13,16,19,22,25,28,31,34,37,40,43,46,49,52,55,58,61,64,67,70,73,76,79,82,85,88,91,94,97,100,103,106,109,112,115,118}

Another example of this principle is changing the value at multiple parts of an expression by using the Part feature only once. This is demonstrated in the section on Part.

Use approximate machine numbers whenever appropriate

If your application allows the round off error inherent in machine precision arithmetic you can greatly improve the speed of your program by ensuring all numeric calculation is done on approximate machine numbers. Of course certain calculations over integers are easily computed at the machine level and computing with approximate numbers would not be any faster in that case.

Ensure your program runs fast with Packed Arrays

Rob Knapp provides a tutorial on Packed Arrays at http://library.wolfram.com/tutorials/. and I give simplified examples of the trick he uses to speed up an implementation of LUDecomposition above in my discussion of Part.

As Rob explains you often need to use certain programming methods to get the improved speed possible with the with Packed Arrays.

Use Compile

The speed of programs can often be enhanced if they are written using Compile, but you need to take certain steps to ensure the program evaluates with compiled evaluation. This is discussed in the section on Compile.

Don't use ReplacePart, MapAt or Insert when the last argument is a
long List (>40 elements).

ReplacePart, MapAt and Insert are very slow in this case. For mor explanation see the discussion of Slow Kernel Functions.

Check These Sources Too

Alan Hayes wrote an in-depth article on efficient Mathematica programming in Vol 2, Issue 2 of The Mathematica Journal.

Chapter 10 of
Power Programming with Mathematica The Kernel
by David B. Wagner  (ISBN 0-07-912237-X)
gives a wealth of great advice on improving the speed of Mathematica programs.
I understand this great book is out of print. If that is the case you may be able to get a copy from an online auction such as e-bay or from the amazon.com out of print book service.