5.4.3 Performance considerations for Lists

Lists provide efficient ways of appending and removing elements. They can be created without knowing their final dimensions. Lisp provides efficient means of copying and handling lists. Also nested lists do not need to be strictly rectangular. These advantages over declared arrays come with the drawback that the amount of time needed for accessing a random element within a list may be roughly proportional to the element’s distance from its beginning. Efficient traversal of lists is still possible, though, by using the list as a stack or a fifo:

(%i1) l:[Test,1,2,3,4];
(%o1)                  [Test, 1, 2, 3, 4]

(%i2) while l # [] do
   disp(pop(l));
                              Test

                                1

                                2

                                3

                                4

(%o2)                         done

Another even faster example would be:

(%i1) l:[Test,1,2,3,4];
(%o1)                  [Test, 1, 2, 3, 4]

(%i2) for i in l do
   disp(pop(l));
                              Test

                                1

                                2

                                3

                                4

(%o2)                         done

Beginning traversal with the last element of a list is possible after reversing the list using reverse (). If the elements of a long list need to be processed in a different order performance might be increased by converting the list into a declared array first.

Note also that the ending condition of for loops is tested for every iteration which means that the result of a length should be cached if it is used in the ending condition:

(%i1) l:makelist(i,i,1,100000)$

(%i2) lngth:length(l);
(%o2)                        100000

(%i3) x:1;
(%o3)                           1

(%i4) for i:1 thru lngth do
    x:x+1$

(%i5) x;
(%o5)                        100001