-2

I'm trying to find an efficient way to represent a grid in any number of dimensions. I would want to be able to specify a set of coordinates and then get the value stored in the location on the grid. I would also like to simply move any number of squares in any dimension easily. How could I create a data structure like this?

closed as too broad by Ixrec, Basile Starynkevitch, David Hammen, gnat, Jörg W Mittag Apr 3 '16 at 0:36

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • Do the grid's dimensions have fixed maximums? – Kasper van den Berg Apr 2 '16 at 12:15
  • 1
    What are the requirements for the data structure? – Kasper van den Berg Apr 2 '16 at 12:31
  • 3
    Please edit your question to improve it (it is unclear) and give much more motivation and context. What concrete problem are you trying to solve? What is this grid representing? It smells like some XY problem – Basile Starynkevitch Apr 2 '16 at 14:09
  • 2
    What language? What kind of data? How big? Are the data sparse or not? What problem are you trying to solve? – David Hammen Apr 2 '16 at 14:27
  • 2
    I voted to close as "too broad". Attempting to solve this problem has lead to multiple packages (CDF & NetCDF, HDF4&5, GRiB, numpy/scipy, ...), and even multiple languages (APL, Fortran, MATLAB, R, ...). – David Hammen Apr 2 '16 at 14:41
4

When the grid's dimensions have fixed maximums you have a simple multi dimensional array; i.e. int grid[10][10][10][10] for a four dimensional grid. (Should your language not support multi dimensional arrays, you can simulate it via int index(int x, int y, int z, int t) { return x + (nX * y) + (nX * nY * z) + (nX * nY * nZ * t); })

When the dimensions' maximum can grow (and shrink) you can use nested lists or a graph; but they might not satisfy your performance requirements.

  • 1
    I feel like this would get really inefficient as you increase dimensions, like if I wanted a 10d array. Is there a better way to do this (maybe without arrays)? – thesecretmaster Apr 2 '16 at 12:33
  • 2
    If the grid is densely populated (ie the ratio of occupied cells to unoccupied ones is high) then this is absolutely the way to go, yes even to 10-D and beyond. If the grid is sparsely populated OP has omitted very important information from the question. – High Performance Mark Apr 2 '16 at 12:38
  • @HighPerformanceMark What if it was sparcely populated? – thesecretmaster Apr 2 '16 at 12:41
  • 2
    If it was sparsely populated OP should have mentioned it in the question where it would have attracted notice. – High Performance Mark Apr 2 '16 at 12:47
1

You say you want to represent the 'grid' but of course you needent actualy do so.

If you define your 'point' object with the required number of dimensions:

Class Point
{
    int x;
    int y;
    int z;
    ....
}

Then you have in essence defined the 'grid' in which they exist without the need for a datastucture for the grid itself.

Looking up a point at a position is simply a matter of storing your points in a suitably indexed list or hashmap.

Moving it is again simply a matter of changing its coordinates.

1

It might be better called a matrix or multi-dimensional array.

You should notice that, in general, such multi-dimensional arrays contain a lot of elements. For example, a array of dimension 10 20 30 contains 10*20*30 that is 6000 elements, and it is considered small (since 10, 20 and 30 are small). But an array of dimension 8 8 8 8 8 8 8 8 8 8 (ten occurrences of 8) has 230 elements (if each element was a 32 bits int i.e. 4 bytes, that requires 4Gbytes of RAM) and each of the individual dimension is 8, a quite small number.

You first need to estimate the amount of elements to be kept. It could be large enough to not fit into your computer (then your problem is practically unsolvable, or untractable, and you should change your approach entirely or get some much bigger computer). Read about Cobham's thesis and combinatorial explosion. If you want to keep all the elements you'll need a multi-dimensional array, like Kasper van den Berg answered.

Sometimes you know that the grid or matrix is sparse (most of the elements are 0), or that it has some other property (e.g. it is symmetric, anti-symmetric, triangular). Then you should state its properties in the question (therefore you need in general to ask yourself: what are the properties I know about such a grid? how can I characterize it?).

Sparse arrays might be represented by hash tables or maps (mapping index tuples to non-zero elements).

Read also about graphs & hypergraphs & relations (and perhaps even inference engines). Perhaps they might be better suited to your concrete problem (which you forgot to mention).

J.Pitrat's blog has some interesting insights, in particular: Is it possible to define a problem?

-1

@Basile Starynkevitch's answer is great, but it skims on dense matrices a bit. They can be represented as one dimensional arrays in code.

Saying you have something like an n-dimensiona cuboid. With say, four dimensions, you could do it something like this:

x1 + side1 * x2 + side1 * side2 * x3 + side1 * side2 * side3 * x4

Where side1..side3 are the matrix' sides and x1..x4 are coordinates. There might be a bug somewhere, but you get the idea.

Although it does take a lot of memory. Say, 1000x1000x1000x1000 matrix of single precision floats is 4TB (decimal tera, not tebi)!

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