• 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

How to implement a sparsely populated two-dimensional array.

 
Ranch Hand
Posts: 153
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
How to implement a sparsely populated two-dimensional array.
 
lowercase baba
Posts: 13089
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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?
 
Sheriff
Posts: 22783
131
Eclipse IDE Spring VI Editor Chrome Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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...
 
author
Posts: 9050
21
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
this seems to be headed into more advanced territory...
 
author and iconoclast
Posts: 24207
46
Mac OS X Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Posts: 22783
131
Eclipse IDE Spring VI Editor Chrome Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Marshal
Posts: 28193
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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]
reply
    Bookmark Topic Watch Topic
  • New Topic