1

I have this 4 Dimensional array to store String values which are used to create a map which is then displayed on screen with the paintComponent. I have read many articles saying that using huge arrays is very inefficient. (Especially since the array dimensions are 16x16x3x3) I was wondering if there was any way to store the string values (I use them as ID values) differently to save memory or reduce fetching time. If you have any ideas or methods I would appreciate it. Thanks!

MrDrProfessorTyler
  • 403
  • 2
  • 10
  • 26
  • Use ... `ArrayList`s instead. – Brian Roach Mar 21 '12 at 22:54
  • Array lists are more efficient than string arrays? – MrDrProfessorTyler Mar 21 '12 at 22:55
  • The only "inefficient" thing about arrays in regard to memory is when you're not using all the elements. ArrayLists are dynamic (But that still doesn't solve a sparseness problem). – Brian Roach Mar 21 '12 at 22:57
  • It sounds like his example doesn't require dynamic size (16x16x3x3). in which case ArrayList would be just as bad if not worse. – JohnnyK Mar 21 '12 at 23:00
  • @Jakrabbit - If it's an issue of sparseness it doesn't help. If it's an issue of under-utilized space (e.g. only X-Y are used out of Z), it would. For something this small ... I personally would just use an array. It smells like premature (and un-needed) optimization. – Brian Roach Mar 21 '12 at 23:02
  • 1
    16x16x3x3 = 2304 references does not sound like a lot to me, if you want to save space, you had better look if strings are really necessary, and if they are, how they are stored - could you expand on how you use the "ID values" and what they comprise of? – Maarten Bodewes Mar 21 '12 at 23:03
  • I guess I will just convert them to ints but I use a00, a01, a02, a03, etc. – MrDrProfessorTyler Mar 21 '12 at 23:06

5 Answers5

4

Well, if your matrix is full, that is every element contains data, then I believe an array is optimally efficient. But if your matrix is sparse, you could look into using more Linking-based data types.

the first thing I would do is to not use strings as IDs, use ints. It'll reduce the size of your structure a lot.

Also, that array really isn't that big, I wouldn't worry about efficiency if that's the only data structure you have. It's only 2304 elements large.

JohnnyK
  • 1,103
  • 6
  • 10
2

Keep in mind that the String values are separate from the array. The array itself takes the same memory space regardless of what string values it links to. Accessing a specific address in your array will take the same amount of time regardless of what type of object you have saved there, or what the value of that object is.

However, if you find that many of your string values represent exactly the same string, you can avoid having multiple copies of the same string by leveraging String.intern(). If you store the interned string, and you don't have any other references to the non-interned string, that frees the non-interned string up to be garbage-collected. Your array will then have multiple entries that point to the same memory space, rather than different memory addresses with equivalent string objects.

See also:

Depending on the requirements of your IDs, you may also want to look into using a different data structure than strings. For example, while the array itself would be the same size, storing int values would avoid the need to allocate extra space for each individual entry.

Also, a 4-dimensional array may not be the best data structure for your needs in the first place. Can you describe why you've chosen this data structure for what you're trying to represent?

Community
  • 1
  • 1
StriplingWarrior
  • 151,543
  • 27
  • 246
  • 315
2

First off, 16*16*3*3 = 2304 - quite modest really. At this size I'd be more worried about the confusion likely to be caused by a 4D array than the size it is taking!

As others have said, if it fully populated, arrays are ok. If it has gaps, an ArrayList or similar would be better.

If the Strings are just IDs, why not store an enum (or even Integers) instead of a string?

John3136
  • 28,809
  • 4
  • 51
  • 69
  • which is more efficient? enums or ints? – MrDrProfessorTyler Mar 21 '12 at 23:05
  • 1
    Rubber stamp answer: "it depends" :) As I said, at 2k elements, size isn't a huge worry. I'd probably go with an enum because it will give you methods to convert enum values to and from strings (assuming you are on any reasonably up to date java version) – John3136 Mar 21 '12 at 23:09
1

The Strings only take up the space of a reference in each array element. There could be a savings if the strings come from a very small set of values. A more important question is are your 4-dimensional arrays sparse or mostly filled? If you have very few values actually specified then you might have a big savings replacing the 4-d array with a Map from the indicies to the String. Let me know if you want a code sample.

Jim
  • 1,161
  • 9
  • 21
0

Do you actually have a 4D array of 16x16x3x3 (i.e. 2k) string objects? That doesn't sound that big to me. An array is the most efficient way to store a collection of objects, in terms of memory. An ArrayList can be slightly less efficient (up to 50% wasted space).

The only other way I can think of is to store the Strings end-to-end in one giant String and then use substring() to get the bit you need from that, but you would still need to store the indexes somewhere.

Are you running out of memory? If so check that the Strings in your array are the size you think they are - the backing array of a String instance in Java can be much larger than the string itself. If you do subString() on a 1 GB string, the returned string instance shares the 1 GB array of the first string so will keep it from being GC'd longer than you might expect.

gub
  • 5,079
  • 3
  • 28
  • 33