[@SomniPhobia]

Всем привет!
Попробовал сравнить время заполнения векторов в векторе и массивов в массиве (динамические) случайными числами, получаемыми STL генератором.
Вот фрагменты кода

C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 //Выбор типа часов //Системные настенные //using clock_type = chrono::system_clock; //Монотонные (неотстающие) //using clock_type = chrono::steady_clock; //С самым точным периодом в рамках STL using clock_type = chrono::high_resolution_clock;   //Выбор единиц измерения времени using seconds0 = chrono::duration<double>; using milliseconds0 = chrono::duration<double, ratio_multiply<seconds0::period, milli>>; using microseconds = chrono::duration<double, ratio_multiply<seconds0::period, micro>>;   //Где - то в main() random_device rd;     mt19937 g{ rd() };     uniform_int_distribution<> uid(-10, 10);     auto gen = [&g, &uid]()     {         return uid(g);     };       size_t count0 = 500u;     size_t max_ = 5000u;     size_t step = 500u;       vector<pair<size_t, double>> durations_v;     vector<pair<size_t, double>> durations_a;     for (; count0 <= max_; count0 += step)     {         auto duration_v = test_vector(gen, count0);         auto duration_a = test_array(gen, count0);         durations_v.push_back(make_pair(count0, duration_v));         durations_a.push_back(make_pair(count0, duration_a));         cout << "count0 = " << count0 << endl;     } //main() закончился   double test_vector(function<int()> gen, const size_t &count0) {     auto start = clock_type::now();     vector<vector<int>> v(count0, vector<int>());     for (auto &str : v)     {         str.reserve(count0);         generate_n(back_inserter(str), count0, gen);     }     auto finish = clock_type::now();     auto duration = seconds0(finish - start);     return duration.count(); }   double test_array(function<int()> gen, const size_t &count0) {     auto start = clock_type::now();     int **a = new int*[count0];     for (size_t u = 0u; u < count0; ++u)     {         a[u] = new int[count0];         generate(a[u], a[u] + count0, gen);     }     auto finish = clock_type::now();     auto duration = seconds0(finish - start);     return duration.count(); }

Затем, полученные контейнеры durations_v и durations_a (для вектора и массива соответственно) с парами
first -> длина стороны матрицы n (получается двумерный массив n x n)
second -> время заполнения матрицы такого размера случайными числами,
передаётся в мой алгоритм построения графиков, который начертил то, что приведено на прикреплённом скрине.

Для динамического массива - оранжевый.
Для вектора - циан.
По оси x размер стороны квадратной матрицы n, по оси y кол-во секунд, затраченное на заполнение матрицы такого размера случайными числами. Чем больше (выше) - тем хуже (медленней).
Как видно вектор долго возится (циановые кольца выше оранжевых, то есть затрачено больше времени), массив его обходит по времени.
Я делал ставку на вектора в векторе, но они проиграли массивам в массиве по времени выполнения.
Предлагаю Вам предложить мне коды, которые бы при равноценных условиях заполняли случайными числами по STL и вектора в векторе и таким же образом массивы в массиве, но чтобы вектор выиграл по времени.
Возможно я использовал недостаточно чёткий алгоритм заполнения векторов и массивов.

[@Azazel-San]

проиграли массивам в массиве

Начнем с того что это не массивы в массиве, а массив указателей на массивы.[quote="SomniPhobia;13304811"]

C++ 1 a[u] = new int[count0];

Это что, зачем?

Добавлено через 2 минуты

C++ 1 2 auto start = clock_type::now(); * * vector<vector<int>> v(count0, vector<int>());

Вы замеряете скорость создания вектора или его заполнение?

Добавлено через 1 минуту

str.reserve(count0);

это тоже не имеет отношение к замеру на "заполнение"

[@SomniPhobia]

Начнем с того что это не массивы в массиве, а массив указателей на массивы

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

Это что, зачем?

Чтобы память зарезервировать? Без него тоже работает?

Вы замеряете скорость создания вектора или его заполнение?

Я замеряю время создания + заполнения при создании через вектора, через массивы.

это тоже не имеет отношение к замеру на "заполнение"

