Сделайте, чтобы двумерный вектор обогнал двумерный массив при заполнении случайными числами

@SomniPhobia · Регистрация: 22.11.2017

Студворк — интернет-сервис помощи студентам

Всем привет!
Попробовал сравнить время заполнения векторов в векторе и массивов в массиве (динамические) случайными числами, получаемыми 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 · 07.02.2019, 12:20

Сообщение от SomniPhobia

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

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

Сообщение от SomniPhobia

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

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

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

Сообщение от SomniPhobia

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

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

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

Сообщение от SomniPhobia

str.reserve(count0);

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

@SomniPhobia · 07.02.2019, 12:26 **[ТС]**

Сообщение от Azazel-San

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

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

Сообщение от Azazel-San

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

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

Сообщение от Azazel-San

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

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

Сообщение от Azazel-San

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

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

@Azazel-San · 07.02.2019, 12:42

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

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 минуту

Сообщение от SomniPhobia

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

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

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

Сообщение от SomniPhobia

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

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

Сообщение от SomniPhobia

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

Ясно..

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

@SomniPhobia · 07.02.2019, 12:42 **[ТС]**

Сообщение от SomniPhobia

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

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

Сообщение от Azazel-San

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

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

Сообщение от Azazel-San

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

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

@Azazel-San · 07.02.2019, 12:48

Сообщение от Azazel-San

str.reserve(count0);

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

@SomniPhobia · 07.02.2019, 12:48 **[ТС]**

Сообщение от Azazel-San

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

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

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

Сообщение от Azazel-San

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

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

@Azazel-San · 07.02.2019, 13:00

Сообщение от SomniPhobia

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

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

@SomniPhobia · 07.02.2019, 13:02 **[ТС]**

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 · 07.02.2019, 13:23

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

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

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

@SomniPhobia · 07.02.2019, 13:47 **[ТС]**

Сообщение от 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
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.

Сообщение от Azazel-San

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

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

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

@SomniPhobia · 07.02.2019, 14:01 **[ТС]**

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

@SomniPhobia · 07.02.2019, 14:03 **[ТС]**

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

@SomniPhobia · 07.02.2019, 14:09 **[ТС]**

Ещё скрин.

@SomniPhobia · 07.02.2019, 14:10 **[ТС]**

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

@Azazel-San · 07.02.2019, 14:12

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

@SomniPhobia · 07.02.2019, 14:22 **[ТС]**

Сообщение от Azazel-San

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

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

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

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

@SomniPhobia · 07.02.2019, 14:25 **[ТС]**

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

@Azazel-San · 07.02.2019, 14:29

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

@SomniPhobia · 07.02.2019, 14:35 **[ТС]**

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();
}

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

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@Azazel-San Mental handicap 1246 / 624 / 171 Регистрация: 24.11.2015 Сообщений: 2,429
	07.02.2019, 13:23
	SomniPhobia, я откуда знаю что делает ваша программа. Первый квадрат ваш на графике, в самом нижнем левом углу, посмотрите и сравните эти две картинки смотря только на этот один квадрат, отклонения почти идентичны (только смотрите на отлонение между линиями, а не относительно осей). Добавлено через 8 минут Впринципе нижняя полоска, как я понимаю для нативного массива ожидаема, у нас доступ к элементу происходит за О(1), лучше уже не может быть, с вектором тоже самое, отклонение должны быть минимальны или на уровне погрешности. Добавлено через 4 минуты Кстати в своем первом замере с вектором на push_back я сделал ошибку из-за констуктора, его надо убрать, но мы всеравно проиграем из-за push_back'a. 0

@SomniPhobia 602 / 439 / 137 Регистрация: 22.11.2017 Сообщений: 1,407
	07.02.2019, 14:01 [ТС]
	Ещё замеры. Начальное значение длины контейнера/массива 1 000. Шаг 10 000. Конечное значение 2 000 000. Единицы измерения времени миллисекунды. Миниатюры 0

@SomniPhobia 602 / 439 / 137 Регистрация: 22.11.2017 Сообщений: 1,407
	07.02.2019, 14:03 [ТС]
	Погрешность? Не знаю. На графиках прослеживаются 2 линии, да значения, формирующие их колеблются, но разброс от линии не велик. 0

@SomniPhobia 602 / 439 / 137 Регистрация: 22.11.2017 Сообщений: 1,407
	07.02.2019, 14:09 [ТС]
	Ещё скрин. Миниатюры 0

@SomniPhobia 602 / 439 / 137 Регистрация: 22.11.2017 Сообщений: 1,407
	07.02.2019, 14:10 [ТС]
	Две последние картинки про заполнение через static inline constexpr std::size_t magic_number = 0xFF; 0

@Azazel-San Mental handicap 1246 / 624 / 171 Регистрация: 24.11.2015 Сообщений: 2,429
	07.02.2019, 14:12
	SomniPhobia, значит при каждом вызове цикла вы вызываете вашу ф-ю `test_array`? Вижу в ней создание динамического массива, а очистки памяти не вижу, у вас там утечка памяти. Если я ничего не пропустил. 1

@SomniPhobia 602 / 439 / 137 Регистрация: 22.11.2017 Сообщений: 1,407
	07.02.2019, 14:25 [ТС]
	Azazel-San, вот скрины. Вектор объявляется + заполняется без цикла. Вектор только заполняется одним и тем же числом. Забыл дописать: в цикле a[i] = ...; Миниатюры 0

@Azazel-San Mental handicap 1246 / 624 / 171 Регистрация: 24.11.2015 Сообщений: 2,429
	07.02.2019, 14:29
	SomniPhobia, не знаю, у меня значения вышли +/- одинаковые, что с нативным массивом, что с вектором, разница была в ~0.002 что может быть на уровне погрешности. 0

Сделайте, чтобы двумерный вектор обогнал двумерный массив при заполнении случайными числами

Решение