Two Laptop Bag*
The moose likes Java in General and the fly likes How to implement a sparsely populated two-dimensional array. Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "How to implement a sparsely populated two-dimensional array." Watch "How to implement a sparsely populated two-dimensional array." New topic
Author

How to implement a sparsely populated two-dimensional array.

Nilesh Raje
Ranch Hand

Joined: Aug 02, 2005
Posts: 153
How to implement a sparsely populated two-dimensional array.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11160
    
  16

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?


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19653
    
  18

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...


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Bert Bates
author
Sheriff

Joined: Oct 14, 2002
Posts: 8803
    
    5
this seems to be headed into more advanced territory...


Spot false dilemmas now, ask me how!
(If you're not on the edge, you're taking up too much room.)
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24183
    
  34

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!


[Jess in Action][AskingGoodQuestions]
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19653
    
  18

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
Bartender

Joined: Oct 14, 2005
Posts: 18541
    
    8

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

Joined: Oct 13, 2005
Posts: 38007
    
  22
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]
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: How to implement a sparsely populated two-dimensional array.
 
Similar Threads
two dimensional array into vector
Two dimensional Array (Strange thing)
Cloneable Object
And the 9th Nov Riddle is ...
Two Dimensional Array in struts