• Post Reply Bookmark Topic Watch Topic
  • New Topic

Dynamic NxN matrix  RSS feed

 
Scott Selikoff
author
Bartender
Posts: 4093
21
Eclipse IDE Flex Google Web Toolkit
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What's the best way to implement a dynamic NxN matrix of numbers? Dynamic in that in may start out 3x3, but could increase to 4x4, 5x5, etc? Also, do any features of java 1.5 help?

I thought of doing a double array of Lists in java 1.5 such as: List<List<Integer>>, and adding rows is easy enough (if you take the first list to be a list of rows), but adding columns seems 'not as clean' in that you have to iterate over every row and add a column.

Is there a more balance way to do this? I also considered typed arrays with temporary limits (such as a 10x10 array that starts with a limit counter of 3x3 for example) but that seems annoying as well since I have to rebuild the array if it grows too big.

Anyone have any thoughts on the best way to implement this?
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think that just about any implementation of this is going to have some part of the code that seems a bit cumbersome here, at least when you're writing it. The users of your class don't need to know that, though. How often do you need to do these resizes, anyway?

I'm guessing that if performance is even an issue (I will assume it is, or this question really doesn't matter), it's probably more important for regular operations like getting and setting values than it is for resizing. I would be inclined to use a single flat int[] internally, mapping to a 2D array with simple math. This is pretty fast for all the regular accesses to the array. Using a List<List<Integer>> may be faster on the resize (though not necessarily), but I'm guessing the int[] will be faster on everything else. (That was true several years ago when I experimented with something like this, though it's possible that JVM optimizations have changed things since then.) When you have to resize, it's a bit of a performance hit, but you can minimize this by adopting a strategy like that used by ArrayList and StringBuilder: whenever you need a larger size, just double the previous size. If the user wants to go from 4x4 to 5x5, then 6x6, 7x7, etc., it would be tedious to recopy the internal array each time. Instead, when the user requests an increase from 4x4 to 5x5, you just recopy to an 8x8, and deny access to the unused portions of the array until the size is changed appropriately. When increasing to 6x6, 7x7, 8x8 there's almost nothing for you to do, except update the size limits. After that you increase to 16x16. Since we're talking about a 2D array, doubling the previous size quadruples the overall memory usage, so maybe that's a bit much. Might want to increase by a smaller factor, maybe 1.5 or so. However it may also be useful to have the array dimensions in powers of two, for fast division.

I suppose the choice of strategy here is determined by how important is performance vs. compact representation in memory. Or simplicity of coding, of course.
 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I also went through something similar years ago. Started out with lists of lists, added other lists that threaded these lists for performance reasons, etc. It became just too complicated.

After a few months, I just bite the bullet and implemented a data structure from scratch. As nice as Java collections are, sometimes you just have to implement your own.

Henry
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!