Using Array and Table Functions in Mathematica. Which is best when

Question

I have been mostly a Table functions user in mathematica. However I have noticed that in several examples where I used Array instead of Table to express the same result, it ran markedly faster, especially as the dimension of table grew larger.

So my question is this: When speed of execution is the primary concern, when is it most appropriate to use table?

What explains this difference?

My guess is that because Arrays assume a functional relationship between the items in the list, it stores them more efficiently, therefore use less memory, thus facilitating storage and subsequent processing?

Is it what is going on?

Answer 1

Array has no performance advantages over Table. There are differences between them which make one preferred over another.

---

EDIT It was noted by several persons that Table is slower on multi-dimensional arrays. All of them used variable to hold the table size. Table has HoldAll attributes and only auto-evaluates outer-most interation bound. Because internal iterators remain unevaluated, the element of the table fails to compile. Using explicit numbers or With with result in auto-compilation:

In[2]:= With[{b = 10^4, c = 10^4},
 {Timing@(#[[1, 1]] &[ar = Array[(# + #2) &, {b, c}]]) , 
  Timing@(#[[1, 1]] &[ta = Table[(i + j), {i, b}, {j, c}]])}
 ]

Out[2]= {{4.93, 2}, {4.742, 2}}

In[3]:= Attributes[Table]

Out[3]= {HoldAll, Protected}

---

The Array allows you to build an array of function values just as much as the Table. They take different arguments. Array takes a function:

In[34]:= Array[Function[{i, j}, a[i, j]], {3, 3}]

Out[34]= {{a[1, 1], a[1, 2], a[1, 3]}, {a[2, 1], a[2, 2], 
  a[2, 3]}, {a[3, 1], a[3, 2], a[3, 3]}}

while table takes an explicit form:

In[35]:= Table[a[i, j], {i, 3}, {j, 3}]

Out[35]= {{a[1, 1], a[1, 2], a[1, 3]}, {a[2, 1], a[2, 2], 
  a[2, 3]}, {a[3, 1], a[3, 2], a[3, 3]}}

Array can only go over regular arrays, while Table can do arbitrary iterating over list:

In[36]:= Table[a[i, j], {i, {2, 3, 5, 7, 11}}, {j, {13, 17, 19}}]

Out[36]= {{a[2, 13], a[2, 17], a[2, 19]}, {a[3, 13], a[3, 17], 
  a[3, 19]}, {a[5, 13], a[5, 17], a[5, 19]}, {a[7, 13], a[7, 17], 
  a[7, 19]}, {a[11, 13], a[11, 17], a[11, 19]}}

Sometimes Array can be more succinct. Compare multiplication table:

In[37]:= Array[Times, {5, 5}]

Out[37]= {{1, 2, 3, 4, 5}, {2, 4, 6, 8, 10}, {3, 6, 9, 12, 15}, {4, 8,
   12, 16, 20}, {5, 10, 15, 20, 25}}

versus

In[38]:= Table[i j, {i, 5}, {j, 5}]

Out[38]= {{1, 2, 3, 4, 5}, {2, 4, 6, 8, 10}, {3, 6, 9, 12, 15}, {4, 8,
   12, 16, 20}, {5, 10, 15, 20, 25}}

Array allows one to build expression with any head, not just list:

In[39]:= Array[a, {3, 3}, {1, 1}, h]

Out[39]= h[h[a[1, 1], a[1, 2], a[1, 3]], h[a[2, 1], a[2, 2], a[2, 3]],
  h[a[3, 1], a[3, 2], a[3, 3]]]

By default the head h is chosen to be List resulting in creation of the regular array. Table does not have this flexibility.

Answer 2

Michael Trott in Programming (pp 707 - 710) address the issue of the differences between Array and Table and argues that as Table has the attribute HoldAll it computes its argument for every call, whereas Array "to the extent possible" computes its argument only at the beginning. This may lead to differences in behaviour as well as speed.

Attributes[Table]

{HoldAll, Protected}

Attributes[Array]

{Protected}

Michael Trott uses the following examples to illustrate the difference in both speed and behaviour. I am taking them verbatim from his book (disc). I hope I am not breaking any rules by doing so.

Remove[a, i, j];
a = 0;
Table[a = a + 1; ToExpression[StringJoin["a" <> ToString[a]]][i, j],
       {i, 3}, {j, 3}]

{{a1[1, 1], a2[1, 2], a3[1, 3]}, {a4[2, 1], a5[2, 2], a6[2, 3]}, {a7[3, 1], a8[3, 2], a9[3, 3]}}

a = 0;
Array[a = a + 1; 
 ToExpression[StringJoin["a" <> ToString[a]]], {3, 3}] 

{{a1[1, 1], a1[1, 2], a1[1, 3]}, {a1[2, 1], a1[2, 2], a1[2, 3]}, {a1[3, 1], a1[3, 2], a1[3, 3]}}

(Note the difference in behaviour)

To illustrate the effect of precomputing the first argument he uses the following example (again verbatim, p 709).

o[a = 0;
  Table[a = a + 1; 
   ToExpression[StringJoin["a" <> ToString[a]]][i, j],
         {i, 3}, {j, 3}], {2000}] // Timing
Do[a = 0;
  Array[a = a + 1; ToExpression[ StringJoin["a" <> ToString[a]]], 
                                            {3, 3}], {2000}] // Timing

{0.700173, Null}

{0.102587, Null}

(I am using mma7 on a Mac. My copy of Programming uses v5.1. There may well be an update to this)

This is not the only difference between Array and Table discussed in Programming, of course.

I view of other answers, I'll be interested to learn what others think of this point.

Answer 3

One reason Array may be faster is that it often compiles its first argument better.

In Mathematica 7:

In[1]:= SystemOptions[CompileOptions -> ArrayCompileLength]

Out[1]= {"CompileOptions" -> {"ArrayCompileLength" -> 250}}

and

In[2]:= SystemOptions[CompileOptions -> TableCompileLength]

Out[2]= {"CompileOptions" -> {"TableCompileLength" -> 250}}

So one can infer that Array and Table should compile at the same point.

But let's try it. I will be making use of Timo's timeAvg function:

n = 15;
Array[Mod[#^2, 5]*(1 + #2) &, {n, n}] // timeAvg
Table[Mod[i^2, 5]*(1 + j), {i, n}, {j, n}] // timeAvg

(* Out = 0.00034496 *)

(* Out = 0.00030016 *)

n = 16;
Array[Mod[#^2, 5]*(1 + #2) &, {n, n}] // timeAvg
Table[Mod[i^2, 5]*(1 + j), {i, n}, {j, n}] // timeAvg

(* Out = 0.000060032 *)

(* Out = 0.0005008   *)

What we see is that Array is able to compile Mod[#^2, 5]*(1 + #2) & while Table is not able to compile Mod[i^2, 5]*(1 + j) and therefore for Array becomes faster when the CompileLength is reached. Many functions are not so favorable. If you merely change multiplication to division in the function, which results in a rational rather than integer result, then this auto-compile does not happen, and Table is faster:

n = 15;
Array[Mod[#^2, 5]/(1 + #2) &, {n, n}] // timeAvg
Table[Mod[i^2, 5]/(1 + j), {i, n}, {j, n}] // timeAvg

(* Out = 0.000576   *)

(* Out = 0.00042496 *)

n = 16;
Array[Mod[#^2, 5]/(1 + #2) &, {n, n}] // timeAvg
Table[Mod[i^2, 5]/(1 + j), {i, n}, {j, n}] // timeAvg

(* Out = 0.0005744  *)

(* Out = 0.0004352  *)

But what if we can make this compile too? If we use floating point numbers, done by starting with 1., we get Real output, which can be compiled:

n = 15;
Array[Mod[#^2, 5]/(1 + #2) &, {n, n}, 1.] // timeAvg
Table[Mod[i^2, 5]/(1 + j), {i, 1., n}, {j, 1., n}] // timeAvg

(* Out = 0.0006256  *)

(* Out = 0.00047488 *)

n = 16;
Array[Mod[#^2, 5]/(1 + #2) &, {n, n}, 1.] // timeAvg
Table[Mod[i^2, 5]/(1 + j), {i, 1., n}, {j, 1., n}] // timeAvg

(* Out = 0.00010528 *)

(* Out = 0.00053472 *)

And once again, Array is faster on the larger dimension array.

Answer 4

Your statement:

However I have noticed that in several examples where I used Array instead of Table to express the same result, it ran markedly faster, especially as the dimension of table grew larger.

is not usually true for one-dimensional arrays. Take a look:

Cl;
Needs["PlotLegends`"]
$HistoryLength = 0;
a = 10^8;
arr = {}; tab = {};
Do[(
   arr = {First@Timing@Array[# &, a], arr};
   tab = {First@Timing@Table[i, {i, a}], tab};
   ), {10}];

ListLinePlot[{Flatten@arr, Flatten@tab}, 
 AxesLabel -> {Style["Iteration", 14], Style["Time", 14]}, 
 PlotLegend -> {Style["Array", 14], Style["Table", 14]}, 
 PlotRange -> {{0, 10}, {1.6, 2}}]  

Answer 5

Without giving some conrete examples, it is difficult to answer your question correctly.

Since Mathematica is a closed source program, the exact implementations behind Table and Array cannot be known, unless explained by people that were involved in development of Mathematica.

These factors will hinder your ability to reason which structure you should use in what circumstances. Experimentation will be your best bet, so I would suggest you keep parallel versions of your programs, one using Table, one using Array. This way, you'll be able to see which one is faster.

Even better, you could write a wrapper function which depends on a global variable. This function will, depending on the variable, use Table, or Array as the underlying implementation, so you will be able to quickly switch from one version to another, without doing many modifications to your code.