Arrays of arrays - or 2D arrays. How to program tables.
Archive - Originally posted on "The Horse's Mouth" - 2011-01-02 19:49:43 - Graham Ellis
It's shorthand when you're learning a new programming language to ask "how does it handle multiple dimension arrays" ... but in practise very few languages actually support true multidimensional arrays these days, and in those which do you might be well advised to use an alternative that's more flexible.
What is a true - proper - two dimensional array? It's a series of successive locations in the computer memory which represents a rectangular table. For example, I could have each 'row' representing a room at our hotel (so that's 1 to 5) and each 'column' representing a day of the month (1 to 31 this month). So that would be 155 memory locations, each of which might contain a number which is the amount we're charging for that room on that night.
Row 1, Column 1. Cell 1. 95.00 (1st of month, room 1)
Row 2, Column 1. Cell 32. 85.00 (1st of month, room 2)
Row 4, Column 10. Cell 103. 85.00 (10th of month, room 4)
Where you need a fixed number of columns in each row, this system can work very well ... but it turn out that this is rarely the case. If you have a separate row for each member of your staff, and then columns to hold the names of their children, you'll find yourself having to decide very early on (perhaps far too early) what the maximum number of children should be, and then you'll find that you've often got a very great deal of wasted memory. We used to have a staff member with six children, and we have a delegate on a course a couple of years back who was one of 22 siblings - just think how much memory would have to be put aside "just in case" if we were to use a rectangle system, where every row must allow for the same number of columns. Diagram - a true two dimensional array, showing how only a few of the cells are actually used
Let me describe the better alternative - and that is an array of arrays (or a list of lists). In this case, you'll have an array with just a single dimension which holds the memory address at which the actual data for each column starts. In the case of my rooms / rate each day, this first single-dimensioned array would perhaps contain:
Row 1 starts at Memory address 1000
Row 2 starts at Memory address 2000
Row 3 starts at Memory address 2400 etc and then the size of each of the arrays that they point to can differ. In the case of days of the month, it's unlikely to make any great difference to the 2 dimensional array (in fact it may be marginally less efficient), but in the majority of cases - of which my staff member example is just one - you'll save huge amounts of space.
Languages such as C and C++, in their fundamental form, use true two dimensional arrays, but using functions such as malloc (in C) and heap objects (C++) you can use the "array of arrays" model instead. Not only does it make for a saving of space, but it also means that memory can be dynamically allocated as you write your program, rather than you having to make a decision as to what maximum you should allow at some point in the development process.Diagram - a list of lists showing the saving of memory and the extra flexibility
With most of the other languages that we teach, you'll actually use arrays of arrays all the time - although the syntax used is very often such that it looks like you are using true two dimensional structures. There's an example of that [here] in PHP, and one [here] in Perl. There's one [here] in Java and one [here] in Python.
((There's an example of a true two dimensional array in C [here] and various C examples that use malloc [here].))
Where you need a fixed number of columns in each row, this system can work very well ... but it turn out that this is rarely the case. If you have a separate row for each member of your staff, and then columns to hold the names of their children, you'll find yourself having to decide very early on (perhaps far too early) what the maximum number of children should be, and then you'll find that you've often got a very great deal of wasted memory. We used to have a staff member with six children, and we have a delegate on a course a couple of years back who was one of 22 siblings - just think how much memory would have to be put aside "just in case" if we were to use a rectangle system, where every row must allow for the same number of columns. Diagram - a true two dimensional array, showing how only a few of the cells are actually used
and then the size of each of the arrays that they point to can differ. In the case of days of the month, it's unlikely to make any great difference to the 2 dimensional array (in fact it may be marginally less efficient), but in the majority of cases - of which my staff member example is just one - you'll save huge amounts of space.