LibGDX Using a Map with Duplicate keys vs using instanceof

Game Mechanics
#1

I’m creating an Array to hold a number of objects which all implement a given interface. Much of the time, it won’t matter what the subtype of the Object is, but, occasionally it will and I want to add some methods to get those subtypes for when required eg getA(), getB() etc.

I’m thinking that indexing them by a number for each subtype would be the quickest way to do this, although it would require a collection class that allows for duplicate keys:


private Array<SuperInterface> objects;

public Array<A> getA() {
    return objects.get(0); //0 being the index number for objects of type A
}

the alternative is simply to iterate through and create a new Array of that type:


private Array<SuperInterface> objects;

public Array<A> getA() {
    Array<A> a = new Array<A>();
    for (SuperInterface super : objects) {
        if (super instanceof A) {
            a.add(super);
        }
    }
    return a;

This, however, seems to me to be the least efficient approach.

So, my questions are:

  1. Do you agree with my assessment regarding efficiency? If not, what would you suggest?

  2. Are you aware of a good Map implementation that allows duplicate keys?

I’m aware that Google’s Guava includes a MultiMap implementation, but it seems overkill to include a library simply to use one class.

Hope that all makes sense!

#2

What is the Array class? Do you mean ArrayList here?

What exactly do you mean be efficiency? How many objects will this data structure contain in real life? What are your memory constraints? “Efficiency” is not just a single number. It’s a bunch of tradeoffs.

Can’t you just use a Map of Lists?

Or just use a different Map for each subtype. Don’t try to come up with a “clever” solution if something simple will work.

#3

Thanks for the reply.

Apologies - I’m using the Array class from libGDX. I should 've mentioned that.

I could possibly use a map with Integer keys and Array values - I just assume that an existing implementation of a Multimap would already be somewhat optimised, but it’s looking like it would also require importing a library just for one class - which may offset the advantage.

There is at least one context (rendering) where it’ll be easier if I can have everything in one collection, so it seems better to me to have a collection of everything where individual collections are easily accessible - hence the multimap idea.

#4

Why not just use a good old-fashioned array then?

Optimized for what? Have you tried implementing any of the above solutions and run into trouble? Or are you just assuming you’re going to have a problem? Premature optimization is the root of all evil, and all that.

What advantage is offset by using a library? How does using a libary offset that?

Honestly you seem to be complicating things a little too much, worrying about “efficiency” without actually defining what that means in your context.

Why is it better for rendering if everything is in one collection?

#5

That’s not what I meant. As I said in my original post, I was planning on using an int as an index for the types and would, therefore, be using the index numbers more than once - which isn’t how an array works.

I think there’s a difference between premature optimisation and trying to build software properly and thinking about design as you build. For example, it makes sense to me to use the libGDX Array class as it’s been optimised for use in a render loop - why would you not use that just because you don’t want to prematurely optimise. I agree that is to be avoided, but avoiding performance efficiency for the sake of it is obviously counter productive.

Honestly - why is considering a multimap over-complicating things? It’s a simple enough concept and, I must admit, I was surprised when I looked at the docs and discovered that there isn’t already an implementation in either java or libGDX. I’m really not trying to over complicate and I don’t think that is what I’m doing - I’m just trying to think about design as I build instead of writing poor code and having to refactor or simply not be able to maintain my own code!

Just because it makes more sense for me to loop through one collection rather than multiple collections. All the objects will need rendering regardless of subtype.

#6

[quote=“phunni,post:5,topic:58839”]
If you’re going to have a small number of sequential indexes, then that’s what an array is designed for. You could use a 2D array, or an array of Lists.

I’m not telling you to avoid efficiency. I’m suggesting that you need to define exactly what you’re optimizing for before you can talk about efficiency.

I’m not saying that a multimap is overly complicated, and in fact I’ve given you a few suggestions on how to implement one. I’m suggesting that worrying about the “efficiency” or “overhead” of a library is missing the point a bit, because honestly there won’t be a noticeable difference either way. Go with whatever makes the most sense to you. Stop worrying about “efficiency” before you actually have any problems.

Like I said, you should go with whatever fits into your brain. But if you want to avoid the kinds of checks you’re talking about, a common approach is to split it up into multiple Lists. Note that you could still have your mega-list if you really needed it.

#7

Thanks for the replies - and interesting discussion :slight_smile:

For now, I’ve gone with a libGDX ArrayMap<Integer, Array> - with the Array also being libGDX. THis means I can have everything in the one place for easy access. I shall refactor if (and only if :stuck_out_tongue: ) I find it less than performant!