Если не зарезервировать память, то массив, который обслуживает вектор (как правильно сказать?) будет пересоздаваться и переливать значения, чтобы расширится, на что нужно время. Это подтверждает vector<T>::capacity().

[@Azazel-San]

Допустим возьмем обычный вектор.
Кот:

C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include <chrono> #include <iostream> #include <vector>   static inline constexpr std::size_t size         = 10000; static inline constexpr std::size_t magic_number = 0xFF;   int main() {     std::vector<int> experimental(size);     auto             start = std::chrono::high_resolution_clock::now();     for (std::size_t i = 0; i < size; ++i) {         experimental.push_back(magic_number);     }     auto                                      end  = std::chrono::high_resolution_clock::now();     std::chrono::duration<double, std::milli> diff = (end - start);     std::cout << "vector: " << diff.count(); }

результат, усредненный по 10 замерам vector: 0.094393

Теперь нативный:

C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include <chrono> #include <iostream> #include <vector>   static inline constexpr std::size_t size         = 10000; static inline constexpr std::size_t magic_number = 0xFF;   int main() {     int* experimental = new int[size];     auto start        = std::chrono::high_resolution_clock::now();     for (std::size_t i = 0; i < size; ++i) {         experimental[i] = magic_number;     }     auto                                      end  = std::chrono::high_resolution_clock::now();     std::chrono::duration<double, std::milli> diff = (end - start);     std::cout << "array: " << diff.count(); }

результат, усредненный по 10 замерам array: 0.001643
Уфф, существенный проигрыш, но постойте в векторе мы же использовали зачем-то push_back, меняем на
experimental[i] = magic_number
результат, усредненный по 10 замерам vector: 0.001478
Упс, разницы нету почти или это погрешность..

Флаги компилятора -Wall -Wextra -std=c++17 -pedantic -O3

Добавлено через 1 минуту

Если не зарезервировать память, то массив, который обслуживает вектор (как правильно сказать?) будет пересоздаваться и переливать значения, чтобы расширится, на что нужно время. Это подтверждает vector<T>::capacity().

И зачем это замерять?

Добавлено через 1 минуту

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

Добавлено через 8 минут

Я замеряю время создания + заполнения при создании через вектора, через массивы.

Ясно..

Добавлено через 3 минуты
Хотя мои замеры просто баловство, по заполению разницы не будет, тк это почти тоже, то что вы используете stl или методы для заполнения вектора/нативного массива только дает небольшое замедление, генератор рандомных чисел тоже такое се, мы проверяем заполнение, какая нам раница чем? + вы еще проверяете на создание.

[@SomniPhobia]

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

Это я не правильно сказал.

Это что, зачем?

Без этого ошибку выдало на этапе выполнения программы.

это тоже не имеет отношение к замеру на "заполнение"

Вот скрин без резервации.

[@Azazel-San]

str.reserve(count0);

там тогда не резерв, а ресайз надо.

[@SomniPhobia]

std::vector<int> experimental(size);

Тут не только объявляется вектор, но ещё нулями заполняется.

Добавлено через 37 секунд

там тогда не резерв, а ресайз надо.

Тогда он нулями заполнится. А потом перезаписывать на случайные.

[@Azazel-San]

Тут не только объявляется вектор, но ещё нулями заполняется.

Ну, я это не замеряю если не заметили.

[@SomniPhobia]

Azazel-San, по Вашим котам я сформировал такой код и графики следующие. Почему такие результаты?

C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 double test_vector(function<int()> gen, const size_t &count0) {     vector<int> v(count0);     auto start = clock_type::now();     for (std::size_t i = 0; i < count0; ++i)     {         v[i] = gen();     }     auto finish = clock_type::now();     auto duration = milliseconds0(finish - start);     return duration.count(); }   double test_array(function<int()> gen, const size_t &count0) {     int *a = new int[count0];     auto start = clock_type::now();     for (std::size_t i = 0; i < count0; ++i)     {         a[i] = gen();     }     auto finish = clock_type::now();     auto duration = milliseconds0(finish - start);     return duration.count(); }

[@Azazel-San]

SomniPhobia, я откуда знаю что делает ваша программа. Первый квадрат ваш на графике, в самом нижнем левом углу, посмотрите и сравните эти две картинки смотря только на этот один квадрат, отклонения почти идентичны (только смотрите на отлонение между линиями, а не относительно осей).

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

