Software Engineering
programming-languages array
Updated Fri, 09 Sep 2022 02:01:05 GMT

Multidimensional vs nested arrays


A seemingly basic question here.

Is there anything you can do with multidimensional arrays that you can't do with nested arrays?

Many languages have been designed with both facilities and syntactical differences, but I can't for the life of me work out what you can do with multidimensional arrays that you can't do with nested arrays, or infer confidently the reasons for their separate existence.

Perhaps, a multidimensional array is always regular and has an associated type constraint (and can therefore have storage layouts and access patterns optimised for that regularity), whereas a nested array can be jagged, and perhaps the inner levels of a nested array can be missing altogether.

But is the need for the distinct concept of a multidimensional array, caused solely by these concerns - namely, that nested arrays suffer from limitations in the type system that don't allow constraints on their shape be expressed (and consequently, an inability to optimise performance for certain regular shapes)?

Or is there something more fundamental about the difference? Something you can do conveniently with multidimensional arrays, which you can't do (or wouldn't do without more difficulty) with nested arrays?

Solution

There is nothing that you can do with multidimensional arrays that you couldnt do with nested arrays. The proof: many popular programming languages (C, C++, Java, Swift, ) offer only nested arrays and syntactic sugar to use them for multidimensional purpose. To be fully accurate, some of these languages also provide for multidimensional arrays but with very restrictive constraints (e.g C and C++).

True multidimensional arrays are a convenience offered natively by only some languages (e.g. Fortan, Ada, Julia), when dealing with arrays of a fixed number of dimensions of known size, often for the purpose of offering multidimensional matrixes.

The difference is just in the implementation and libraries bridge the gap:

  • Multidimensional arrays can be stored in a contiguous space, with less storage management overhead, and quick indexing. But dynamically changing the size of one dimension could be very inefficient.
  • Nested arrays require more complex storage management and indexing, but allow a greater deal of flexibility, as any elements in any dimension could allow further nesting and different sizes. Hence they could even offer variable number of dimensions. On the other side, they require extra care when the dimensions are meant to be of homogeneous size like for matrixes.

But this dichotomic view of the array world is very simplified; many more concerns and implementation exist:

  • Multidimensional arrays can also be implemented with maps/dictionaries, that allow to quickly retrieve a specific element regardless of storage mecanism used. While fast for accessing individual elements, they might be less performant for iterating over elements.
  • Multidimensional arrays can be sparse allowing to manage more efficiently uneven distribution of elements (e.g. when there is a lot of empty space like in the universe and some clusters of non-default values here and there).

So ultimately, what matters is the properties of the multimensional array you need, as well as the envisaged usage patterns.


External Links

External links referenced by this document:

References