С++: Оптимизация скорости с помощью вектора/массива?

Ответ 1

Вот какой код, который проверяет несколько разных методов.

#include <chrono>
#include <iostream>
#include <vector>

int main()
{
  typedef std::chrono::high_resolution_clock clock;

  unsigned n1 = 1000;
  unsigned n2 = 1000;

  // Original method
  {
    auto start = clock::now();
    for (unsigned i = 0; i < 10000; ++i)
    {
      std::vector<std::vector<long long>> vec(n1, std::vector<long long>(n2));
      // vec is initialized to zero already

      // do stuff
    }
    auto elapsed_time = clock::now() - start;

    std::cout << elapsed_time.count() << std::endl;
  }


  // reinitialize values to zero at every pass in the loop
  {
    auto start = clock::now();
    std::vector<std::vector<long long>> vec(n1, std::vector<long long>(n2));
    for (unsigned i = 0; i < 10000; ++i)
    {
      // initialize vec to zero at the start of every loop
      for (unsigned j = 0; j < n1; ++j)
        for (unsigned k = 0; k < n2; ++k)
            vec[j][k] = 0;

      // do stuff
    }
    auto elapsed_time = clock::now() - start;

    std::cout << elapsed_time.count() << std::endl;
  }

  // clearing the vector this way is not optimal since it will destruct the
  // inner vectors
  {
    auto start = clock::now();
    std::vector<std::vector<long long>> vec(n1, std::vector<long long>(n2));
    for (unsigned i = 0; i < 10000; ++i)
    {
      vec.clear();
      vec.resize(n1, std::vector<long long>(n2));

      // do stuff
    }
    auto elapsed_time = clock::now() - start;

    std::cout << elapsed_time.count() << std::endl;
  }

  // equivalent to the second method from above
  // no performace penalty
  {
    auto start = clock::now();
    std::vector<std::vector<long long>> vec(n1, std::vector<long long>(n2));
    for (unsigned i = 0; i < 10000; ++i)
    {
      for (unsigned j = 0; j < n1; ++j)
      {
        vec[j].clear();
        vec[j].resize(n2);
      }

      // do stuff
    }
    auto elapsed_time = clock::now() - start;

    std::cout << elapsed_time.count() << std::endl;
  }
}

Изменить. Я обновил код, чтобы сделать более справедливое сравнение между этими методами. Изменить 2: немного очистили код, способы 2 или 4 - это путь.

Ниже приведены таймеры четырех вышеперечисленных методов на моем компьютере:

16327389
15216024
16371469
15279471

Дело в том, что вы должны попробовать различные методы и профайл вашего кода.

Ответ 2

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

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

Не используйте необработанный массив - он не дает вам никаких преимуществ и только проблем.

Ответ 3

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

источник

Кроме этого,

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

Ответ 4

Почему бы не что-то подобное:

{
    vector< vector<long long> > vec(n1, vector<long long>(n2));

    for (int i=0; i<bound; i++){

         //about three more for-loops here

         vec.clear();
    }
}

Изменить: добавлены рамки области, -)

Ответ 5

В дополнение к предыдущим комментариям:

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

Ответ 6

Хорошо, если вы действительно обеспокоены производительностью (и знаете заранее размер n1 и n2), но не хотите использовать массив C-стиля, std::array может быть вашим другом.

ИЗМЕНИТЬ: Учитывая ваше редактирование, кажется, что std::array не является подходящей заменой, поскольку в то время как размер вектора не изменяет каждую итерацию, он до сих пор не известен до компиляции.

Ответ 7

Так как вы должны reset значения вектора до 0 на каждой итерации, с практической точки зрения этот вопрос сводится к тому, что "это стоимость выделения и освобождения памяти для вектора дешево или дорого по сравнению с вычислениями внутри циклов".

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

Если ваши вычисления и обновления чрезвычайно быстрые, а распределение/освобождение вектора относительно дорого, вы можете использовать std::fill для заполнения нулей в массиве в конце/начале каждой итерации через цикл.

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

Ответ 8

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