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

• December 10th, 2010, 04:06 PM
aussiemcgr
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?
• December 10th, 2010, 06:27 PM
copeg
Re: What is the fastest and most efficient for 3 dimensional structures?
Can you define 'add to it in order'? Do you mean order based upon when it was added, or order based upon the some sorting algorithm? And if the latter, will you need to access the elements in the appropriate order many times in between additions? Should each list ever possibly contain duplicate values?
• December 10th, 2010, 06:45 PM
helloworld922
Re: What is the fastest and most efficient for 3 dimensional structures?
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?
• December 10th, 2010, 08:39 PM
aussiemcgr
Re: What is the fastest and most efficient for 3 dimensional structures?
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.
• December 10th, 2010, 08:51 PM
copeg
Re: What is the fastest and most efficient for 3 dimensional structures?
Perhaps others might suggest alternatives but I'd say you are on the right track. If you do not need multi-threading protection, an ArrayList would be faster since is not synchronized (Vector is synchronized).
• December 11th, 2010, 10:02 AM
helloworld922
Re: What is the fastest and most efficient for 3 dimensional structures?
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.
• December 11th, 2010, 11:03 AM
copeg
Re: What is the fastest and most efficient for 3 dimensional structures?
To add a more object oriented option, you could try and hide the complexity of a 3D List inside an object. Based upon the model you describe above, create a class SpreadSheet which itself contains the 2D list. Then all the client sees a List of spreadsheets. You could then have the Spreadsheet class encapsulate the 2D list by providing get/setCellValue(int row, int col) accessors. Although it doesn't directly increase the efficiency of the runnable code, in my opinion could make it much more readable, expandable, reusable, and from a programmer's standpoint could increase the efficiency of writing the code.
• December 11th, 2010, 03:13 PM
aussiemcgr
Re: What is the fastest and most efficient for 3 dimensional structures?
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.
• December 11th, 2010, 04:06 PM
copeg
Re: What is the fastest and most efficient for 3 dimensional structures?
While I don't know exactly the purpose of all the data and how it will be used, this sounds like something that can be better handled by storing the data within a relational database. If designed appropriately redundant information can be pulled out into their own tables which depending upon the data reduce a good amount of the memory usage. Also has the advantage of being able to query the data model to pull out appropriate information, and query the model in unique ways to provide better data analysis and reporting. Again, no idea what the goal so its hard to be sure.
• December 11th, 2010, 06:25 PM
helloworld922
Re: What is the fastest and most efficient for 3 dimensional structures?
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).
• December 11th, 2010, 06:50 PM
aussiemcgr
Re: What is the fastest and most efficient for 3 dimensional structures?
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.