Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!

How to implement a sparsely populated two-dimensional array.

Nilesh Raje
Ranch Hand
Posts: 153
How to implement a sparsely populated two-dimensional array.

fred rosenberger
lowercase baba
Bartender
Posts: 12127
30
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
Posts: 20532
54
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
this seems to be headed into more advanced territory...

Ernest Friedman-Hill
author and iconoclast
Marshal
Posts: 24211
35
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
Posts: 20532
54
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
Posts: 21107
32
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: 48976
60
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]