Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.86/22: Рейтинг темы: голосов - 22, средняя оценка - 4.86
566 / 405 / 132
Регистрация: 22.11.2017
Сообщений: 1,019
1

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

07.02.2019, 10:21. Показов 4282. Ответов 31
Метки нет (Все метки)

Всем привет!
Попробовал сравнить время заполнения векторов в векторе и массивов в массиве (динамические) случайными числами, получаемыми 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 и вектора в векторе и таким же образом массивы в массиве, но чтобы вектор выиграл по времени.
Возможно я использовал недостаточно чёткий алгоритм заполнения векторов и массивов.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
07.02.2019, 10:21
Ответы с готовыми решениями:

Двумерный массив со случайными числами
Пытаюсь создать двумерный массив со случайными числами( без разницы, какие диапазоны). Написал одну...

Задать двумерный массив со случайными числами
Добрый день, мне нужно задать двумерный массив с рандомными числами. Что я сделал:procedure...

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

Заполнить двумерный массив случайными числами
Заполнить двумерный массив случайными числами в диапазоне от 1 до N Виконати заповнення...

__________________

Записывайтесь на профессиональные курсы C++ разработчиков
31
Mental handicap
1243 / 621 / 171
Регистрация: 24.11.2015
Сообщений: 2,426
07.02.2019, 12:20 2
Цитата Сообщение от 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);
это тоже не имеет отношение к замеру на "заполнение"
0
566 / 405 / 132
Регистрация: 22.11.2017
Сообщений: 1,019
07.02.2019, 12:26  [ТС] 3
Цитата Сообщение от Azazel-San Посмотреть сообщение
Начнем с того что это не массивы в массиве, а массив указателей на массивы
Это не массив указателей на массивы, это массив указателей на массив указателей на ячейки памяти, где располагаются значения.
Цитата Сообщение от Azazel-San Посмотреть сообщение
Это что, зачем?
Чтобы память зарезервировать? Без него тоже работает?
Цитата Сообщение от Azazel-San Посмотреть сообщение
Вы замеряете скорость создания вектора или его заполнение?
Я замеряю время создания + заполнения при создании через вектора, через массивы.
Цитата Сообщение от Azazel-San Посмотреть сообщение
это тоже не имеет отношение к замеру на "заполнение"
Если не зарезервировать память, то массив, который обслуживает вектор (как правильно сказать?) будет пересоздаваться и переливать значения, чтобы расширится, на что нужно время. Это подтверждает vector<T>::capacity().
0
Mental handicap
1243 / 621 / 171
Регистрация: 24.11.2015
Сообщений: 2,426
07.02.2019, 12:42 4
Лучший ответ Сообщение было отмечено SomniPhobia как решение

Решение

Допустим возьмем обычный вектор.
Кот:
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 или методы для заполнения вектора/нативного массива только дает небольшое замедление, генератор рандомных чисел тоже такое се, мы проверяем заполнение, какая нам раница чем? + вы еще проверяете на создание.
1
566 / 405 / 132
Регистрация: 22.11.2017
Сообщений: 1,019
07.02.2019, 12:42  [ТС] 5
Цитата Сообщение от SomniPhobia Посмотреть сообщение
Это не массив указателей на массивы, это массив указателей на массив указателей на ячейки памяти, где располагаются значения.
Это я не правильно сказал.
Цитата Сообщение от Azazel-San Посмотреть сообщение
Это что, зачем?
Без этого ошибку выдало на этапе выполнения программы.
Цитата Сообщение от Azazel-San Посмотреть сообщение
это тоже не имеет отношение к замеру на "заполнение"
Вот скрин без резервации.
0
Миниатюры
Сделайте, чтобы двумерный вектор обогнал двумерный массив при заполнении случайными числами  
Mental handicap
1243 / 621 / 171
Регистрация: 24.11.2015
Сообщений: 2,426
07.02.2019, 12:48 6
Цитата Сообщение от Azazel-San Посмотреть сообщение
str.reserve(count0);
там тогда не резерв, а ресайз надо.
0
566 / 405 / 132
Регистрация: 22.11.2017
Сообщений: 1,019
07.02.2019, 12:48  [ТС] 7
Цитата Сообщение от Azazel-San Посмотреть сообщение
std::vector<int> experimental(size);
Тут не только объявляется вектор, но ещё нулями заполняется.

Добавлено через 37 секунд
Цитата Сообщение от Azazel-San Посмотреть сообщение
там тогда не резерв, а ресайз надо.
Тогда он нулями заполнится. А потом перезаписывать на случайные.
0
Mental handicap
1243 / 621 / 171
Регистрация: 24.11.2015
Сообщений: 2,426
07.02.2019, 13:00 8
Цитата Сообщение от SomniPhobia Посмотреть сообщение
Тут не только объявляется вектор, но ещё нулями заполняется.
Ну, я это не замеряю если не заметили.
0
566 / 405 / 132
Регистрация: 22.11.2017
Сообщений: 1,019
07.02.2019, 13:02  [ТС] 9
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();
}
0
Миниатюры
Сделайте, чтобы двумерный вектор обогнал двумерный массив при заполнении случайными числами   Сделайте, чтобы двумерный вектор обогнал двумерный массив при заполнении случайными числами  
Mental handicap
1243 / 621 / 171
Регистрация: 24.11.2015
Сообщений: 2,426
07.02.2019, 13:23 10
SomniPhobia, я откуда знаю что делает ваша программа. Первый квадрат ваш на графике, в самом нижнем левом углу, посмотрите и сравните эти две картинки смотря только на этот один квадрат, отклонения почти идентичны (только смотрите на отлонение между линиями, а не относительно осей).

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