Добавлено через 4 минуты
Кстати в своем первом замере с вектором на push_back я сделал ошибку из-за констуктора, его надо убрать, но мы всеравно проиграем из-за push_back'a.

[@SomniPhobia]

я откуда знаю что делает ваша программа

Вот эти две функции, что я сделал, по Вашим котам. + Вот это

C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 random_device rd;     mt19937 g{ rd() };     uniform_int_distribution<> uid(-10, 10);     auto gen = [&g, &uid]()     {         return uid(g);     };       size_t count0 = 1000u;     size_t max_ = 100000u;     size_t step = 1000u;       vector<pair<size_t, double>> durations_v;     vector<pair<size_t, double>> durations_a;     for (; count0 <= max_; count0 += step)     {         auto duration_v = test_vector(gen, count0);         auto duration_a = test_array(gen, count0);         durations_v.push_back(make_pair(count0, duration_v));         durations_a.push_back(make_pair(count0, duration_a));         cout << "count0 = " << count0 << endl;     }

Заметьте, что test_vector() и test_array() чередуются при вызовах. Я не знаю, но компилятор наверно может оптимизировать тем, что одно и тоже число или действие поставит на конвейер. Чередование вызовов должно перебить, если всё таки оптимизация со стороны компилятора возможна.
Затем для durations_v (циан) и durations_a (рыжий) строятся эти графики. first (кол-во элементов) откладывается по x, second (время выполнения) - по y.

Впринципе нижняя полоска, как я понимаю для нативного массива ожидаема

Да. А что с вектором случилось, что он проседает?

Добавлено через 2 минуты
В случае с gen() просто чуть дольше заполнение, но эта функция если применяется к вектору, то и к массиву аналогично - подразумевается равноправность данных для заполнения.

[@SomniPhobia]

Ещё замеры.
Начальное значение длины контейнера/массива 1 000.
Шаг 10 000.
Конечное значение 2 000 000.
Единицы измерения времени миллисекунды.

[@SomniPhobia]

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

[@SomniPhobia]

Ещё скрин.

[@SomniPhobia]

Две последние картинки про заполнение через
static inline constexpr std::size_t magic_number = 0xFF;

[@Azazel-San]

SomniPhobia, значит при каждом вызове цикла вы вызываете вашу ф-ю test_array?
Вижу в ней создание динамического массива, а очистки памяти не вижу, у вас там утечка памяти. Если я ничего не пропустил.

[@SomniPhobia]

Вижу в ней создание динамического массива, а очистки памяти не вижу, у вас там утечка памяти.

Да, утечка памяти была. Поправил. Спасибо!

Добавлено через 4 минуты
Так быстрее заполняется, почти в два раза угол от x до прямой меньше.

C++
1 2 3     auto start = clock_type::now();     vector<int> v(count0, magic_number);     auto finish = clock_type::now();

[@SomniPhobia]

Azazel-San, вот скрины.
Вектор объявляется + заполняется без цикла.
Вектор только заполняется одним и тем же числом. Забыл дописать: в цикле a[i] = ...;

[@Azazel-San]

SomniPhobia, не знаю, у меня значения вышли +/- одинаковые, что с нативным массивом, что с вектором, разница была в ~0.002 что может быть на уровне погрешности.

[@SomniPhobia]

Azazel-San, при такой записи

C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 double test_vector(function<int()> gen, const size_t &count0) {     vector<int> v(count0);     auto h = v.data();     auto start = clock_type::now();     for (std::size_t i = 0; i < count0; ++i)     {         h[i] = gen();     }     /*for (std::size_t i = 0; i < count0; ++i)     {         v[i] = magic_number;     }*/     auto finish = clock_type::now();     auto duration = milliseconds0(finish - start);     return duration.count(); }   double test_array(function<int()> gen, const size_t &count0) {     int *a = new int[count0];     auto start = clock_type::now();     for (std::size_t i = 0; i < count0; ++i)     {         a[i] = gen();     }     auto finish = clock_type::now();     delete[] a;     auto duration = milliseconds0(finish - start);     return duration.count(); }

Графики совпали.