Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.60/30: Рейтинг темы: голосов - 30, средняя оценка - 4.60
599 / 436 / 136
Регистрация: 22.11.2017
Сообщений: 1,344
1

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

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

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

31
599 / 436 / 136
Регистрация: 22.11.2017
Сообщений: 1,344
07.02.2019, 14:55  [ТС] 21
Author24 — интернет-сервис помощи студентам
Сравнил работу оператора [] для обращения по индексу и метода at() для обращения по индексу. Результаты почти одинаковы. В пределах ошибки.
Миниатюры
Сделайте, чтобы двумерный вектор обогнал двумерный массив при заполнении случайными числами   Сделайте, чтобы двумерный вектор обогнал двумерный массив при заполнении случайными числами  
0
599 / 436 / 136
Регистрация: 22.11.2017
Сообщений: 1,344
07.02.2019, 18:05  [ТС] 22
Такое ощущение что оператор [], перегруженный для экземпляров вектора, вызывает метод и/или проверяет указанный индекс на предмет выхода за границы диапазона.

Добавлено через 2 минуты
Я попробовал за передлы индекс указать, выпало исключение vector subsctipt out of range. Значит проверяет всё таки? Иначе бы просто разрешил обратиться в ячейку памяти в окрестностях массива, обслуживаемого данным экземпляром вектора. Оказалось это не выброс исключения, а просто вылет программы при выполнении. А вот at скинул исключение при выходе за границы.
0
18894 / 9852 / 2410
Регистрация: 30.01.2014
Сообщений: 17,295
07.02.2019, 19:48 23
Лучший ответ Сообщение было отмечено SomniPhobia как решение

Решение

Цитата Сообщение от SomniPhobia Посмотреть сообщение
Я попробовал за передлы индекс указать, выпало исключение vector subsctipt out of range. Значит проверяет всё таки? Иначе бы просто разрешил обратиться в ячейку памяти в окрестностях массива, обслуживаемого данным экземпляром вектора. Оказалось это не выброс исключения, а просто вылет программы при выполнении.
Это assert сработал. И срабатывает он только в отладочном режиме. Вы что, замеры делаете в Debug сборке?

Еще бы у вас не было расхождений. В Debug режиме у библиотечных классов куча доп. проверок, чтобы ускорить отладку и отключена оптимизация.
Никто не меряет производительность в отладочном режиме, просто потому что он не для этого.
1
Mental handicap
1246 / 624 / 171
Регистрация: 24.11.2015
Сообщений: 2,429
07.02.2019, 20:08 24
DrOffset, я делал замеры в релизе, лично мне не удалось поймать существенных различий, в ТС какая-то другая ситуация и это все из-за дебага?
0
Неэпический
17870 / 10635 / 2054
Регистрация: 27.09.2012
Сообщений: 26,737
Записей в блоге: 1
07.02.2019, 20:46 25
Лучший ответ Сообщение было отмечено SomniPhobia как решение

Решение

C++
1
2
3
4
5
6
7
8
9
10
11
12
double test_vector(function<int()> gen, const size_t &count0)
{
    auto start = clock_type::now();
    vector<vector<int>> v(count0, vector<int>(count0));
    for (auto & str : v)
    {
        generate_n(str.begin(), count0, gen);
    }
    auto finish = clock_type::now();
    auto duration = seconds0(finish - start);
    return duration.count();
}
Добавлено через 1 минуту
https://wandbox.org/permlink/2QVHwvTv7ad0YWA6
1
37 / 36 / 9
Регистрация: 16.04.2015
Сообщений: 283
07.02.2019, 21:02 26
Цитата Сообщение от SomniPhobia Посмотреть сообщение
Графики совпали.
Понятно, почему совпали. В double test_vector(..) сам вектор Вы не поменяли.
(поменяли копию массива вектора h).
0
599 / 436 / 136
Регистрация: 22.11.2017
Сообщений: 1,344
07.02.2019, 21:04  [ТС] 27
DrOffset, Azazel-San, в режиме release совсем другой результат.
Спасибо DrOffset. Всё дело в режиме запуска оказалось.
Вот код, на который построены прикреплённые графики.
В режиме релиза на 1млн и на 2 млн построилось за считанные секунды. В дебаге - несколько минут потребовалось.
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
double test_vector(const 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(const 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();
}
Миниатюры
Сделайте, чтобы двумерный вектор обогнал двумерный массив при заполнении случайными числами   Сделайте, чтобы двумерный вектор обогнал двумерный массив при заполнении случайными числами   Сделайте, чтобы двумерный вектор обогнал двумерный массив при заполнении случайными числами  

0
Mental handicap
1246 / 624 / 171
Регистрация: 24.11.2015
Сообщений: 2,429
07.02.2019, 21:19 28
SomniPhobia, ну вот и совпали, я что-то не подумал что Вы тестили в дебаге, я знал что нельзя делать замеры в дебаге, но честно сказать не думал что такая сильная разница будет, но видимо особенно это бьет по STL контейнерам, как и сказал DrOffset из-за всяких проверок.
1
18894 / 9852 / 2410
Регистрация: 30.01.2014
Сообщений: 17,295
07.02.2019, 21:20 29
Цитата Сообщение от Azazel-San Посмотреть сообщение
это все из-за дебага?
Это все из-за debug`а.
2
599 / 436 / 136
Регистрация: 22.11.2017
Сообщений: 1,344
07.02.2019, 21:31  [ТС] 30
Croessmah, здравствуйте!
Вот на Ваш вариант кода замеры.
Время в миллисекундах отложено на графике.
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
double test_vector(const function<int()> &gen, const size_t &count0)
{
    auto start = clock_type::now();
    vector<vector<int>> v(count0, vector<int>(count0));
    for (auto &str : v)
    {
        generate_n(str.begin(), count0, gen);
    }
    auto finish = clock_type::now();
    auto duration = milliseconds0(finish - start);
    return duration.count();
}
 
double test_array(const 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);
    }
    delete[] a;
    auto finish = clock_type::now();
    auto duration = milliseconds0(finish - start);
    return duration.count();
}
Миниатюры
Сделайте, чтобы двумерный вектор обогнал двумерный массив при заполнении случайными числами   Сделайте, чтобы двумерный вектор обогнал двумерный массив при заполнении случайными числами   Сделайте, чтобы двумерный вектор обогнал двумерный массив при заполнении случайными числами  

0
599 / 436 / 136
Регистрация: 22.11.2017
Сообщений: 1,344
07.02.2019, 21:49  [ТС] 31
SerVal, не копию. Метод data() вернул указатель на массив, который обслуживает текущий экземпляр класса вектор. Я проверял - назначил значения через h, потом прочитал через v[i] ответы были, то есть там числа были занесены в сам вектор.
Croessmah, Вы даже сделали так, что на дебаге совпали значения вектора и массива, образующих матрицу.
0
37 / 36 / 9
Регистрация: 16.04.2015
Сообщений: 283
08.02.2019, 00:37 32
А.. понятно.. Переменные типа auto x = auto start + auto finish
... сразу и не поймёшь, где объект, а где указатель на него.
0
08.02.2019, 00:37
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
08.02.2019, 00:37
Помогаю со студенческими работами здесь

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

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
32
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru