• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Dynamic NxN matrix

 
author
Posts: 4335
39
jQuery Eclipse IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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?
 
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic