Делается полный перебор по 4-х мерному массиву — выполняется очень долго, а нужно быстрее

 // Начинаем перебор
 for(i1=0;i1<=2*CellsNum;i1++)
 {tx = i1;
  for(i2=0;i2<=2*CellsNum;i2++)
  {ty = i2;
   for(i3=-Vg;i3<=Vg;i3++)
    {x = tx + i3*kof;
     for(i4=-Vg;i4<=Vg;i4++)
      {y = ty + i4*kof;
       Q1[i1][i2][i3+Vg][i4+Vg].dh += cl[x][y].h;

       if (Q1[i1][i2][i3][i4].dh<MinH)
        { // Сохраняем лучший вариант
         MinH = Q1[i1][i2][i3+Vg][i4+Vg].dh;
         r.x = i1;
         r.y = i2;
         r1.x = i3+Vg;
         r1.y = i4+Vg;
        }
      } // for i4
    } //for i3
  } // for i2
 } //for i1

аналогичная прога на паскале работает намного быстрее, но исходников нет (((

дайте пару советов по оптимизации такого кода

Здравствуйте, Piero2, Вы писали:

P>Делается полный перебор по 4-х мерному массиву — выполняется очень долго, а нужно быстрее

P> // Начинаем перебор
P> for(i1=0;i1<=2*CellsNum;i1++)
P> {tx = i1;
P> for(i2=0;i2<=2*CellsNum;i2++)
P> {ty = i2;
P> for(i3=-Vg;i3<=Vg;i3++)
P> {x = tx + i3*kof;
P> for(i4=-Vg;i4<=Vg;i4++)
P> {y = ty + i4*kof;
P> Q1[i1][i2][i3+Vg][i4+Vg].dh += cl[x][y].h;

P> if (Q1[i1][i2][i3][i4].dh<MinH)
P> { // Сохраняем лучший вариант
P> MinH = Q1[i1][i2][i3+Vg][i4+Vg].dh;
P> r.x = i1;
P> r.y = i2;
P> r1.x = i3+Vg;
P> r1.y = i4+Vg;
P> }
P> } // for i4
P> } //for i3
P> } // for i2
P> } //for i1

P>аналогичная прога на паскале работает намного быстрее, но исходников нет (((

P>дайте пару советов по оптимизации такого кода

Первое что бросилось в глаза — перемножение в цикле 2*CellsNum. Вычисли это произведение до циклов.

Здравствуйте, Piero2, Вы писали:

P>Делается полный перебор по 4-х мерному массиву — выполняется очень долго, а нужно быстрее

P> // Начинаем перебор
P> for(i1=0;i1<=2*CellsNum;i1++)
P> {tx = i1;
P>  for(i2=0;i2<=2*CellsNum;i2++)
P>  {ty = i2;
P>   for(i3=-Vg;i3<=Vg;i3++)
P>    {x = tx + i3*kof;
P>     for(i4=-Vg;i4<=Vg;i4++)
P>      {y = ty + i4*kof;
P>       Q1[i1][i2][i3+Vg][i4+Vg].dh += cl[x][y].h;

P>       if (Q1[i1][i2][i3][i4].dh<MinH)
P>        { // Сохраняем лучший вариант
P>         MinH = Q1[i1][i2][i3+Vg][i4+Vg].dh;
P>         r.x = i1;
P>         r.y = i2;
P>         r1.x = i3+Vg;
P>         r1.y = i4+Vg;
P>        }
P>      } // for i4
P>    } //for i3
P>  } // for i2
P> } //for i1

P>аналогичная прога на паскале работает намного быстрее, но исходников нет (((

P>дайте пару советов по оптимизации такого кода
1. Заранее вычислить 2*CellsNum. Вряд ли сколь-либо поможет, но все же.
2. вычислить заранее массив значений i3*kof/i4*kof в диапазоне [-Vg, Vg] и во внутренних циклах использовать вычисленные значения из массива.
3. Зампомнить один раз ссылку на элемент массива и пользовться ей:

...
ElemType& ref = Q1[i1][i2][i3+Vg][i4+Vg].dh;
ref += cl[x][y].h;
...
if(ref < MinH)
{
   MinH = ref;
   ...
}

4. Доложить о результатах

Здравствуйте, Bell, Вы писали:

Да, и еще на всякий случай: используется ведь release-конфигурация?

Piero2 wrote:

> дайте пару советов по оптимизации такого кода
У тебя не четырёхмерный массив, а массив массивов массивов массивов. Это требуется алгоритмом или можно переделать?
А остальное — хз, компилятор должен такое оптимизировать. У тебя какой комплиятор? Включена ли оптимизация?

Здравствуйте, ., Вы писали:

.>У тебя не четырёхмерный массив, а массив массивов массивов массивов.

В С/С++ четырёхмерный массив как раз и является массивом массивов массивов массивов.

.> Это требуется алгоритмом или можно переделать?

А у тебя какие предложения?

Аноним wrote:

> В С/С++ четырёхмерный массив как раз и является массивом массивов
> массивов массивов.
Нет, в С++ встроенных многомерных массивов нет. [] в объявлении означает "превращение" типа в массива, так что запись
вида int[][] означает массив массивов, а не двухмерный массив.

> .> Это требуется алгоритмом или можно переделать?
>
> А у тебя какие предложения?
Ну как обычно —
int array[M*N*K*L]
И индексируешься как:
array[((m*N+n)*K+k)*L+l];
(вроде ничего не напутал в арифметике)

Здравствуйте, ., Вы писали:

>> В С/С++ четырёхмерный массив как раз и является массивом массивов
>> массивов массивов.
.>Нет, в С++ встроенных многомерных массивов нет. [] в объявлении означает "превращение" типа в массива, так что запись
.>вида int[][] означает массив массивов, а не двухмерный массив.

Молодец. Но фактически это двумерный массив.

>> А у тебя какие предложения?
.>Ну как обычно -
.>int array[M*N*K*L]

Обычно? Ты так делаешь обычно и называешь 4-мерным массивом? Вообще-то он одномерный...

.>И индексируешься как:
.>array[((m*N+n)*K+k)*L+l];

Думаешь ты в чем-то выгадал по сравнению с "массивом массивов"? Ты считаешь что твое индексирование эффективнее чем сделает компилятор?

спасибо всем кто откликнулся

упростил прогу до такого вида:
int *v;

for(i1=0;i1<=c;i1++)
{tx = i1 + CellsNumPlus;
for(i2=0;i2<=c;i2++)
{ty = i2 + CellsNumPlus;
for(i3=-Vg;i3<=Vg;i3++)
{fx = tx + ms[i3+Vg];// i3*kof;
i33 =i3+Vg;
for(i4=-Vg;i4<=Vg;i4++)
{fy = ty + ms[i4+Vg];// i4*kof
v = &Q3[i1][i2][i33][i4+Vg];
*v += cl[fx][fy];

if (*v<MinH)
{ //
MinH = *v;
r.x = i1;
r.y = i2;
r1.x = i3+Vg;
r1.y = i4+Vg;
}
} // for i4
} //for i3
} // for i2
} //for i1

помогло мало — почти не заметно (((

где включить оптимизацию?
что такое release-конфигурация?

компилятор у меня — borland я работаю на Builder 6.

включил оптимизацию — еще немного побыстрее

Аноним wrote:

> Думаешь ты в чем-то выгадал по сравнению с "массивом массивов"? Ты
> считаешь что твое индексирование эффективнее чем сделает компилятор?
Это алгоритмически другая конструкция. Иногда выгоднее, иногда нет. Я не знаю что именно требуется в данной задаче.
Массив массивов может быть таким:
[1,2,3]
[4,5]
[6,7,8,9]
т.е. по сути это массив указателей, каждый указатель указывает на массив значений.
Память выделяемая под массив массивов N*M*<размер значения>+N*<размер указателя>.
если же двухмерный массив (ака матрица), то он может быть только таким:
[1,2,3]
[4,5,6]
[7,8,9]
Реализовываться может с помомщью одномерного массива с вычислением индекса по паре значений.
Память выделяемая под двумерный массив N*M*<размер значения>.

Здравствуйте, Piero2, Вы писали:

P>включил оптимизацию — еще немного побыстрее
Поздравляю
Дальше нужно брать в руки профайлер.

ЗЫ
А ты уверен, что тормозит именно приведенный кусок кода?

да 100%

что такое профайлер?

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

Здравствуйте, Piero2, Вы писали:

P>да 100%

P>что такое профайлер?

Ну глянь здесь например.

Bell, спасибо ща почитаем, а на какой прирост скорости примерно можно расчитывать?

Здравствуйте, Piero2, Вы писали:

P>Bell, спасибо ща почитаем, а на какой прирост скорости примерно можно расчитывать?

Мне кажется, что на большой прирост расчитывать не стОит. Но посмотреть на диагностику профайлера никогда не помешает.
Кстати что в твоем случае значит "медленно"? Какой объем входных данных? Количество итераций? Насколько быстрее паскалевская программа? Ты уверен, что эта самая паскалевская программа идентична твоей сишной?
Да, и что представляет из себя Q1?

Здравствуйте, Piero2, Вы писали:

P>включил оптимизацию — еще немного побыстрее
Как кстати включил? Конфигурация точно release? Не debug?

Здравствуйте, Bell, Вы писали:

B>Здравствуйте, Piero2, Вы писали:

P>>Bell, спасибо ща почитаем, а на какой прирост скорости примерно можно расчитывать?

B>Мне кажется, что на большой прирост расчитывать не стОит. Но посмотреть на диагностику профайлера никогда не помешает.
B>Кстати что в твоем случае значит "медленно"? Какой объем входных данных? Количество итераций? Насколько быстрее паскалевская программа? Ты уверен, что эта самая паскалевская программа идентична твоей сишной?
B>Да, и что представляет из себя Q1?

в последней версии программы
int ****Q1

итераций:
c =40;
Vg = 5;

т.е. получается: 41^2*11^2 = 203 000 итераций


удалось добыть кусок паскаль программы:
for kVSm:=-Size_A to Size_A do
begin {111}
mVx:=trunc(Sm_time*kVSm+0.5);
for kVSb:=-Size_B to Size_B do
begin {112}
mVy:=trunc(Sb_time*kVSb+0.5);
for m:=-SizeDK0_5 to SizeDK0_5 do
begin {113}
m1:=m+mVx;
for n:=-SizeDK0_5 to SizeDK0_5 do
begin {114}
Q[m,n,kVSm,kVSb]:=Q[m,n,kVSm,kVSb]+Ext_DK[m1,n+mVy];
if Q[m,n,kVSm,kVSb]< Qmin then
begin {115}
Qmin:=Q[m,n,kVSm,kVSb];
Mmin:=m;
Nmin:=n;
Kmin1:=kVSm;
Kmin2:=kVSb;
end {115}
end; {114}
end; {113}
end; {112}
end; {111}

суть здесь та же, я не вижу чем моя прога хуже, но эта работает намноооого быстрее, моя прога подвисает на 30 секунд, а эта 2-3 секунды при тех же входных данных

Здравствуйте, Bell, Вы писали:

B>Здравствуйте, Piero2, Вы писали:

P>>включил оптимизацию — еще немного побыстрее
B>Как кстати включил? Конфигурация точно release? Не debug?

в опциях проекта, да release стоит

Здравствуйте, Piero2, Вы писали:

P>Здравствуйте, Bell, Вы писали:

B>>Здравствуйте, Piero2, Вы писали:

P>>>включил оптимизацию — еще немного побыстрее
B>>Как кстати включил? Конфигурация точно release? Не debug?

P>в опциях проекта, да release стоит

а в 2003 студии как ето зделать ?
там в линкере есть оптимизация и пункты:
1 References
2 Enable COMDAT folding
3 Optimize for Windows 98
4 Function order
ето то о чом вы пишете ?
и что там ставить ? что за что отвечает ?