-1
\$\begingroup\$

I'm working on a 2D game for Android using LibGDX in Java. In my game I got lots of enemies, bullets and other stuff. I hold a hash map, which every cell holds a reference to an array list of that kind of objects. For example:

HASH MAP->

Enemies = [enemy1,enemy2,enemy3]

Bullets = [bullet1,bullet2] etc...

In my render() loop I run with an iterator on the hash map and run through all the objects in every array list, calling each one's update() method.

I wonder, would it be faster holding a linked list to every kind of objects instead of array list and running through that linked list?

Thanks!

\$\endgroup\$
  • \$\begingroup\$ So you're asking whether LinkedList is faster than ArrayList, and your question has little to do with HashMap? \$\endgroup\$ – immibis Feb 2 '16 at 23:16
  • \$\begingroup\$ Well, hash map can also be replaced with a linked list while every link has a reference to a linked list so the question can be also related to that. But basically, yes. \$\endgroup\$ – Gad Wissberg Feb 2 '16 at 23:19
  • 3
    \$\begingroup\$ This sort of relates to premature optimization, the advice I would give is unless you're aware that your current solution isn't performing well enough it's not worth messing with. On top of that, more than likely you will not be able to noticeably improve your current solution. You have a fixed cost of iterating through the total number of enemies which almost certainly dominates your computation time compared to the HashMap iteration. \$\endgroup\$ – Alex Sherman Feb 2 '16 at 23:34
0
\$\begingroup\$

I wonder, would it be faster holding a linked list to every kind of objects instead of array list and running through that linked list?

If all you are doing is iteration, stick with the ArrayList. The difference in iteration performance for an ArrayList versus a linked list is small-to-nonexistent, and favors the ArrayList (because of contiguity and cache misses).

The reason to favor a linked list would be if you're need to insert and remove from the interior of the list often, and need items to maintain order (so you can't do the swap-and-pop tricks of sorting "dead" items to the back of a list). It doesn't sound like that's the case here, based on your presented problem description.


That said, the above is theoretical in nature; you should really profile your actual code to be sure. I suspect your bottleneck is not where you think it is, and even if it is, profiling the before-and-after scenario will let you know exactly how better or worse you've made things with changes.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.