Как оптимизировать этот алгоритм

Question

Мне нужна помощь, чтобы сделать этот бит кода быстрее:

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], но 5-й элемент UnitFormation со статусом UNIT_ON_FRONT.

Я пытался использовать приведенный выше код, но, по словам моего профилировщика, это занимает слишком много времени. Это имеет смысл, поскольку алгоритм должен подсчитать все элементы, прежде чем возвращать запрошенный указатель.

Нужно ли полностью переосмыслить всю проблему или это можно сделать как-то быстрее?

Заранее спасибо.

Answer 1

Одна быстрая оптимизация состояла бы в том, чтобы вернуть юнит, как только вы его найдете, вместо того, чтобы продолжать перебирать все остальные юниты, например,

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

становится

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

Конечно, это помогает только в том случае, если искомый юнит находится в начале последовательности формирования юнитов, но это тривиально и иногда помогает.

Более сложный, но более эффективный способ сделать это быстрее - для каждого статуса создать и поддерживать связанный список юнитов, имеющих этот статус. Вы будете делать это параллельно с основным массивом модулей, а содержимое связанных списков будет указателями на массив основных модулей, поэтому вы не будете дублировать данные о единицах. Затем, чтобы найти заданное смещение в статусе, вы можете просто перейти к offset -ому узлу связанного списка, а не выполнять итерации по каждой единице.

Создание этого двусвязного списка и сохранение указателя хвоста позволит вам находить элементы с высоким смещением так же быстро, как с низким смещением (начиная с конца и возвращаясь назад).

Однако, это все равно будет медленным, если есть много юнитов с одинаковым статусом, и вы ищете тот, чье смещение близко к середине.

Answer 2

А как насчет редизайна вашего кода, чтобы сохранить таблицу «единиц на фронте», что бы это ни значило, звучит интересно :-).Если эта часть действительно часто запрашивается и не часто изменяется, то вы сэкономите немного времени.Вместо проверки всего или частей полного списка единиц, вы получите результат мгновенно.

PS: int должен использовать наиболее естественный тип для вашего процессора, поэтому использование ushorts не обязательно делать вашу программу быстрее .

Answer 3

В дополнение к другим предложениям, которые вы сделали, вы можете посмотреть, не выполняется ли какой-либо из этих вызовов этой функции без необходимости, и устранить эти точки вызова.Например, если вы видите, что вы вызываете это несколько раз, когда нет никаких шансов, что результат изменился.Самый быстрый код - это тот, который никогда не запускается.

Answer 4

Я полностью переработал решение, используя два вектора, один для юнитов спереди и один для других юнитов, и изменил все алгоритмы таким образом, чтобы юнит с измененным статусом немедленно перемещался из одного вектора в другой.Таким образом, я исключил подсчет в операторе [], который был основным узким местом.

Перед использованием профилировщика я получал время вычислений от 5500 до 7000 мс.Посмотрев здесь ответы, 1) я изменил переменные цикла с ushort на int или uint, что уменьшило продолжительность на ~ 10%, 2) я сделал еще одну модификацию вторичного алгоритма, чтобы уменьшить продолжительность еще на 30%3) Я реализовал два вектора, как описано выше.Это помогло сократить время вычислений с ~ 3300 мс до ~ 700 мс, то есть еще на 40%!

В целом это сокращение на 85 - 90%!Спасибо SO и профилировщику.

Далее я собираюсь реализовать шаблон-посредник и вызывать функцию обновления только при необходимости, возможно, вытягивая еще несколько мс.:)

Новый код, который соответствует старому фрагменту (функциональность теперь совершенно другая):

UnitBase* Formation::operator[](ushort offset)
{
    if (offset < numFightingUnits)
        return unitFormation[offset]->getUnit();
    else
        return NULL;
}

Намного короче и ближе к делу.Конечно, было много других тяжелых модификаций, наиболее важным из которых было то, что unitFormation теперь std::vector<UnitFormationElement*>, а не просто UnitBase**.UnitFormationElement* содержит UnitBase* вместе с некоторыми другими важными данными, которые раньше были в классе Formation.

Answer 5

Одной из проблем может быть то, что эта функция может вызываться слишком часто. Предполагая, что доля UNIT_ON_FRONT постоянна, сложность линейна. Однако, если вы вызываете оператор из цикла, эта сложность возрастает до O (N ^ 2).

Если вместо этого вы вернули что-то вроде boost::filter_iterator, вы могли бы повысить эффективность тех алгоритмов, которым необходимо перебирать UNIT_ON_FRONT.

Answer 6

Как часто будет меняться статус юнита?Возможно, вам следует сохранить список единиц, которые имеют надлежащий статус, и обновлять этот список только при изменении статуса.

Если необходимо минимизировать стоимость изменений статуса, вы можете сохранить массив, в котором указано, сколько изпервые 256 блоков имеют определенный статус, сколько из следующих 256 блоков и т. д. Можно сканировать массив в 256 раз быстрее, чем можно сканировать через блоки, пока один из них не окажется в пределах 256 слотов от N-го «хорошего» блока.Изменение статуса объекта потребует увеличения или уменьшения только одного слота массива.

Можно использовать другие подходы, чтобы сбалансировать стоимость изменения статуса объекта с затратами на поиск единиц с учетом различных моделей использования.

Answer 7

Можно ли отсортировать (или вставить отсортированные) ваши данные по статусу UNIT_ON_FRONT?Это сделало бы функцию тривиальной.

Answer 8

Вы перехитриваете себя (что каждый иногда делает). Вы сделали простую проблему O (N ^ 2). Просто подумайте о том, что вам нужно сделать, прежде чем перегружать операторов.

Добавлено в ответ на комментарий:

Попробуйте вернуться к более простому языку, например C или подмножеству C в C ++. Забудьте об абстракциях, классах коллекций и обо всем этом. Посмотрите, что нужно делать вашей программе, и подумайте о своем алгоритме. Затем, если вы можете упростить это, используя контейнерные классы и перегрузку, не заставляя это делать больше работы, тогда сделайте это. Большинство проблем с производительностью вызваны простыми проблемами и усложняют их, пытаясь использовать все причудливые идеи.

Например, вы берете оператор [], который обычно считается O (1), и делаете его O (N). Тогда я предполагаю, что вы используете его в некотором цикле O (N), поэтому вы получите O (N ^ 2). Что вы действительно хотите сделать, так это перебрать элементы массива, которые удовлетворяют определенному условию. Вы могли бы просто сделать это. Если их очень мало, и вы делаете это с очень высокой частотой, вы можете составить отдельный список из них. Но сохраняйте структуру данных простая , простая , простая . Лучше "тратить" циклы, и оптимизировать, только если это действительно нужно.

Answer 9

Для этого последнего кусочка сока, и если исключение выдается регулярно, возможно, стоит перейти к возвращению кода ошибки.Это более уродливый код, но отсутствие скачков в стеке может сильно помочь.В разработке игр обычно отключают исключения и RTTI.

Answer 10

Это не должно иметь большого влияния, но вы можете проверить сборку, чтобы увидеть, загружаются ли itsNumFightingUnits и itsNumUnits на каждой итерации цикла или они помещаются в регистры. Если они загружаются каждый раз, попробуйте добавить временные ссылки в начале функции.