Efficiently accessing a 3-d value using 2-d keys
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
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
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.
long key = (x<<32) | y;
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.
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)?
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?
Originally Posted by dhakier
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.
-- Android Development Center
-- Cloud Development Project Center
-- HTML5 Development Center
-- Windows Mobile Development Center