• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

How to implement a sparsely populated two-dimensional array.

 
Nilesh Raje
Ranch Hand
Posts: 153
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
How to implement a sparsely populated two-dimensional array.
 
fred rosenberger
lowercase baba
Bartender
Posts: 12083
29
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Not exactly sure what you mean by 'sparsely populated', or why it would be different from a 'densely populated' one (whatever that is).

Can you elaborate a little more?
 
Rob Spoor
Sheriff
Pie
Posts: 20493
54
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think this is what Nilesh means:

A matrix is usually implemented by an actual 2D array: T[][]. However, this requires, for an M by N matrix, M*N references to T. If many of those are null, you waste a lot of space.
You can instead use a linked list of sorts, where each node has a reference to the next non-null cell (or non-0 / non-false for primitives). Implementing this was an exercise in my 2nd year of University.

Seeing as that is 9 years ago, I can't remember any of the details though...
 
Bert Bates
author
Sheriff
Posts: 8898
5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
this seems to be headed into more advanced territory...
 
Ernest Friedman-Hill
author and iconoclast
Marshal
Pie
Posts: 24208
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
One easy way to do it is to use a Map. Let the keys be Strings that look like "M,N" where M and N are the array indices. That way if you have a 100x100 array with 5 elements in it, you've got just a Map with the five key/value pairs stored. Write get/set methods like



and you're all set!
 
Rob Spoor
Sheriff
Pie
Posts: 20493
54
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'd use a Map<Point,T> instead. That makes it easier to parse back if needed, and it is most likely more efficient than a string too. String has a char[] and three ints as fields, whereas Point only has two ints.

Of course Point does have the drawback of being highly mutable, but as long as you don't publicize the Point objects that's not a problem.
 
Paul Clapham
Sheriff
Pie
Posts: 20724
30
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
One of the things not mentioned in the original requirements description was whether you want to find all the entries in a row of the array. Or whether you want to find all the entries in a column. That would influence whether you used a bunch of linked lists, or a map, or something else.
 
Campbell Ritchie
Sheriff
Posts: 48378
56
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You create your own Point classThis is an immutable class, and final (so you can safely use instanceof in the equals method) and works out its hash code early (because you intend to use it in structures which use hash codes frequently). The hash code is worked out on the assumption that you will be using values between 0 and 100, and the % operators are so as to get more variability in the low-order part of the hash code. It is probably full of spelling errrors, but you will find them out when you get the compiler errors.

[pedantic mode]By the way, there is no such thing as a two-dimensional array in Java, only an array of arrays.[/pedantic mode]
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic