Mapping items in 2-dimensional space into memory

Question

I've got number of items that are identified by its 2-dimensional coordinates (signed short range). Every item is class containing 64KB of data. There are about 500-1500 of items at any moment. Items are usually in groups of ~20 around a point. My question is how should I map them so that it would not take too much of memory. Items will be added/deleted slowly (1-10 per second) and will be fetched very often so fetching element from the list (pointer to bigger structure) should be as fast as possible.

What I came up with is that there would be some gridContainer class with lets say it would store rectangle of 64x64 pointers. I would have main grid container, which would store other gridContainer and this nested gridContainer would store actual items i want to map (this would allow 4096x4096 actual items). To access a particular item, for example [260, 130] I would divide it by 64 and take quotient to find parent gridContainer position and remainder to find nested gridContainer position. So for [270,145] i would have [4,2] and [14,17].

I was also thinking of using std::map but I don't know the internals of it and I don't know what performance should I expect from it.

Any suggestions on my method or is there any better way to do it?

Answer 1

You could use a std::map as already suggested, which is just a b tree container, or you could use a hash table, which has the potential to be faster. A quad tree is also an option, which would be far more involved than the previous two options, but would provide early out options.

A hash table with a minimal load has a good chance of being an O(1) lookup, but has a worst case of O(n), when n = items present. If you can keep the load below about 10%, then you'd have to have a really horrible hashing function to get worse than O(1). This obviously chews up a lot of extra memory, but it has the potential to be the fastest option. The comparison type for a hash table is quite involved. You have a hasher function which accepts input of the key type, in this case a pair of shorts, and returns an index. That index corresponds to a location on a semi-fixed array of objects. If there's already an object there, the collision has to be resolved, which can result in detrimental running times, so the sparser, the better.

A quad tree has a best case return time of O(1), but only for empty cells, whereas if there's a item present, it has a lookup time of O(log n) where n is the size of the desired field. Unless you have very few objects, this has the potential to eat up more memory than the hash table, but like stated above, you get a decent running time and a lookup that yields no results can terminate with relative speed. The comparison type for a Quad tree is usually just a cascading boolean check.

A std::map has a constant lookup time of O(log n), where n is the elements in the map. This is the most memory efficient option, but has a guaranteed run time for any lookup. The comparison type for a std::map is a cascading less-than operation, which in the case of an int ((short1<<16)|short2), is also quite fast.

There's a good overview of the containers you'll likely use. The one you ought to use depends on how loaded down you expect your table to be. With just a few objects (< 500), a std::map is probably your best bet. For 500 to about 5000, you should probably use a quad tree. Any more than that, you'll start using a ridiculous amount of memory for the tree, and should probably use a hash table instead.

Answer 2

A Quad Tree seems to be what you are looking for.

Answer 3

You can always use a std::map<std::pair<short, short>, *item>this would allow retrieving and adding in log(n) time, but for a more precise answer we have to know what operations you require to be fast