Efficient Data Type Needed

Thread view:

Brian Bagnall - 19 Dec 2006 22:37 GMT

This is different from my last question. I need a data type that can store a
bunch of values for a map made up of x, y coordinates. However, I don't want
to store a value for *every* point on the map. For example, most of the map
will be grey, but perhaps the point at x=23 and y=34 will be blue. So I store
a value 6 at 23, 34. And at maybe 100, 123 I store a value of -2. etc...

When it comes time to draw this map, I want it to redraw quickly, so I don't
want to have to look through each and every array value in a 200 x 200 array.
I would rather just get one after another of the values that happen to be
stored with some non-zero value. So if my map only has the two points I
mentioned above, it should retrieve the first value that says "23, 34, 6" and
then "100, 123, -2"

On top of this, I would like to be able to tell it two coordinates and have it
return the value for that point. e.g. getVal(100, 123) ... returns -2.

- Brian

Reply to this Message

Matt Humphrey - 20 Dec 2006 00:10 GMT

> This is different from my last question. I need a data type that can store
> a bunch of values for a map made up of x, y coordinates. However, I don't
[quoted text clipped - 13 lines]
> have it return the value for that point. e.g. getVal(100, 123) ...
> returns -2.

If all you're doing is inserting and retrieving data points, I would go with
a simple HashMap using a key that's an object like

class Point{
int x, int y
}

and be sure to override equals and hashCode because that's what will make it
work. Think of it as a sparse array. If you want to do any other operations,
such as finding nearest points, there are more exotic structures such as
quadtrees.

Matt Humphrey matth@ivizNOSPAM.com http://www.iviz.com/

Reply to this Message

Brian Bagnall - 20 Dec 2006 00:28 GMT

> If all you're doing is inserting and retrieving data points, I would go with
> a simple HashMap using a key that's an object like
[quoted text clipped - 5 lines]
> and be sure to override equals and hashCode because that's what will make it
> work.

I know how to override equals, but how would I come up with a hashCode value?

> Think of it as a sparse array. If you want to do any other operations, such
> as finding nearest points, there are more exotic structures such as
> quadtrees.

This sounds interesting. Does Java have an implementation of Quadtrees?

- Brian

Reply to this Message

Matt Humphrey - 20 Dec 2006 12:58 GMT

>> If all you're doing is inserting and retrieving data points, I would go
>> with a simple HashMap using a key that's an object like
[quoted text clipped - 8 lines]
> I know how to override equals, but how would I come up with a hashCode
> value?

Minimally, two objects that are equal must produce the same hash code,
although ideally you want objects that are not equal to produce different
hash codes. Because your (x, y) values are constrained to such a small
range 0..200 you can give each equivalent Point a distinct hash with:

public int hashCode () { return (x << 8) | y; }

This is a good starting place for the problem you've described and there
won't be any point in optimizing it further until after you do profiling.

> This sounds interesting. Does Java have an implementation of Quadtrees?

It's likely, but I don't know offhand. Google is your friend.

Matt Humphrey matth@ivizNOSPAM.com http://www.iviz.com

Reply to this Message

Lew - 20 Dec 2006 03:04 GMT

"Brian Bagnall" <bbagnall@mts.net> wrote:

>> This is different from my last question. I need a data type that can store
>> a bunch of values for a map made up of x, y coordinates. However, I don't
>> want to store a value for *every* point on the map. For example, most of
>> the map will be grey, but perhaps the point at x=23 and y=34 will be blue.
>> So I store a value 6 at 23, 34. And at maybe 100, 123 I store a value
>> of -2. etc...

> I would go with a simple HashMap using a key that's an object like
>
> class Point{
> int x, int y
> }

Oliver Wong wrote "Re: Tricky Data Type Needed":

> ... I'd probably use Map<Pair<Integer,Integer>,Byte> ...

or, in your "different" case, Map< Pair<Integer,Integer>, WhateverValueType >

- Lew

Reply to this Message

Efficient Data Type Needed

Free Magazines