Thread: What is the fastest and most efficient for 3 dimensional structures?

If I have a 3 Dimensional Datastructure, where I am wanting to add to it in order and then later retrieve information from it in order, what data structure would I want to use?

Each dimension of the datastructure has an unknown length and "spot" in the datastructure simply contains Objects (basic things like Strings, Integers, Doubles, ect).

At the moment I am doing a 3 Dimensional Vector, but I have to imagine there is a much more efficient way of doing it. I'm looking for speed (for obvious reasons) and careful memory usage (very large program and high possibility of memory errors).

Any suggestions? And can those suggestions be backed up with information so I can make an informed decision?

I know that in 3D computer graphics work that the most common data structures used are some sort of a tree (Oct trees, Bounding volume hierarchy, KD tree, etc.). However, these structures are designed to allow for spacial ordering (i.e. it's very easy to find something located near a point x,y,z). Most data-structures can be ordered into any dimension you want, and the properties of these data structures extrapolate to multiple dimensions fairly well.

Could you give more details on your particular application?

By, "in order" I mean it is assumed the data will be inputted in order and will outputted in the same order. Basically, I am saying that there should not be a situation where I will be inserting data mid-way through the data structure, but at the end of it each time.

It is effectively a data structure of 2 Dimensional data structures, of rows and columns of data.

To put it in reference, look at an Excel Document. Where each Sheet contains X number of rows and X number of columns. So, a sheet will be a 2 dimensional data structure of rows and columns. And I have a data structure of Sheets. It is complicated, but at the same time quite simple.

Sounds like a queue or stack would work better for you, depending on if you want LIFO or FIFO. Queues are generally implemented using a linked list while stacks fit well with arrays (or ArrayLists/Vectors). In order to get O(1) performance from the array implementations of stacks, you'll need to add/remove from the end of the array.

Well my largest obstacle is memory usage. I am in fact putting this data into an Excel document. Because of the size of the document this program will create (20 sheets and about 600 printable pages) and the inefficiency of the .xml parser in the external library we use, we are constantly running into memory walls, despite increasing the amount of memory JAVA has access to. The memory walls we have been hitting recently has rendered the program useless, so we are having to redesign it.

I am attempting several solutions for creating 16 large sheets, one of which is a 3 dimensional data structure. For those reasons, the 3 dimensional data structure must absolutely be optimize for the smallest memory footprint so we can hopefully overcome the memory problems.

Excel really isn't that good at storing large amounts of data. If it's possible, I'd suggest you ask your company to move towards a database-type solution (something like SQL), then write an interface application which can pull out just the parts you need (and if necessary, write just a small portion of the database into an excel spreadsheet).

When recreating this program, we are in-fact moving to a database to store the 16 sheets of data to reduce the amount of memory usage required. Unfortunately, we cannot move entirely over to a database design because the President(s) and VP(s) who receive these reports want them in paper form (and in notebooks believe it or not). They also want the excel document emailed to them (and a bunch of directors). The Excel document, when printed out, it about 500 pages long. It is what it is...

With the new design I am making, we should not need to read any excel documents (other than a small source document for updating) but instead most of the program's excel work will be revolved around placing and formatting data into an excel workbook that it will create. Basically, the database I made for this program is just to update the data before it is inserted into the excel document so I don't have to read a large excel file and run out of memory.