Expression Efficiency

Documentation MathematicaBuilt-in Functions Advanced Documentation Linear Algebra Performance

The introduction explained that Mathematica represents matrices as expressions, a uniform data type that is used throughout the system. It described the advantages that came from this uniformity in the system. There are a number of efficiency implications that arise from the use of Mathematica expressions. This section will discuss these.

Updating of Matrices

A general principle of Mathematica expressions is that they cannot be changed directly. This immutability of expressions is very useful; it allows an expression to be shared in many locations and each use need not be concerned that some other part of the code will modify the expression. This means that when an expression is updated (this was described in the section Setting Pieces of a Matrix), it may be necessary to make a copy. In this example, a vector is made and assigned to two different symbols.

In[1]:=

Now change the contents of one symbol.

In[3]:=

Out[4]=

However, the other one is left unchanged. This is because the expression was copied before modification.

In[5]:=

Out[5]=

This copying can have an implication for efficiency, especially if you are iterating over the elements of a matrix and updating it. If this is done and you also have other copies of the matrix, it will need to be copied. The principle is demonstrated in the following two examples. In this first example there are no extra copies of the vector and so it does not need to be copied and the loop runs faster.

In[6]:=

Out[7]=

In this example there are extra copies of the vector and so it does need to be copied at each step; the loop runs more slowly.

In[8]:=

Out[9]=

Another slow way to update elements is to use ReplacePart. This also has to copy at every step.

In[10]:=

Out[11]=

If you use the vectorizing operations described previously, this is a good way to avoid the iteration over the matrix and minimize the number of copying operations. If you really cannot avoid iterating over the matrix, it is a good idea to keep the loop as simple and tidy as possible so that you can avoid extra copies of the matrix.

The time for the overall process will scale with the square of the length of the list for the technique that has to copy at every step. With no copying the time will scale linearly. The longer the input list, the greater the impact, and the performance of the code will start to degrade.

Appending to Matrices

In Mathematica, expressions are implemented as arrays. This allows fast access to any particular elements of an expression. Because matrices are regular Mathematica expressions, they are also arrays. While arrays are very fast for accessing elements, they are slower for adding elements. Typically this requires a copy, and it should be avoided. The example that follows shows the cost of adding elements.

In[1]:=

Out[2]=

It is much more efficient to generate the entire vector at once.

In[3]:=

Out[3]=

If the arguments are not known all at once, other techniques may be used. These are demonstrated below. First, build a list of random numbers.

In[4]:=

The first technique is using AppendTo.

In[6]:=

Out[7]=

It is much faster to accumulate the list, inserting empty lists that can be removed at the end with Flatten.

In[8]:=

Out[8]=

It may be inconvenient to use Flatten because this might interfere with the structure of the list. In this case it might be convenient to use Sow and Reap. This is more flexible than the Flatten approach.

In[9]:=

Out[9]=

All three methods generate the same result.

In[10]:=

Out[10]=