Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Abstract:

So, as I understand it (although I have a very limited understanding), there are three dimensions that we (usually) work with physically:

The 1st would be represented by a line.
The 2nd would be represented by a square.
The 3rd would be represented by a cube.

Simple enough until we get to the 4th -- It is kinda hard to draw in a 3D space, if you know what I mean... Some people say that it has something to do with time.

The Question:

Now, though that doesn't all make much sense, that is all great with me. My question isn't about this, or I'd be asking it on MathSO or PhysicsSO. My question is: How does the computer handle this with arrays?

I know that you can create 4D, 5D, 6D, etc... arrays in many different programming languages, but I want to know how that works.

share|improve this question
12  
Sharing your research helps everyone. Tell us what you've tried and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see How to Ask –  gnat Jul 2 at 21:28
6  
@gnat "...what you've tried and why it didn’t meet your needs..." I am not trying to get this to work -- I am trying to understand why it does work.... –  Questionmark Jul 2 at 21:30
65  
If 3 dimensions can be visualized as a cube, then 4 dimensions can be visualized as a bunch of cubes in a line. 5 dimensions can be visualized as a grid where each cell in the grid contains... a cube! And so on... The "Fourth Dimension" has nothing to do with time (whatever that is), unless you define it as such in the context of the semantics of your program. –  FrustratedWithFormsDesigner Jul 2 at 21:35
14  
In general, you can get over this conceptual hump by trying to avoid thinking of dimensions as strictly physical constructs. For example, some machine learning problems can have a dimensionality in the hundreds of thousands, where each dimension is a feature of the dataset. –  Steve Evers Jul 3 at 0:42
24  
Remember that the computer doesn't care about the idea of geometric dimensions--those are just a device for human convenience. If you allocate a 5x5x5x5 array, the computer just allocates an array of 625 elements and does math with your indices accordingly. –  David Zhang Jul 3 at 2:58

11 Answers 11

up vote 75 down vote accepted

Fortunately, programs aren't limited by the physical constraints of the real world. Arrays aren't stored in physical space, so the number of dimensions of the array doesn't matter. They are flattened out into linear memory. For example, a single dimensional array with two elements might be laid out as:

(0) (1)

A 2x2 dimensional array might then be:

(0,0) (0,1) (1,0) (1,1)

A three dimensional 2x2x2 array might be:

(0,0,0) (0,0,1) (0,1,0) (0,1,1) (1,0,0) (1,0,1) (1,1,0) (1,1,1)

You can hopefully see where this is going. Four dimensions might be:

(0,0,0,0) (0,0,0,1) (0,0,1,0) (0,0,1,1) (0,1,0,0) (0,1,0,1) (0,1,1,0) (0,1,1,1)
(1,0,0,0) (1,0,0,1) (1,0,1,0) (1,0,1,1) (1,1,0,0) (1,1,0,1) (1,1,1,0) (1,1,1,1)
share|improve this answer
9  
Computer arrays are not limited by human comprehension or visualization, but they're limited by physical constraints, e.g. an array of d dimensions each of length n will take n^d, or more generally with different length dimensions, n1 × n2 × … × nd. –  Paulo Madeira Jul 2 at 23:25
6  
@ColtonAllen: I'm not quite sure what you're referring to. The definition of dimension says "Roughly speaking, it is the number of coordinates needed to specify a point on the object." An array declared in C as int a[2][2][2]; would be a 3-dimensional array. –  Greg Hewgill Jul 3 at 0:23
4  
"Fortunately, programs aren't limited by the physical constraints of the real world" So thats why all we have processors at 4.5THz, and no one cares about the memory hierarchy, isn't? This is really the most funny answer I have readed.... –  Manu343726 Jul 3 at 15:32
23  
@Manu343726 He's referring to the fact that we live in (theoretically) limited dimensions of space and time, but arrays in computer memory have "pretend" dimensions - it's all stored in a linearly contiguous space in memory - so they are not limited to the number of dimensions we live in. Don't troll >:( –  Blackhawk Jul 3 at 16:38
14  
@Manu343726: I carefully said Programs, not Computers. That's one of the great things about software. –  Greg Hewgill Jul 3 at 17:27

