5.5.2.8   Example:   linked lists and the fast accumulation of results

For many applications, one needs to be able to build up a list of some intermediate results obtained in some computation. The easiest way to set up such a list is to use Append or Prepend (or perhaps, AppendTo or PrependTo). However, for large lists this method is quite inefficient. The reason is that lists in Mathematica are implemented as arrays, and thus every time we add an element, the entire list is copied.

We can use FoldList to illustrate the creation of a list in such manner :

Now, let us do some performance tests :

We see that  the time used by this operation is quadratic in the size of the list. We of course would like a linear time. One way to achieve this which is available starting with the Mathematica  version 5.0 is to use the Reap-Sow technique (to be described in Part II). Another (perhaps, slightly less efficient) way to get a linear time is to use linked lists. We will follow the discussion in the book of David Wagner [7].

A linked list in Mathematica is a structure of the type

The advantage of this representation is that on every level, we have a list containing just 2 elements, which is easy to copy. It will not work in this way for elements that are lists themselves, but then one can replace a list by an arbitrary head <h>.

To avoid a possible conflict with some < h > already defined, we can use Module[{h}, ...] to make it local.

Using Fold is the most natural way to  create such structures :

Converting them back to a normal list is just as easy with Flatten :

Notice that in the second case we used the fact that Flatten  takes as an optional third argument the head which has to be Flatten - ed, and then Flatten - s only subexpressions with this head. In any case, this is another linear-time operation.

We can now write a function:

Let us do some performance tests:

We see that the time is roughly linear in the list size, and for example, for a list of 20000 we get already a speed - up of the order of 100 times! Flattening is even faster:

Here we assumed that the list of results is accumulated immediately, just to separate this topic from the other problem - specific part of a program.   If the list is accumulated not immediately but some other operations are performed in between (which is what usually happens), one just has to use the idiom list  = {newelement, list}, to achieve the same result.

Created by Wolfram Mathematica 6.0  (05 February 2009)