Efficiently accessing a 3-d value using 2-d keys


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 4 of 4

Thread: Efficiently accessing a 3-d value using 2-d keys

  1. #1
    Join Date
    Dec 2004
    Posts
    34

    Efficiently accessing a 3-d value using 2-d keys

    Hello folks,

    I'm doing a graphic widget which has a component that draws a grid and some graphical marks. The marks are stored in a Set, so all I have to do is draw the grid and iterate the set to draw the marks. Each of them holds 3 values: X coordinate, Y coordinate and Z coordinate (in my case, the Z coordinate is displayed as an int in a square on the grid).

    But there's the possibility to group marks: two marks with the same X and Y coordinate have to combine themselves to generate another mark with the Z coordinate being Z1 + Z2 (the sum of each other marks). So, each time I'm trying to add a new mark, I have to check if there is an existing mark already there.

    My question is: how do I make it more efficient? By allocating a 2-d array of marks (and probably getting a LOT of empty spaces), or by making use of some sort of "bi" hashtable? Or should I combine the X and Y coordinates to make it a single key and use it to access the position in the hashtable?

    I'm considering the 2-d array because it seems simpler and faster to access, but I don't know precisely how many memory would it waste, so if there were a better solution...
    Last edited by dhakir; 04-15-2005 at 09:35 PM. Reason: Unclear title

  2. #2
    Join Date
    Mar 2005
    Location
    Sendling, MUC, .de
    Posts
    100
    You have to decide on priorities for the different goals
    • time efficiency (how long it takes to compute)
    • space efficiency (how much memory's required)
    • readability / simplicity (depends on what you think is readable/simple)
    • ease of implementation (how long it takes you to write the stuff)

    There is a tradeoff between each two of these goals.

    As far as I'm concerned, I'd use a TreeMap with the keys being longs made up of the two integer (they are integers, are they?) coordinates X and Y like
    Code:
    long key = (x<<32) | y;
    TreeMap guarantees log(n) time for put and remove operations and linear space, ie for some small constants c, k and n key-value mappings, at most c+k*n bytes of memory are used.
    The main reason for TreeMap is that you benefit from the natural order of the keys.

    A Hashmap in turn offers average constant time for access but not in the worst case (then linear, worse than log(n)). And it does NOT offer linear space complexity as it is based on some backing array that is usually considerably larger than the number of entries. Also, if the backing array becomes too small, an expensive (wrt time and space) re-hashing is performed.

    A 2d integer array is probably out of question, since if your coordinates are in the range [min,max], you would need (max-min) entries or 4*(max-min) bytes of memory. Compare this to the estimated number of coordinates.
    If you cannot limit the range of numbers (a coordinate can be any of the roughly 4 billion integers) - well figure it out yourself...
    But since you're displaying that grid, the range can't be too large I guess. So up to about 1000 ~ 4MB you could do it. What you'd get is indeed constant access time but it definitely is not elegant.

  3. #3
    Join Date
    Dec 2004
    Posts
    34
    Thanks for the help...

    I think I'll stick with the Map, but now I've got another problem: I can't use ints to make the key because I realized that, instead of using the values' x and y coordinates (as I had considered), I'll have to use the values themselves. This is because sometimes the grid is zoomed in, so some values are lost, therefore the marks lose their coordinates and I can't use them to generate the keys again.

    So, my new question is: how do I combine two objects (which can be Strings, Integers or some similar kind of value) to generate a key? Do I have to make a new class and reimplement equals(), or is there a simpler way (like an ObjectPair class or something like that)?

  4. #4
    Join Date
    Mar 2005
    Location
    Sendling, MUC, .de
    Posts
    100
    Quote Originally Posted by dhakier
    ...I'll stick with the Map...
    Yep. BTW: whenever you refer to the thing you should do this by the least specific type possible - so be it a TreeMap or a Hashtable, you're essentially using it as a Map and this you should make explicit in your code. See what I mean?

    As for your new question: you're thinking about a generalization of what I have proposed for combining two integers into one long, right?
    You do it exactly as you said. AFAIK there is no such class like ObjectPair in the API, but rolling your own ain't hard. Simply delegate in ObjectPair.equals() to component1.equals(...) && component2.equals(...).
    : Beware of bugs in the above code - I have only proved it correct, not tried it.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center