Могу ли я оптимизировать код, в котором есть 3 цикла for и 4 if?

• С точки зрения языка вы можете улучшить производительность, зарезервировав 26 (или 27 в зависимости от того, какое число вы имеете в виду :)) элементов в векторе:

  std::vector<Pos> vect1; vect1.reserve(27);

  это сделает внутренний массив достаточно большим и позволит избежать перераспределения вектора.

• Будет ли возврат вектора или передача вектора по ссылке и запись в него более производительна, будет выяснено только путем выполнения тестов. Компиляторы могут оптимизировать копии возвращаемого значения.

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

Все ваши циклы for имеют вид:

for (d_ = somPos._ - resol; d_ <= somPos_.+resol; d_+= resol)

Это выполняется ровно 3 раза. Этот код, вероятно, станет быстрее, если вы замените эти три цикла for чем-нибудь для формы:

double dz = somePos.m_pPos[2] - resol; 
for(z = 0; z < 3; z++, dz += resol)

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

Обновлено: Также, если вы используете const или #define для своих значений MinPos / MaxPos, компилятор может ускорить работу с помощью бита маленький. Я не думаю, что он сможет понять, что значения действительно являются константами в том виде, в каком они у вас есть.

Сравнение равенства с числами с плавающей запятой очень рискованно и подвержено ошибкам.

Передача и возврат объектов по значению? В зависимости от ваших объектов это может замедлить работу.

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

Во-первых, избавьтесь от операторов if. В них нет нужды. Вы можете объединить их в условие цикла. Во-вторых, избегайте пересчета условия цикла на каждой итерации. Да, компилятор может оптимизировать его, но обычно он очень консервативен с оптимизацией с плавающей запятой (и он может обрабатывать значения fp, считанные из памяти, иначе, чем значения, считанные из регистра, что означает, что не могу исключает поиск вашего массива из условий цикла) , поэтому часто даже простые оптимизации лучше проводить вручную:

