Is there a way to implement something like a "broken" 3dimensional array?

Question

I have an algorithm that creates instances of objects in 3d space, to avoid double placement i have to loop through all of them for each instance to find out if an instance has the same id as an already existing one.

My dream solution would be a 3 dimensional array that i can reference via x y z coordinates. However I guess it is impossible due to ram restrictions.

So i was wondering if there is something like a "broken" array that i can still reference via Array[x][y][z], but works like a list, so if that specific x y z was never declared, it just doesnt exist and thus doesnt fill up the ram.

I'd highly appreciate if someone could point me in the right direction to what I am actually looking for and maybe even provide some code example of how to implement it.

The way I do it now takes a performance hit at more than 8k objects, so I'd say at least double that as I have absolutely no issues below that value — user3488765, Apr 02 '14 at 10:04
Similar question to http://stackoverflow.com/questions/12626135/memory-efficient-sparse-array-in-java — Daniel Renshaw, Apr 02 '14 at 10:11
@ Sebastian I am just a hobby programmer, but looking up what you said looks like it may be what i need, maybe you could give an example of how to implement that? — user3488765, Apr 02 '14 at 10:12
Please don't add the word 'solved' to the title. People can see your question is answered when you accept an answer. — George Stocker, Apr 02 '14 at 12:11

Bob Sammers · Accepted Answer · 2014-04-02T12:59:27.523

Have you considered the Dictionary<> collection? If you used an object with three coords as the key (you'll presumably have a vector class or struct for your coordinates already?), you can look up a specific set of coords quickly (close to O(1)); there is a ContainsKey() method which will tell you whether another object exists at any given position.

There are two complications:

You cannot have duplicate keys, so you must not need to have more than one object at any given set of coords.
The speed of lookup depends on the hash function of the key type, which in your case will presumably be a 3d vector class / struct you roll yourself. You will need to invest a little time implementing a decent hash algorithm for this.

Edit: I should have mentioned that you can use a tuple<> as the coordinate vector / key. It already has an implementation for GetHash(), but you may find (since you are using significant numbers of objects) that overriding this with a more specialised version increases your performance.

Is there a way to implement something like a "broken" 3dimensional array?

1 Answers1