Is there a cleaner way to give dictionary-like access to a list?

Unity Engine
1

I have a chunk class and I want it to contain references(represented by a int identifier) to objects that are occupying certain coordinates in the chunk. Since many objects don’t have collisions, the same position may be occupied by multiple objects. The chunks have 2 dimensions (x,y). Here is what I was thinking to achieve this:

public class Chunk{

public List<int>[] objPresence;

}

This would make an array of lists( in which size = chunksizeX * chunksizeY) where the index would be the flattened x,y coordinates, and the list would contain all objects on that position. ( each int in the list would be my identifier of a given object )

So to find what objects are currently in a given position I would do:

listOfObjectsOnPosition = objPresence[ flattenIndex(x,y) ];

So far so good, but now if I want to check if one specific object is in a certain position I have to iterate through the list, and I would like to be able to have O(1) access on this.

So here is the alternative using dictionary:

public class Chunk{

public Dictionary<int,byte>[] objPresence;

}

and for access, to find a certain object:

objPresence[ flattenIndex(x,y) ].ContainsKey(objToSearch)

I can also iterate through the dictionary keys if I just want to get all objects in the position.

However in this method since I am using Dictionary<int,byte>, and the int key is the identifier for the object, the byte value on the dictionary is wasting memory since i dont need that value for anything.

Is there a way to implement what I have here without that wasted byte, or is there another, better way to do this altogether?

Thanks!

2

The whole “flattenIndex” thing is kind of confusing me, but I don’t think it’s related to what you’re asking about.

Are you looking for the functionality of HashSet maybe?

1 Like
3

exactly what I was looking for thanks!

the flattened(x,y) is just a formula in which I input x and y coordinates and outputs the index to the x,y position, instead of using a multidimensional array [x , y]

1 Like
4

Note that if your chunk is “sparse” in the sense that most coordinates have 0 objects at that coordinate, then it might be more efficient to replace the array with a dictionary. (That way you only need to allocate memory to the coordinates that actually contain something, instead of to every possible coordinate.)

2 Likes
5

Thanks, so this would be the best?

public Dictionary<int,HashSet<int>> objPresence;
1 Like
6

Well, whether it’s best depends on the details of what you’re doing with it, but yes, that’s the sort of thing I was describing.

1 Like
7

By the way, do you think it is worth object pooling a class like this?

public class Chunk{

    public Dictionary<int,HashSet<int>> objPresence;

}

it seems clean enough to do objPresence.Clear(), but it will still generate garbage from the hashsets unless I loop through the dictionary and .clear() each hashset? Would the performance gained by fully pooling and avoiding that garbage collection offset the need to do this:

foreach(KeyValuePair<int, hashset<int>> entry in objPresence)
{
    entry.Value.Clear()
}
8

Er…do you mean clearing the HashSets instead of clearing the Dictionary? Clearing HashSets when you’re about to throw them away is pointless. Clearing just the HashSets would be complicated, since the whole reason you’re using a Dictionary is that this is a sparse data structure and you only want HashSets for the specific coordinates you’re interested in, so unless the interesting coordinates are always the same ones then clearing the HashSets would be just the first step in an object pooling scheme, you’d have to do a lot more work than that.

1 Like
9

I see thanks, i guess in this case pooling is unpractical and maybe even not needed.

10

I think you may be confused about the terms “garbage” and “object pooling”.

Garbage is when you stop using an object and allow the garbage collector to delete it so it can reclaim the memory. Note that this is worse than if you never used the memory in the first place, but it’s better than if you keep hold of it even when you no longer need it; keeping it when you don’t need it is called a “memory leak”. Memory leaks mostly don’t happen in C# because it has an automatic garbage collector that works hard to figure out memory you don’t need anymore, but it doesn’t predict the future, it just checks whether you could still access something. So if you keep around variables that you don’t need then the garbage collector can’t reap them because it’s not sure if you still need them.

Assuming that you have no way to access those HashSets except through the Dictionary, then clearing the Dictionary will turn them into garbage automatically. If you can access them in some other way, but don’t intend to, then that would be a memory leak, which is worse. Clearing an object right before you turn the entire object into garbage isn’t going to help you.

Object pooling is when you keep a reference to the object and reuse it for new content. Suppose that you no longer need to keep track of anything happening at location #219, but you just now need to start keeping track of objects at location #372. The obvious thing to do would be something like:

objPresence[219] = null;
objPresence[372] = new HashSet<int>();

Object reuse would be if you instead did something like:

objPresence[219].Clear();
objPresence[372] = objPresence[219];
objPresence[219] = null;

Reusing the same, pre-existing HashSet for a new job now that it’s old job is done.

Naturally, the times when you stop needing one object at the exact moment that you need a new one somewhere else are rare, so usually if you want to reuse objects you take objects that you don’t currently need and put them into some sort of reserve area, called a pool, so that the next time you need a new object you can grab one out of the pool instead of creating a new one.

This is probably not worth doing in your case, because HashSets are pretty simple objects. But it’s not harder to do in your case than in a typical case. Might even be easier.

But “clearing objects right before you throw them away” isn’t a thing; that’s not how object pooling works.

2 Likes
11

Thanks for the info it was my mistake. I was thinking about clearing the dictionary to pool the class and keep it in memory to reuse later, and got caught up on the fact that the hashsets were not reusable in a practical way, Thanks!