An array is only a block of continous memory. Memory addressing is one-dimensional, you can either go forward or backward. So assuming you have an array with 5 elements, 5 memory blocks will be reserved. If you have a 2-dimensional array with 5 elements in each dimension, 25 memory blocks will be reserved.

share|improve this answer
5  
Yes, keep this in mind as you add more dimensions to your arrays. Memory usage may not be trivial. –  davidhaskins Jul 2 at 21:35

The dimensions are whatever you want to be, the 4th dimension doesn't necessarily have to be time. If you think of three dimensions as a cube, you can think of 4 dimensions as a row of cubes. 5 dimensions, a grid of cubes, and so on.

You could also have a 3d collection of voxels, with a 4th dimension being color, or density, or some other property.

When you allocate the memory for your multidimensional array, it just simply allocates the product of each dimensions maximum for your data type. If you have a 3d array or 'cube' of 10 elements in each dimension, you'll have 1,000 elements allocated. If you make that a 4d array with 10 elements in the 4th dimension, the computer will just allocate 10,000. Bump it up to 5 dimensions, and it will allocate 100,000.

The computer doesn't care about any sort of meaning about what each dimension represents. To select where in the list of elements a single point is, it's just multiplication to select a memory address.

share|improve this answer

...or I'd be asking it on MathSO...

Well, as a matter of fact mathematicians would never (or at least not usually) associate a fourth dimension with anything like time. Nor would they associate the first three ones with anything space like: mathematicians simply define dimension as an abstract property of, typically, a vector space (often this will be generalised to manifolds or even metric spaces). And this abstract definition doesn't care about how many dimensions the physical space we happen to move in has. The concept of dimensions applies to spaces that don't even resemble the physical space. In fact mathematicians (and indeed physicists) very often use infinite-dimensional spaces, such as the Hilbert spaces of quantum mechanics.

With that clarified, let's talk arrays – you don't need to understand vector spaces, since the abstract definition is actually much simpler here.

An (0 × 1 × 2 × ... × n−1)-sized array (i.e. of dimension n) is simply a collection of 01 ⋅ ... ⋅ n−1 numbers (or whatever type of object populates the array). The only difference to a one-dimensional array of that length is that you have a particular useful way of indexing the dimensions seperately, namely

ilin = in−1 + n−1 ⋅ (in−2 + n−1 ⋅ ( ... 2 ⋅ (i1 + 1i0)...))

share|improve this answer
    
To be clear, you only need an array with 3 elements to describe 3 dimensions, and an N element array describes N dimensions. However, detailing every vector is a different story. Often times, it's done by showing an image (imshow in Python) -- it can show two spatial dimensions as well as a third color dimension. –  Scott Jul 7 at 3:23
    
