How to optimize this algorithm

Question

I need help with making this bit of code faster:

UnitBase* Formation::operator[](ushort offset)
{
 UnitBase* unit = 0;
 if (offset < itsNumFightingUnits)
 {
  ushort j = 0;
  for (ushort i = 0; i < itsNumUnits; ++i)
  {
   if (unitSetup[i] == UNIT_ON_FRONT)
   {
    if (j == offset)
     unit = unitFormation[i];
    ++j;
   }
  }
 }
 else
  throw NotFound();
 return unit;
}

So, to give some background, I have this class Formation which contains an array of pointers to UnitBase objects, called UnitFormation. The UnitBase* array has an equally sized array of numbers that indicate the status of each corresponding UnitBase object, called UnitSetup.

I have overloaded the [] operator so as to return only pointers to those UnitBase objects that have a certain status, so if I ask for itsFormation[5], the function does not necessarily return UnitFormation[5], but the 5th element of UnitFormation that has the status UNIT_ON_FRONT.

I have tried using the code above, but according to my profiler, it is taking way too much time. Which makes sense, since the algorithm has to count all the elements before returning the requested pointer.

Do I need to rethink the whole problem completely, or can this be made somehow faster?

Thanks in advance.

Answer 1

One quick optimization would be to return the unit as soon as you find it, rather than continuing to iterate over all of the rest of the units, e.g.

if (j == offset)
 unit = unitFormation[i];

becomes

if (j == offset)
 return unitFormation[i];

Of course, this only helps in the case that the unit you're looking for is towards the front of the unitFormation sequence, but it's trivial to do and does help sometimes.

A more involved, but more effective way to make this faster would be, for each status, to build and maintain a linked list of units that have that status. You would do this in parallel to the main array of units, and the contents of the linked lists would be pointers into the main units array, so you are not duplicating the unit data. Then, to find a given offset within a status, you could just traverse to the offsetth node of the linked list, rather than iterating over each unit.

Making it a doubly-linked list and keeping a tail pointer would allow you to find elements with high offsets just as quickly as low offsets (by starting from the end and going backwards).

However, this would still be slow if there are a lot of units with the same status and you are looking for one whose offset is near the middle.