std::vector<Pos> Create26Neighbor(Pos somePos, double resol) 
{
    std::vector <Pos> vect1(27); // Initialize the vector with the correct size.
    Pos  m_MinPos(0.0,0.0,0.0);
    Pos  m_MaxPos(5.0,4.0,5.0);

    double minz = std::max(somePos.m_pPos[2] - resol, m_MinPos.m_pPos[2]);
    double maxz = std::min(somePos.m_pPos[2] + resol, m_MaxPos.m_pPos[2];
    int i = 0;
    for (double dz = min; dz <= max; dz+=resol)
    {
        double miny = std::max(somePos.m_pPos[1] - resol, m_MinPos.m_pPos[1]);
        double maxy = std::min(somePos.m_pPos[1] + resol, m_MaxPos.m_pPos[1];
        for (double dy = miny; dy <= maxy; dy+=resol)
        {
            double minx = std::max(somePos.m_pPos[0] - resol, m_MinPos.m_pPos[0]);
            double maxx = std::min(somePos.m_pPos[0] + resol, m_MaxPos.m_pPos[0];

            for (double dx = minx; dx <= maxx; dx+=resol)
            {
                ++i;
                // If we're not at the center, just use 'i' as index. Otherwise use i+1
                int idx = (dx != somePos.m_pPos[0] || dy != somePos.m_pPos[1] || dz != somePos.m_pPos[2]) ? i : i+1;
                vec1[idx] = Pos(dx, dy, dz); // Construct Pos on the spot, *might* save you a copy, compared to initilizing it, storing it as a local variable, and then copying it into the vector.
              }
        }
    }
    return vect1;
}

Последний пункт, на который я хотел бы обратить внимание, - это внутренний if-оператор. Ответвления в тесной петле могут быть более дорогостоящими, чем вы могли ожидать. Я могу придумать несколько способов избавиться от этого:

• Как я набросал в коде, оператор?: Можно уговорить вычислить другой индекс вектора для центрального значения (так, чтобы он записывался в следующий элемент вектора, и поэтому на следующей итерации снова перезаписывается). Это устранит ветвь, но может быть или не быть в целом быстрее.
• Разделите циклы так, чтобы у вас были отдельные циклы до и после значения «resol». Это становится немного неудобным с большим количеством меньших циклов и может быть менее эффективным в целом. Но это устранило бы внутренний if-оператор, поэтому он также может быть быстрее.
• Разрешите добавить центральную точку к вектору и либо проигнорируйте ее впоследствии, либо удалите ее после циклов (это будет довольно дорогостоящая операция и может окупиться, а может и не окупиться. Это может быть дешевле, если вы используете двухстороннюю очередь вместо вектора.

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

Наконец, многое зависит от того, как определяется Pos.

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

В зависимости от того, насколько далеко вы готовы зайти, вы можете объединить все в один цикл (работающий с целыми числами) и просто вычислять координаты Pos на лету на каждой итерации.

Вы, вероятно, не найдете много способов упростить подобное кубическое уравнение, не добавив «умов», таких как фильтрация домена.

На самом деле, моя настоящая причина публикации здесь заключается в том, что код откровенно чудовищный, то есть: eugh. фу. У меня есть личная и недавно появившаяся ненависть к чрезмерно вложенному коду, и я постараюсь экспортировать некоторые из этих внутренних циклов в отдельную функцию, НЕСМОТРЯ - дополнительные теоретические накладные расходы, которые он добавит (профилируйте это, небольшие функции обычно в любом случае будут встроены)

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

Кроме того, если вы можете гарантировать, что количество координат будет фиксированным относительно начальной точки, вы можете извлечь выгоду, жестко закодировав структуру, то есть сделав это вручную, то есть:

function generate26( x,y,z ){ 
   return [ 
   # Top 
     # Left
      [x-1,y+1,z-1], 
      [x-1,y+1,z],
      [x-1,y+1,z+1]
   ];
}

Или создайте макрос, или 2, чтобы сделать это за вас.

По крайней мере, в этом случае вы полностью полагаетесь на способность компилятора оптимизировать структуру в памяти, без циклов или чего-то еще. (Профилируйте это, чтобы быть уверенным)

Is there a way to implement this recursively in a way that will make it faster?

Нет. На самом деле, нет.

Рекурсия означает вызовы функций, обычно в большом количестве. Вызов функций означает манипуляции со стеком и (потенциально) изменения контекста, которые являются относительно медленными операциями.

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

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

Если вы действительно хотите оптимизировать эту функцию до максимума, наиболее оптимальной реализацией будет одиночный переключатель и развернутые циклы.

Для каждого из трех измерений есть только пять вариантов:

case 1:  {somePos[i] - resol};  // 1 value only
case 2:  {somePos[i] - resol, somePos[i]}   // 2 values
case 3:  {somePos[i] - resol, somePos[i], somePos[i] + resol}  // all 3
case 4:                      {somePos[i], somePos[i] + resol}  // 2 values again
case 5:                                  {somePos[i] + resol}  // 1 value only

Также существует «случай 0», когда никто значений находится в диапазоне. Но если это верно для любого из измерений, вы вообще не добавляете никаких значений.

Объединение 5 возможностей для каждого из трех измерений дает вам 125 возможных вариантов для реализации. Учитывая, какой из 125 случаев у вас есть, вы можете просто развернуть циклы и if в последовательность до 26 вызовов push_back ().

Что-то вроде этого:

enum eCase {
CASE_NONE = 0,
CASE_LOW1 = 1,
CASE_LOW2 = 2,
CASE_ALL3 = 3,
CASE_HIGH2 = 4,
CASE_HIGH1 = 5,
};

eCase Xcase = /* a function of somePos[0], m_MinPos[0], m_MaxPos[0], and resol */
eCase Ycase = ...
eCase Zcase = ...

#define MUNGE(_x,_y,_z) (((((_x)*6)+(_y))*6)+(_z))
switch (MUNGE(Xcase, Ycase, Zcase) {

default:
    break;  // all CASE_NONE's do nothing
case MUNGE (CASE_ALL3, CASE_ALL3, CASE_ALL3):
    vect1.push_back( pos (somePos.m_pPos[0] - resol, somePos.m_pPos[1] - resol, somePos.m_pPos[2] - resol));
    vect1.push_back( pos (somePos.m_pPos[0] - resol, somePos.m_pPos[1] - resol, somePos.m_pPos[2]        ));
    vect1.push_back( pos (somePos.m_pPos[0] - resol, somePos.m_pPos[1] - resol, somePos.m_pPos[2] + resol));
    vect1.push_back( pos (somePos.m_pPos[0] - resol, somePos.m_pPos[1]        , somePos.m_pPos[2] - resol));
    vect1.push_back( pos (somePos.m_pPos[0] - resol, somePos.m_pPos[1]        , somePos.m_pPos[2]        ));
    vect1.push_back( pos (somePos.m_pPos[0] - resol, somePos.m_pPos[1]        , somePos.m_pPos[2] + resol));
    vect1.push_back( pos (somePos.m_pPos[0] - resol, somePos.m_pPos[1] + resol, somePos.m_pPos[2] - resol));
    vect1.push_back( pos (somePos.m_pPos[0] - resol, somePos.m_pPos[1] + resol, somePos.m_pPos[2]        ));
    vect1.push_back( pos (somePos.m_pPos[0] - resol, somePos.m_pPos[1] + resol, somePos.m_pPos[2] + resol));

    vect1.push_back( pos (somePos.m_pPos[0]        , somePos.m_pPos[1] - resol, somePos.m_pPos[2] - resol));
    vect1.push_back( pos (somePos.m_pPos[0]        , somePos.m_pPos[1] - resol, somePos.m_pPos[2]        ));
    vect1.push_back( pos (somePos.m_pPos[0]        , somePos.m_pPos[1] - resol, somePos.m_pPos[2] + resol));
    vect1.push_back( pos (somePos.m_pPos[0]        , somePos.m_pPos[1]        , somePos.m_pPos[2] - resol));
    vect1.push_back( pos (somePos.m_pPos[0]        , somePos.m_pPos[1]        , somePos.m_pPos[2] + resol));
    vect1.push_back( pos (somePos.m_pPos[0]        , somePos.m_pPos[1] + resol, somePos.m_pPos[2] - resol));
    vect1.push_back( pos (somePos.m_pPos[0]        , somePos.m_pPos[1] + resol, somePos.m_pPos[2]        ));
    vect1.push_back( pos (somePos.m_pPos[0]        , somePos.m_pPos[1] + resol, somePos.m_pPos[2] + resol));


vect1.push_back( pos (somePos.m_pPos[0] + resol, somePos.m_pPos[1] - resol, somePos.m_pPos[2] - resol));
vect1.push_back( pos (somePos.m_pPos[0] + resol, somePos.m_pPos[1] - resol, somePos.m_pPos[2]        ));
vect1.push_back( pos (somePos.m_pPos[0] + resol, somePos.m_pPos[1] - resol, somePos.m_pPos[2] + resol));
vect1.push_back( pos (somePos.m_pPos[0] + resol, somePos.m_pPos[1]        , somePos.m_pPos[2] - resol));
vect1.push_back( pos (somePos.m_pPos[0] + resol, somePos.m_pPos[1]        , somePos.m_pPos[2]        ));
vect1.push_back( pos (somePos.m_pPos[0] + resol, somePos.m_pPos[1]        , somePos.m_pPos[2] + resol));
vect1.push_back( pos (somePos.m_pPos[0] + resol, somePos.m_pPos[1] + resol, somePos.m_pPos[2] - resol));
vect1.push_back( pos (somePos.m_pPos[0] + resol, somePos.m_pPos[1] + resol, somePos.m_pPos[2]        ));
vect1.push_back( pos (somePos.m_pPos[0] + resol, somePos.m_pPos[1] + resol, somePos.m_pPos[2] + resol));
break;

... осталось всего 124 дела!

НЕ - повторять НЕ на самом деле пишет весь этот код вручную !!! Ни один человек не смог бы сделать это, не запрограммировав труднодоступную ошибку. Напишите другую программу для написания исходного кода. :-)

std::vector<Pos> Create26Neighbor(Pos somePos, double resol) 
{
    std::vector<Pos> vect1(26);
    Pos  m_MinPos(0.0,0.0,0.0);
    Pos  m_MaxPos(5.0,4.0,5.0);

    double z = somePos.m_pPos[2] - resol;

    for(int dz = -1; dz <= 1; ++dz) {
        z += resol;
        if (z <= m_MinPos.m_pPos[2] || z >= m_MaxPos.m_pPos[2])
            continue;

        double y = somePos.m_pPos[1] - resol;

        for(int dy = -1; dy <= 1; ++dy) {
            y += resol;
            if (y <= m_MinPos.m_pPos[1] || y >= m_MaxPos.m_pPos[1])
                continue;

            double x = somePos.m_pPos[0] - resol;

            for(int dx = -1; dx <= 1; ++dx) {
                x += resol;

                if (dx == 0 && dy == 0 && dz == 0)
                    continue;

                if (x <= m_MinPos.m_pPos[0] || x >= m_MaxPos.m_pPos[0])
                    continue;

                vect1.push_back(Pos(x, y, z));
            }
        }
    }

    return vect1;
}

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

Я не пытался в этом разобраться, но, возможно, вы сможете делать некоторые изящные вещи с помощью SSE2 / Altivec / других векторных инструкций для одновременного выполнения нескольких сравнений.