@Scott: I agree the notion of "dimension of an array" is unfortunate because it means something unrelated to the dimensionality of a space whose vectors you might represent by the arrays. (However I also think it's not such a good idea to represent vectors by plain, unabstracted arrays in the first place.) A better name might be the rank of an array, in analogy to tensors. –  leftaroundabout Jul 7 at 9:44

You don't need to imagine in high spatial dimensions, just think of it as a fern leaf. fern leaf

The main stalk is your first array, with each branch being an item that it is storing. If we look at a branch this is your second dimension. It has a similar structure of smaller branches coming of it representing its data. These in turn have their own small branches which continues until we get to the tiny leaves representing the data of the inner most or highest dimension array.

You can see this building up if you declare each level with its own name. Here I am reusing each level varible to minimise the code:

leaf = 2;
tinyBranch = [leaf, leaf, leaf];
middleBranch = [tinyBranch, tinyBranch, tinyBranch];
bigBranch = [middleBranch, middleBranch, middleBranch];
mainBranch = [bigBranch, bigBranch, bigBranch];
share|improve this answer
1  
Wouldn't this visualization more closely represent a jagged array? –  Matt Johnson Jul 3 at 22:25
2  
@MattJohnson Formally yes, but this example does explain/visualize multi-dimensional arrays as well. –  M.Mimpen Jul 4 at 8:14
4  
+1 this is not only a neat visualization, but closer to the truth than the linear explanation for many array implementations. Whether or not most people here would restrict the term "array" to contiguous memory, "multidimensional array" is certainly the term used for such arrangements in the literature for many languages. –  imsotiredicantsleep Jul 5 at 21:17

Imagine doing R&D on some new medical device, a series of sensors that you put along a patient's arms. You have seven volunteers lined up for testing. Each sensor reports low-frequency, mid-frequency, and high-frequency readings, which you take once every 100ms for about a minute.

How to store all that data in memory for analysis and plotting?

An array, obviously. It would look like this (using made-up generic pseudocode):

npatients = 7
nsensors = 4     // number of sensors on an arm
nchannels = 3
nsamples = 60.0 / 0.1
sensordata = Array[ npatients, nsensors, 2, nchannels, nsamples ]

That's a five dimensional array, and there's nothing tricky, mysterious or baffling about it. There is no reason to try to associate it with 5-dimensional Euclidean space. To obtain any one data value, we use an expression like

x = sensordata[6, 5, 1, 2, 338)

It just like querying a relational database where you have a record for each data value, with five columns holding patient id, sensor id and so on, and a column with the value. To get one data point you use five terms in the WHERE: SELECT value FROM SensorData WHERE (patientid=6) and (sensorid=5) and (arm="left") and (channel="midfreq") and (sampleindex=338).

There is nothing mystical about a database table with five or more columns, is there?

(I'm using 1-based indexing though in real life, 0-based is much more common.)

Note that I'm a bad boy due to hard-coding the number of arms. If I'm ever given funding to investigate these sensors on an octopus, I'm in trouble!

share|improve this answer
1  
+1 Excellent example demonstrating that dimensions can be any data that you require. –  Mike Jul 3 at 2:19

In programming, arrays are quite easy to implement, but maybe not to understand.

Generally, each level of arrays means to have the content n-fold. That means

  • int x[4] are 4 blocks, each of them containing an int.
  • int x[5][4] are 5 blocks, each of them containing an int[4].
  • int x[3][5][4] are 3 blocks, each of them containing an int[5][4].
  • int x[2][3][5][4] are 2 blocks, each of them containing an int[3][5][4].

How you are referring to them is up to you, but for better understanding, you have something like

  • COLUMN for the last one
  • ROW for the second-last one
  • PAGE for the third-last one

Till here, I read it somewhere. In order to stay here, we can as well define

  • BOOK for the fourth-last one
  • and maybe SHELF for the fifth-last one. (Or, if you prefer, SHELFROW so that we can continue.)

That said, I never saw array with more than 4 or maybe 5 dimensions in "wild life".

This way, you can define and imagine int x[6][2][3][5][4] as a collection of 6 "shelves", each having 2 books, each having 3 pages, each having 5 rows, each having 4 columns.

share|improve this answer

Think of a one-dimensional array like a chest of drawers:

chest of drawers

Each drawer is an index of the array. You can put whatever you want in each drawer, and for many purposes, each drawer will only contain a single item (that's a one-dimensional array).

This chest of drawers is magical though, so it's not limited by physical space. That means that you can put another chest of drawers inside each drawer of the first chest of drawers. The inner chests of drawers can then contain whatever you want. That's a two-dimensional array.

So you can say something like "open up the top drawer of the first chest of drawers, get the chest of drawers out of that drawer, then open up the bottom drawer of that second chest of drawers". That would be like accessing an index of a 2D array: myArray[0][3];

And of course, the chests of drawers inside the outer-most chest of drawers can themselves contain chests of drawers. That's a three-dimensional array.

So, your question is: what's a four-dimensional array? It's a chest of drawers of chests of drawers of chests of drawers of chests of drawers, of course!

It's drawers all the way down.

share|improve this answer
4  
It's chests of drawers all the way down, man. –  Thomas Eding Jul 3 at 18:39
8  
And in the last chest of drawers? Turtles. –  Kevin Workman Jul 3 at 18:43
    
Being slightly pedantic. Given there are 3 drawers in each chest (based on the picture), not 4, and you are using a base 0 index, the bottom drawer would be 2 not 3. So instead of myArray[0][3] it would be myArray[0][2]. But otherwise good explanation. –  Tom Heard Jul 3 at 21:34
    
@TomHeard The first chest of drawers has 3 drawers, but the chest of drawers inside of the first drawer has 4 drawers. Duh! :p –  Kevin Workman Jul 3 at 21:51
1  
Oh then that is fine. =D –  Tom Heard Jul 6 at 21:00

In the Cartesian coordinate system, you have the x and y axes on a plane. You can represent any number on the plane as (x,y).

In three-"space" (otherwise known as a cube), you can have the x, y, and z axes. You can represent any element of the cube as (x,y,z).

In multivariate space, you can have the x, y, z and, w axes (where the w axis is "imaginary"). You can represent any element of that space as (x, y, z, w).

All of these points in space are denoted by vectors. In four-space, you can have two vectors, where v1 =(x1, y1, z1, w1), and v2 =(x2, y2, z2, w2). Then you manipulate these vectors as you would numbers. For instance, the sum of the two vectors, v1+ v2 would be (x1, y1, z1, w1)+ (x2, y2, z2, w2). Then you add these vectors term by term as you would numbers, to get: (x1+x2, y1+y2, z1+z2, w1+w2).

Your program will define the vectors using appropriate arrays, and then perform arithmetic operations on them in the appropriate order.

share|improve this answer

In physics, we assume each spatial dimension to be infinite, which makes finding space for new dimensions pretty difficult.

When dealing with finite arrays, it's easy to find space.

Imagine a sheet of paper with a grid printed on it; you can write some information in each cell of the grid. That's a 2D array: row and column.

Put several of those sheets of paper in a file folder; that's a 3D array: page, row, and column.

Put several of those folders in a file box. 4D array: folder, page, row, column.

Arrange boxes in a rectangular grid on a wooden pallet. 6D array: box-row, box-column, folder, page, row, column.

Stack more grids of boxes on top of those. 7D array: box-depth, box-row, box-column, folder, page, row, column.

Start cramming pallets into a shipping container: 9D array. (Assuming each stack is as tall as the inside of the container, so you can only get 2 more dimensions here.)

Stack up shipping containers on the deck of a container ship: 12D array.

Your fleet of container ships is now a 13D array.

share|improve this answer
    
"we assume each spatial dimension to be infinite" infinite isn't the biggest deal here actually, continuous is the "real" problem (i.e. over-countably infinite, and we need a homeomorphic mapping so it's physically meaningful). –  leftaroundabout Jul 4 at 11:01

Most of the aspects of this question have already been considered, but I think it will help if you consider the nature of a dimension. Not all dimensions are spatial. A dimension is a context for measurement. Here are some examples:

  • Frequency - colour or pitch
  • Mass
  • Valence
  • Colour (up quark, down quark, strange quark, charmed quark etc)
  • Spin direction
  • Angle
  • Loudness
  • Hotness (of chili)

The "fourth" dimension is only fourth because there are three spatial dimensions. Space and time loom large because, well, they loom large. Very much in-your-face. But any quantifiable, measurable quality can be a dimension if you measure it.

For example, brassieres have three dimensions: cup size, chest size and interstitial (I don't know what you girls call it but I mean the distance between cups).

share|improve this answer
1  
"Not all dimensions are spatial." For arrays, all dimensions are spatial. –  Rhymoid Jul 5 at 17:03
2  
@Rhymoid: For arrays, no dimensions are inherently spatial in the way we think about space. :P We define them to represent whatever we want. –  cHao Jul 6 at 16:37
    
@cHao Maybe if you look at the semantics of the data they store. But on the representational/syntactic/implementation side of things, all array dimensions are inherently spatial. It's actually what you depend on when using arrays as part of an algorithm. –  Rhymoid Jul 6 at 16:42
    
@Rhymoid: That is the same thought process that led to this question being asked in the first place. A dimension being enumerable doesn't make it spatial. Implementationwise, there is no space. There is only memory, and memory is one-dimensional as far as a program knows/sees/cares. –  cHao Jul 6 at 16:59
    
@cHao: implementationwise, there is space, because there is also time. The term 'space leak' (as an alternative for 'memory leak', found in the Haskell community) is no coincidence. The fact that memory is described as one-dimensional is a heritage from BCPL. –  Rhymoid Jul 6 at 18:13

protected by gnat Jul 5 at 12:19

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.