Добавлено через 4 минуты
Кстати в своем первом замере с вектором на push_back я сделал ошибку из-за констуктора, его надо убрать, но мы всеравно проиграем из-за push_back'a.
0
566 / 405 / 132
Регистрация: 22.11.2017
Сообщений: 1,019
07.02.2019, 13:47  [ТС] 11
Цитата Сообщение от 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() просто чуть дольше заполнение, но эта функция если применяется к вектору, то и к массиву аналогично - подразумевается равноправность данных для заполнения.
0
566 / 405 / 132
Регистрация: 22.11.2017
Сообщений: 1,019
07.02.2019, 14:01  [ТС] 12
Ещё замеры.
Начальное значение длины контейнера/массива 1 000.
Шаг 10 000.
Конечное значение 2 000 000.
Единицы измерения времени миллисекунды.
0
Миниатюры
Сделайте, чтобы двумерный вектор обогнал двумерный массив при заполнении случайными числами  
566 / 405 / 132
Регистрация: 22.11.2017
Сообщений: 1,019
07.02.2019, 14:03  [ТС] 13
Погрешность? Не знаю. На графиках прослеживаются 2 линии, да значения, формирующие их колеблются, но разброс от линии не велик.
0
566 / 405 / 132
Регистрация: 22.11.2017
Сообщений: 1,019
07.02.2019, 14:09  [ТС] 14
Ещё скрин.
0
Миниатюры
Сделайте, чтобы двумерный вектор обогнал двумерный массив при заполнении случайными числами  
566 / 405 / 132
Регистрация: 22.11.2017
Сообщений: 1,019
07.02.2019, 14:10  [ТС] 15
Две последние картинки про заполнение через
static inline constexpr std::size_t magic_number = 0xFF;
0
Mental handicap
1243 / 621 / 171
Регистрация: 24.11.2015
Сообщений: 2,426
07.02.2019, 14:12 16
SomniPhobia, значит при каждом вызове цикла вы вызываете вашу ф-ю test_array?
Вижу в ней создание динамического массива, а очистки памяти не вижу, у вас там утечка памяти. Если я ничего не пропустил.
1
566 / 405 / 132
Регистрация: 22.11.2017
Сообщений: 1,019
07.02.2019, 14:22  [ТС] 17
Цитата Сообщение от Azazel-San Посмотреть сообщение
Вижу в ней создание динамического массива, а очистки памяти не вижу, у вас там утечка памяти.
Да, утечка памяти была. Поправил. Спасибо!

Добавлено через 4 минуты
Так быстрее заполняется, почти в два раза угол от x до прямой меньше.
C++
1
2
3
    auto start = clock_type::now();
    vector<int> v(count0, magic_number);
    auto finish = clock_type::now();
0
566 / 405 / 132
Регистрация: 22.11.2017
Сообщений: 1,019
07.02.2019, 14:25  [ТС] 18
Azazel-San, вот скрины.
Вектор объявляется + заполняется без цикла.
Вектор только заполняется одним и тем же числом. Забыл дописать: в цикле a[i] = ...;
0
Миниатюры
Сделайте, чтобы двумерный вектор обогнал двумерный массив при заполнении случайными числами   Сделайте, чтобы двумерный вектор обогнал двумерный массив при заполнении случайными числами  
Mental handicap
1243 / 621 / 171
Регистрация: 24.11.2015
Сообщений: 2,426
07.02.2019, 14:29 19
SomniPhobia, не знаю, у меня значения вышли +/- одинаковые, что с нативным массивом, что с вектором, разница была в ~0.002 что может быть на уровне погрешности.
0
566 / 405 / 132
Регистрация: 22.11.2017
Сообщений: 1,019
07.02.2019, 14:35  [ТС] 20
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();
}
Графики совпали.
1
Миниатюры
Сделайте, чтобы двумерный вектор обогнал двумерный массив при заполнении случайными числами  
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
07.02.2019, 14:35

Заказываю контрольные, курсовые, дипломные работы и диссертации здесь.

Заполнить двумерный массив случайными числами
Задача на Паскале: Заполнит двумерный массив размерностью N*M(константы) случайными числами и...

Заполнить двумерный массив случайными числами
Заполнить двумерный массив случайными числами по главной диагонали. Напечатать оба массива. uses...

Заполнить двумерный массив случайными числами
Заполнить двумерный массив с++ случайными числами

Заполнить двумерный массив случайными числами
Задача на Паскале: Заполнит двумерный массив размерностью 6*6(константы) случайными числами и...

Двумерный массив заполнить случайными числами.
Прошу прощения, но сам понять что-то никак. Никогда не был силён в информатике. Необходим двумерный...

Заполнить динамический двумерный массив случайными числами
Как заполнить матрицу рандомными числами и чтобы было разное количество строк и столбцов через...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.