4

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?

Improve this question
6
  • 2
    No, the same is also true of 99% of all programming language features - there's absolutely nothing that anyone can do with any feature of any high-level language which couldn't also be done without them. Anything you can do with multi-dimensional arrays or nested arrays can also be done using raw machine code which has no such concept as an "array" let alone the concept of a "dimension". For example, there's also no need for functions, classes, for/while loops, if/else, switch, data types, etc.
    – Ben Cottrell
    Commented Jul 30, 2022 at 11:34
  • @BenCottrell, well obviously I'm not asking "could we just do it all in assembly instead". I'm asking is there anything you can do with multidimensional arrays which you can't trivially do with nested. Also, all computers have to have some arrays natively - at least as I understand it.
    – Steve
    Commented Jul 30, 2022 at 12:34
  • 1
    My point is that you can ask of any high-level language feature whether it's necessary, and the answer is nearly always "no" because all anyone really needs are whichever instructions are available natively to the platform, and then you'll always have a way of being able to implement higher-level abstractions on top of that, whether those abstractions are data types, language keywords, libraries or anything else (Arrays are a higher-level abstraction based on simple arithmetic with memory addressing, not a native feature of any CPU instruction set that I've ever heard of)
    – Ben Cottrell
    Commented Jul 30, 2022 at 13:04
  • @BenCottrell, but they don't appear to me to be two different abstractions. They appear to cover exactly the same ground, save that the nested way is entirely more general because it can cope with irregular as well as regular arrays (with no apparent hardship in terms of syntax). As for native arrays, the byte is an array of bits, and main memory is an array of bytes. Registers and instructions typically operate on words.
    – Steve
    Commented Jul 30, 2022 at 13:48
  • They are fundamentally different; including memory representations ('array-of-pointers' vs. a single cohesive block), with different constraints, guarantees, and available operations; which affects how programmers write their code, Even in cases where the same functionality can be implemented in either, the choice would determine whether the code is idiomatic, or whether it involves unnecessary and avoidable complexity, which is likely to be detrimental in areas like code quality, legibility, automated testing and maintainability, compared with choosing the most appropriate abstraction.
    – Ben Cottrell
    Commented Jul 30, 2022 at 14:43

2 Answers 2

Reset to default
4

There is nothing that you can do with multidimensional arrays that you couldn’t 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.

Improve this answer
2

Multi dimensional arrays are just single dimension arrays with math done on the indexing. You can access any cell in O(1).

Nested arrays have indirection. Accessing them is slower because of that indirection.

However, unless you have a ridiculous number of dimensions to traverse this is rarely noticeable.

Nested arrays also have the ragged array form. Arrays of arrays can have different lengths. Can’t really do that with multi dimensional arrays, unless you use some reserved filler character, like null.

They are also allocated differently. You must know the entire size of a multi dimensional array when you build it. A nested array you only need to know the size of one dimension at a time. And you can allocate them at different times.

They can seem awfully similar when accessing them. But they are as different as arrays and linked lists.

Improve this answer
3
  • 1
    A multidimensional array does not have to be stored without indirection, and a nested array could also be stored and accessed without indirection (and yet retain the current syntax). I suppose what I'm asking is whether the syntactical differences are purely on account of the different implementation details of these arrays? To the programmer, the question whether the access is indirect by offset or indirect by dereference, is often an irrelevant concern - so I'm coming from the perspective that it would be better to have one general syntax and concept for arrays, rather than two.
    – Steve
    Commented Jul 30, 2022 at 12:46
  • In C, there is no syntax difference between the two during usage. Another advantage of a multidimensional array is that it is one contiguous block of ram which could be written to disk in a single system call.
    – user10489
    Commented Jul 30, 2022 at 14:13
  • @user10489, indeed, the difference in syntax for access in other languages tends to be limited to whether you separate the two indexes with brackets or with a comma. And you mention one advantage in terms of storage and access being more efficient (although in Dotnet, the nested version is actually more efficient than the multidimensional version). Is there any other advantage in your view?
    – Steve
    Commented Jul 30, 2022 at 19:55

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.