Рубрики

Головоломка с вложенным циклом

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

/* ПЕРВЫЙ */

for(i=0;i<10;i++)

  for(j=0;j<100;j++)

    //сделай что-нибудь

/ * ВТОРОЙ * /

for(i=0;i<100;i++)

  for(j=0;j<10;j++)

    //сделай что-нибудь

Оба сегмента кода обеспечивают одинаковую функциональность, и код внутри двух циклов for будет выполняться одинаковое количество раз в обоих сегментах кода.
Если мы посмотрим поближе, то увидим, что SECOND выполняет больше операций, чем FIRST. Он выполняет все три части (назначение, сравнение и приращение) цикла for больше раз, чем соответствующие части FIRST:

  1. SECOND выполняет операции присваивания (j = 0 или i = 0) 101 раз, тогда как FIRST выполняет только 11 раз.
  2. ВТОРАЯ делает 101 + 1100 сравнений (i <100 или j <10), в то время как FIRST делает 11 + 1010 сравнений (i <10 или j <100).
  3. SECOND выполняет 1100 операций приращения (i ++ или j ++), а FIRST выполняет операцию 1010 приращения.

Ниже код C ++ подсчитывает количество операций приращения, выполненных в FIRST и SECOND, и печатает счетчики.

// программа для подсчета количества приращений
// операции в ПЕРВОМ и ВТОРОМ
#include<iostream>

  

using namespace std;

  

int main()

{

  int c1 = 0, c2 = 0;

     

  /* ПЕРВЫЙ */

  for(int i=0;i<10;i++,c1++)

    for(int j=0;j<100;j++, c1++);

      //сделай что-нибудь

  

     

  / * ВТОРОЙ * /

  for(int i=0; i<100; i++, c2++)

      for(int j=0; j<10; j++, c2++);

        //сделай что-нибудь

  

  cout << " Count in FIRST = " <<c1 << endl;

  cout << " Count in SECOND  = " <<c2 << endl;

  

  getchar();

  return 0;

}

Выход:

Count in FIRST = 1010
 Count in SECOND  = 1100

Ниже код C ++ подсчитывает количество операций сравнения, выполненных FIRST и SECOND

// программа для подсчета количества сравнений
// операции выполняются FIRST и SECOND * /
#include<iostream>

  

using namespace std;

  

int main()

{

   int c1 = 0, c2 = 0;

      

   /* ПЕРВЫЙ */

   for(int i=0; ++c1&&i<10; i++)

      for(int j=0; ++c1&&j<100;j++);

     //сделай что-нибудь

  

   / * ВТОРОЙ * /

   for(int i=0; ++c2&&i<100; i++)

      for(int j=0; ++c2&&j<10; j++);

      //сделай что-нибудь

  

   cout << " Count fot FIRST  " <<c1 << endl;

   cout << " Count fot SECOND  " <<c2 << endl;

   getchar();

   return 0;

}

Выход:

Count fot FIRST  1021
 Count fot SECOND  1201

Спасибо Dheeraj за предложенное решение.

Пожалуйста, пишите комментарии, если вы обнаружите, что какие-либо ответы / коды неверны, или вы хотите поделиться дополнительной информацией по темам, обсужденным выше.

Рекомендуемые посты:

Головоломка с вложенным циклом

0.00 (0%) 0 votes