c++ - 如何优化这个算法

我需要帮助使这段代码更快:

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;
}

因此，为了提供一些背景知识，我有一个Formation类，其中包含一个指向UnitBase对象的指针数组，称为UnitFormation。 UnitBase* 数组有一个相同大小的数字数组，用于指示每个相应 UnitBase 对象的状态，称为 UnitSetup 。

我重载了 [] 运算符，以便仅返回指向具有特定状态的那些 UnitBase 对象的指针，因此如果我要求 itsFormation[5] ，该函数不一定返回 UnitFormation[5] ，而是 UnitFormation 具有状态 UNIT_ON_FRONT 的第 5 个元素。

我曾尝试使用上面的代码，但根据我的分析器，它花费了太多时间。这是有道理的，因为算法必须在返回请求的指针之前计算所有元素。

我是否需要完全重新考虑整个问题，或者可以以某种方式使其更快？

提前致谢。

最佳答案

一种快速优化是在找到该单元后立即返回该单元，而不是继续迭代所有其余单元，例如

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

变成

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

当然，这仅在您要查找的单位位于 unitFormation 序列的前面的情况下才有帮助，但这样做很简单，有时确实有帮助。

一种更复杂但更有效的加快速度的方法是，对于每个状态，构建和维护具有该状态的单元的链接列表。您将与主单元数组并行执行此操作，并且链接列表的内容将是指向主单元数组的指针，因此您不会复制单元数据。然后，要在状态中找到给定的偏移量，您只需遍历链表的第 offset 节点，而不是遍历每个单元。

使它成为一个双向链表并保留一个尾指针将允许您像低偏移量一样快速地找到具有高偏移量的元素(通过从末尾开始向后移动)。

但是，如果有很多具有相同状态的单元并且您正在寻找偏移量接近中间的单元，这仍然会很慢。