Arduino.ru

По мотивам Конкурса. В теме поднимал вопрос (#154,#252) по различиям во времени выполнения программ, созданных при помощи разных версий ИДЕ, но откликов не было. Поэтому решил создать новую тему.

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

      for (uint8_t i = 0; i < minQ - qOn; i++)                     //сделали их "on"
        spanners[currArr[i]].included = on;

и

      for (uint8_t i = 0; i < minQ - qOn; i++)                     //сбросили ключи в "off"
       spanners[currArr[i]].included = off;

каждый из которых выполнялся 5113 раз (i=6, потом меняется i=7 ) для исходного набора. Я убрал их, ожидая, что время сократится. Программа перестала выполнять более 10 тыс. циклов из 6 - 7 итераций - но время выполнения не уменьшилось, как я ожидал, а УВЕЛИЧИЛОСЬ !!??

Стоимость набора: 6367 руб. 66 коп.
Время расчёта: 198 миллисекунд

с "лишними" циклами

Стоимость набора: 6367 руб. 66 коп.
Время расчёта: 202 миллисекунд

без них.

Использовалась "чистая", без доустановки чего-либо ИДЕ версии 1.8.13, ситема Win 7x64.

Полная версия программы

//
//  Тип данных для хранения ключа
//
struct Spanner : public Printable {
  uint32_t price;// цена в копейках
  uint8_t size1;  // размер 1
  uint8_t size2;  // размер 2
  uint8_t included; // если 1, то включается в результирующий набор,0 - возможно будет включен,10 - исключен из перебора

  //ТУТ НЕ ТАК,КАК В ВАС! included МОЖЕТ ПРИНИМАТЬ: если 1 (оn), то включается в результирующий набор,0 (off) - возможно будет включен,

  Spanner(const uint8_t s1, const uint8_t s2, const uint32_t p, const uint8_t ini = 0)
    :  price(p), size1(s1), size2(s2), included(ini) {}

  size_t printTo(Print & p) const {
    size_t res = p.print(size1);
    res += p.print('-');
    res += p.print(size2);
    res += p.print(": ");
    res += printPrice(p, price);
    return res;
  }

  static size_t printPrice(Print & p, const uint32_t priceCop) {
    size_t res = p.print(priceCop / 100);
    res += p.print(" руб. ");
    res += p.print(priceCop % 100);
    res += p.print(" коп.");
    return res;
  }
};



//
//  Массив всех ключей
//
static Spanner spanners[] = {
  
    {6, 8 , 38208},
    {8, 9 , 41520},
    {8, 10, 43054},
    {9, 11, 49597},
    {10, 12, 51455},
    {12, 13, 56544},
    {12, 14, 57675},
    {13, 15, 62845},
    {14, 15, 61714},
    {14, 17, 70276},
    {16, 17, 76496},
    {16, 18, 81989},
    {17, 19, 82312},
    {18, 19, 82877},
    {19, 22, 110826},
    {22, 24, 145560},
    {24, 27, 171570},
    //{9, 27, 71570}

};
static constexpr uint8_t totalSpanners = sizeof(spanners) / sizeof(spanners[0]);
const uint8_t on = 1, off = 0, excluded = 10;// если 1, то включается в результирующий набор,0 - возможно будет включен,10 - исключен из перебора


//
//  Эта функция вычисляет оптимальный набор ключей
//  и устанваливает поле included в on для ключей,
//  которые попадают в решение, и off или excluded для ключей,
//  которые не попадают в решение.
//
void doCalculations(void) {
  spanSort(spanners);              //отсортировали
  uint8_t quantityOff;            //ввели переменную кол-ва ключей, которые могут быть включены "off" в набор
  uint8_t quantityOn;            //ввели переменную кол-ва ключей, которые  включены "On" в набор
  uint8_t quantitySize = totalSize();//кол-во уникальных размеров и заодно удалили (excluded) дубли
  uint8_t minQuantSpann;            //ввели переменную миним. кол-во ключей, из которых может состоять набор
  if (quantitySize % 2 == 0)
    minQuantSpann = quantitySize / 2;
  else minQuantSpann = quantitySize / 2 + 1; //Вычислили мин. возможное кол-во ключей
  quantityOn = unique();                        //включили уникальные 6*8; 9*11; 24*27.
  exclud();                        //Тут исключать 8*9
  uint8_t quantitySizeOn =  onSize(quantityOn); //ввели переменную кол-ва размеров в "On" - ключах
  uint8_t arrBruteForce[quantitySize - quantitySizeOn] = {};
  arrey__B_F(quantityOff, quantityOn, arrBruteForce);
  //for (int k = 0; k < quantitySize - quantitySizeOn; k++){Serial.print(arrBruteForce[k]);Serial.print(',');}
  quantityOff = offSpanners();     //
  if (quantityOff == 0)return;
  sortOff(spanners); //Сортировка невклученных офф вперед
  //перебор вариантов.Почти все, что выше исключительно для умеьшения возм. сочетаний и времени.
  bruteForce(minQuantSpann, quantityOff, quantityOn, quantitySize,arrBruteForce, quantitySize - quantitySizeOn);
}

//
//  Функция печатает результирующий
//  набор ключей и его стоимость
//
void printResults(void) {
  Serial.println("Ключи");
  uint32_t total = 0;
  for (uint8_t i = 0; i < totalSpanners; i++) {
    if (spanners[i].included == on) {
      Serial.print(i + 1);
      Serial.print(". ");
      Serial.println(spanners[i]);
      total += spanners[i].price;
    }
  }
  Serial.print("Стоимость набора: ");
  Spanner::printPrice(Serial, total);
  Serial.println();
}
//--------------------------------------------------



//
// Функция пeребора вариантов сочетаний ключей
//
void  bruteForce(uint8_t minQ, uint8_t qOff, uint8_t qOn, uint8_t qSize,uint8_t *arr_B_F, uint8_t sizeA_B_F)
{
  uint8_t tempArr[qOff];
  uint32_t tempTotal = 4294967295;
  bool complectYes = false;

  for ( minQ; minQ <= qOff + qOn; minQ++)
  { //Serial.println(minQ);
    bool flagComplect = false;
    uint8_t *currArr;
    currArr = new uint8_t[minQ - qOn];


    for (uint8_t i = 0; i < minQ - qOn; i++)                     //первое сочетание ключей
    {
      currArr[i] = i ;
    }
    for (uint8_t i = 0; i < minQ - qOn; i++)                     //сделали их "on"
      spanners[currArr[i]].included = on;

    if (totalSizeOn1(arr_B_F, sizeA_B_F, currArr,  minQ,  qOn ) == true)                  //если собрался правильный набор набор
    {
      uint32_t currTotal = 0;
      for (uint8_t i = 0; i < minQ - qOn; i++)                   //подсчитали цену
      {
        currTotal += spanners[currArr[i]].price;
      }
      if (currTotal < tempTotal)                                 //если цена  меньше записанной или это первый набор
      {
        tempTotal = currTotal;                                    //записываем цену

        for (uint8_t i = 0; i < qOff; i++)                        //темп аррей делаем пустым
         tempArr[i] = 0;

        for (uint8_t i = 0; i < minQ - qOn; i++)
          tempArr[currArr[i]] = 1;                            //записываем в темп аррей
        flagComplect = true;                                      //поднимаем флаг "собран комплект"

      }
    }
    for (uint8_t i = 0; i < minQ - qOn; i++)                      //сбросили ключи в "off"
      spanners[currArr[i]].included = off;

      
//Здесь начинается бред. Строки 135,136; 158,159; 178,179; 198,199
//в этом коде лишние, они тут просто не нужны
//Но если их закомментить, время выполнения УВЕЛИЧИВАЕТСЯ!!!


    while (NextSet(currArr, qOff-1, minQ - qOn))                     //новое сочетание ключей
    {
      uint32_t currTotal = 0;
      for (uint8_t i = 0; i < minQ - qOn; i++)                   //подсчитали цену
      {
        currTotal += spanners[currArr[i]].price;
      }
      if (currTotal >= tempTotal)                                //"граница" по цене
      {
        continue;
      }
      for (uint8_t i = 0; i < minQ - qOn; i++)                     //сделали их "on"
        spanners[currArr[i]].included = on;


     if (totalSizeOn1(arr_B_F, sizeA_B_F, currArr,  minQ,  qOn ) == true)                          //если собрался правильный набор набор
      {

        if  (currTotal < tempTotal )                              //если цена  меньше записанной или это первый набор
        {
          tempTotal = currTotal;                                   //записываем цену
          for (uint8_t i = 0; i < qOff; i++)                       //темп аррей делаем пустым
            tempArr[i] = 0;
          for (uint8_t i = 0; i < minQ - qOn; i++)
          {
            tempArr[currArr[i]] = 1;                           //записываем в темп аррей
          }
          flagComplect = true;                                     //поднимаем флаг "собран комплект"
        }
      }

      for (uint8_t i = 0; i < minQ - qOn; i++)                     //сбросили ключи в "off"
       spanners[currArr[i]].included = off;
    }

    delete[] currArr;                                              // динамич. массив удаляем

    if (flagComplect == true)                                      // комплект был создан мин.1 раз
      complectYes = true;

    if (flagComplect == false && complectYes == true)               //если в иттерации не нашли комплект дешевле
    { //и комплект был создан ранее выходим
      for (uint8_t i = 0; i < qOff; i++)
        spanners[i].included = tempArr[i];
      break;
    }

    if ( qOff == minQ + qOn)                                            //Последняя иттер.
    {
      for (uint8_t i = 0; i < qOff; i++)
        spanners[i].included = tempArr[i];
    }
  }
}
//-------------------------------------------------


//
//Функция вычисляет  количество существующих размеров среди включенных "On"ключей и сравнивает с кол-вом сущ. размеров
//
bool totalSizeOn1(uint8_t *arr_B_F, uint8_t sizeA_B_F, uint8_t *currA, uint8_t minQ, uint8_t qOn )
{
  uint8_t inSize = 0;
  for (uint8_t i = 0; i < sizeA_B_F; i++)
  {
    bool flag = false;

    for (uint8_t k = 0; k < minQ - qOn; k++)
    {
      if (arr_B_F[i] == spanners[currA[k]].size1 ||
          arr_B_F[i] == spanners[currA[k]].size2)
      {
        flag = true;
      }
    }
    if (flag) inSize++;
  }
  if (inSize != sizeA_B_F)
    return false;
  else return true;
}
//---------------------------------------------------------

//
//Функция всех сочетаний для чисел 1…n по m.
//Честно содрана на <a href="https://prog-cpp.ru/combinations/" title="https://prog-cpp.ru/combinations/" rel="nofollow">https://prog-cpp.ru/combinations/</a>
//
bool NextSet(uint8_t *a, uint8_t  n, uint8_t  m)
{
  uint8_t k = m;
  for (int i = k - 1; i >= 0; --i)
    if (a[i] < n - k + i + 1)
    {
      ++a[i];
      for (uint8_t j = i + 1; j < k; ++j)
      {
        a[j] = a[j - 1] + 1;

      }
      return true;
    }
  return false;
}
//-----------------------------------------------------

//
//Функция подсчета невключенных(off)ключей
//
uint8_t offSpanners()
{
  uint8_t j = 0;
  for (uint8_t i = 0; i < (totalSpanners ); i++)
  {
    if (spanners[i].included == off)
      j++;
  }
  return j;
}
//----------------------------------------

//
// функция сортировки ключей по "off"; ключи со значением included == off станут первыми
//
void sortOff(Spanner * spanarray)
{
  Spanner tmp[] = {{0, 0, 0}};
  for (uint8_t i = 0; i < (totalSpanners ); i++)
  {
    for (int j = 0; j < totalSpanners - 1; j++)
    {
      if ((spanarray[j].included) > (spanarray[j + 1].included))
      {
        tmp[0] = spanarray[j];
        spanarray[j] = spanarray[j + 1];
        spanarray[j + 1] = tmp[0];
      }
    }
  }
}
//------------------------------------------------------

//
//Функция исключает из анализа (excluded) ключи, размеры которых дублируют обязательно включенные функцией unique()
//
//
void exclud()
{
  uint8_t inSp = 0;
  for (uint8_t i = 0; i < totalSpanners; i++)
  {
    if (spanners[i].included == on) inSp++;
  }
  inSp = inSp * 2;
  uint8_t *arrayTemp = new uint8_t[inSp];
  uint8_t j = 0;
  for (uint8_t i = 0; i < totalSpanners; i++)
  {
    if (spanners[i].included == on)
    {
      arrayTemp[j] = spanners[i].size1;
      j++;
      arrayTemp[j] = spanners[i].size2;
      j++;
    }
  }
  for (uint8_t i = 0; i < totalSpanners; i++)
  {
    bool flag1 = false;
    bool flag2 = false;
    if (spanners[i].included == off)
    {
      for (uint8_t k = 0; k < j; k++)
      {
        if (spanners[i].size1 == arrayTemp[k] )
        {
          flag1 = true;
        }
        if (spanners[i].size2 == arrayTemp[k])
        {
          flag2 = true;
        }
      }

    }
    if (flag1 == true && flag2 == true )
    {
      spanners[i].included = excluded;
    }
  }
  delete[] arrayTemp;
}
//-----------------------------------------------------------

//
// Функция определяет неповторяющиеся размеры и ключи, которым они принадлежат, "делаем" "on"
//
uint8_t unique()
{
  uint8_t uniqueSpanner = 0;
  for (uint8_t i = 0; i < totalSpanners; i++)
  {
    bool flag1 = false;
    bool flag2 = false;
    for (uint8_t k = 0; k < totalSpanners; k++)
    {
      if (i == k) continue;                              //сам на себя
      if (spanners[k].included == excluded) continue;     //на удаленный
      if (spanners[i].size1 == spanners[k].size1 ||
          spanners[i].size1 == spanners[k].size2)
      {
        flag1 = true;
      }
      if (spanners[i].size2 == spanners[k].size1 ||
          spanners[i].size2 == spanners[k].size2)
      {
        flag2 = true;
      }
    }
    if (flag1 == false || flag2 == false)
    {
      spanners[i].included = on;
      uniqueSpanner++;
    }
  }
  //Serial.print(uniqueSpanner);
  return uniqueSpanner;

}
//------------------------------------------

//
//Функция вычисляет общее количество существующих размеров и Функция удаляет (excluded) дубли ключей
//
uint8_t totalSize()
{
  uint8_t arrSize[totalSpanners * 2] = {};
  uint8_t inSize = 0;
  uint8_t y = 0;
  for (uint8_t i = 0; i < totalSpanners; i++)
  {
    arrSize[y] = spanners[i].size1;
    y++;
    arrSize[y] = spanners[i].size2;
    y++;
    for (int k = i - 1; k >= 0; k--)
    {

      if ((spanners[i].size1 == spanners[k].size1 ||
           spanners[i].size1 == spanners[k].size2) &&
          (spanners[i].size2 == spanners[k].size1 ||
           spanners[i].size2 == spanners[k].size2))

      {
        spanners[i].included = excluded;
      }
    }

  }
  for (uint8_t i = 0; i < totalSpanners * 2; i++)
  {
    uint8_t j = 0;
    while (j < i && arrSize[j] != arrSize[i])
      ++j;

    if (j == i)
      inSize ++;
  }
  //Serial.print(inSize);

  return inSize;
}

//-------------------------------------------------------


//
//Функция вычисляет общее количество размеров в "он" ключах
//
uint8_t onSize(int8_t qOn)
{
  uint8_t arrSize[qOn * 2] = {};
  uint8_t inSize = 0;
  uint8_t y = 0;

  for (uint8_t i = 0; i < totalSpanners; i++)
  {
    if (spanners[i].included == on)
    {
      arrSize[y] = spanners[i].size1;
      y++;
      arrSize[y] = spanners[i].size2;
      y++;
    }
  }

  for (uint8_t i = 0; i < qOn * 2; i++)
  {
    uint8_t j = 0;
    while (j < i && arrSize[j] != arrSize[i])
      ++j;

    if (j == i)
      inSize ++;
  }
  //Serial.print(inSize);

  return inSize;
}

//-------------------------------------------------------


void arrey__B_F(uint8_t qOff, uint8_t qOn, uint8_t *arrB_F)
{
  uint8_t arrOn[qOn * 2] = {};
  uint8_t arrSize[totalSpanners * 2] = {};
  uint8_t inSize = 0;
  uint8_t y = 0;
  uint8_t z = 0;
  for (uint8_t i = 0; i < totalSpanners; i++)
  {
    if (spanners[i].included == on)
    {
      arrOn[y] = spanners[i].size1;
      y++;
      arrOn[y] = spanners[i].size2;
      y++;
    }
    arrSize[z] = spanners[i].size1;
    z++;
    arrSize[z] = spanners[i].size2;
    z++;
  }
  for (uint8_t i = 0; i < totalSpanners * 2; i++)
  {
    uint8_t j = 0;
    while (j < i && arrSize[j] != arrSize[i])
      ++j;

    if (j == i)
    {
      bool flag = true;
     for (uint8_t k = 0; k < qOn * 2; k++)
        if (arrSize[i] == arrOn[k])
        {
          flag = false;
          
        }
      if (flag)
      {
        arrB_F[inSize] = arrSize[i];
        //Serial.print(inSize); Serial.print(',');
        inSize ++;
      }
    }
  }
}


//
// функция сортировки ключей от дешевых к дорогим
//
void spanSort(Spanner * spanarray)
{
  Spanner tmp[] = {{0, 0, 0}};
  for (uint8_t i = 0; i < (totalSpanners ); i++)
  {
    for (int j = 0; j < totalSpanners - 1; j++)
    {
      if ((spanarray[j].price) > (spanarray[j + 1].price))
      {
        tmp[0] = spanarray[j];
        spanarray[j] = spanarray[j + 1];
        spanarray[j + 1] = tmp[0];
      }
    }
  }
}
//------------------------------------------------------
void setup(void) {
  Serial.begin(9600);
  const uint32_t start = millis();
  doCalculations();
  const uint32_t duration = millis() - start;
  printResults();
  Serial.print("Время расчёта: ");
  Serial.print(duration);
  Serial.println(" миллисекунд");
}

void loop(void) {}

Циклы, о которых идет речь - стр. 178,179 и 198,199.

Собственно вопрос - что не так с Ардуиновским компилятором?

ПС. В моей версии ИДЕ 1.8.7 все ожидаемо: время с циклами 183 мс, без - 167мс