Модифікуючі алгоритми в послідовних контейнерах

Размещено на http://www.allbest.ru/

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

ДЕРЖАВНИЙ ВИЩИЙ НАВЧАЛЬНИЙ ЗАКЛАД «УЖГОРОДСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ»

ІНЖЕНЕРНО-ТЕХНІЧНИЙ ФАКУЛЬТЕТ КАФЕДРА КОМП'ЮТЕРНИХ СИСТЕМ ТА МЕРЕЖ

Лабораторна робота №2

з дисципліни «системне програмне забезпечення»

«Модифікуючі алгоритми в послідовних контейнерах»

студента 1-го курсу СТ

спеціальності 123 -

«комп'ютерна інженерія»

Рикавця Едуарда Васильовича

Ужгород 2021 р



Етап 1

Вивчив теорію, та ще раз додатково проробив і осмислив кожний із прикладів з лекції про «Модифікуючі алгоритми в послідовних контейнерах», щоб полегшити виконання лабораторної роботи, та не зіткнутися із помилками.

Етап 2

Задача A (rotate)

Циклічно зсунути вправо на одну позицію елементи першої половини послідовності. Третю і четверту четвертини послідовності поміняти місцями.

	Задана послідовність	Результуюча послідовність
Тест	1 2 3 4 5 6 7 8	4 1 2 3 7 8 5 6

Лістинг програми для Vector:

Рис. 1 Лістинг програми A (vector)



Рис. 2 Вивід результату та часу (vector)

Лістинг програми для Deque:

Рис. 3 Лістинг програми A (deque)

Рис. 4 Вивід результату та часу (deque)

Лістинг програми для List:



Рис. 5 Лістинг програми A (list)

Рис. 6 Вивід результату та часу (list)

Задачa B - (remove_if)

Вилучити з послідовності елементи кратні nv. Додатково скористатись функцією erase.

	Задана послідовність	Результуюча послідовність
Тест nv=3	1 2 3 4 5 6 7 8	1 2 4 5 7 8

Лістинг програми для Vector:

Рис. 7 Лістинг програми B (vector)

Рис. 8 Вивід результату та часу (vector)

Лістинг програми для Deque:

Рис. 9 Лістинг програми B (deque)



Рис. 10 Вивід результату та часу (deque)

Лістинг програми для List:

Рис. 11 Лістинг програми B (list)

Рис. 12 Вивід результату та часу (list)



Задача C - (swap ranges)

Обміняти між собою елементи двох послідовностей, та слідуючі за ними елементи: x[nv]<->y[nv],.., x[2*nv]<->y[2*nv].

	Задана послідовність	Результуюча послідовність
Тест	x: 1 2 3 4 5 6 7 8 y: 9 8 7 6 5 4 3 2	x: 1 2 7 6 5 4 7 8 y: 9 8 3 4 5 6 3 2

Лістинг програми для Vector:

Рис. 13 Лістинг програми C (vector)



Рис. 14 Вивід результату та часу

Лістинг програми для Deque:

Рис. 15 Лістинг програми C (deque)

Рис. 16 Вивід результату та часу (deque)



Лістинг програми для List:

Рис. 17 Лістинг програми C (list)

Рис. 18 Вивід результату та часу

Задача D - (replace_copy_if)

Скопіювати послідовність x у послідовність y. Замінити у послідовності y елементи a, які задовольняють умову nv<a<3*n на елементи рівні 2*nv.

	Задана послідовність	Результуюча послідовність
Тест nv=3	x: 1 2 3 4 5 6 7 8 y: 1 1 1 1 1 1 1 1	y: 1 2 3 6 6 6 6 6

Лістинг програми для Vector:

Рис.19 Лістинг програми D (vector)

Рис.20 Вивід результату та часу (vector)

Лістинг програми для Deque:



Рис.21 Лістинг програми D (deque)

Рис.22 Вивід результату та часу (deque)

Лістинг програми для List:



Рис.23 Лістинг програми D (list)

послідовність елемент циклічний половина

Рис.24 Вивід результату та часу (list)

Для виконання третього етапу необхідний ось такий фрагмент коду:

Де вибирається діапазон виконання, і після кожного діапазону заміряється час за допомогою бібліотеки.



Етап 3

Дослідницька частина роботи. Дослідити час виконання задачі D. Заповнити таблицю з результатами дослідження.

		Діапазон функції rand()	Час виконання задач варіанту у сек.
			Vector	Deque	List
n	m
10	10	[0;10]	0.000122	0.0003221	0.0003365
100	10	[0;10]	0.0001292	0.0007087	0.0006648
1000	10	[0;10]	0.0003885	0.0127724	0.0131786
10000	100	[0;100]	0.0014712	0.0778483	0.061188
100 000	100	[0;100]	0.0063008	0.594091	0.600958
1000000	1000	[0;1000]	0.069288	6.06934	7.03862
10000000	1000	[0;1000]	65.682857	76.2201	460.147

Висновок: під час роботи даної лабораторної роботи я знайомився з послідовними контейнерами бібліотеки STL, освоїв модифікуючі алгоритми.

При реалізація програм з використанням Vector та Deque, затруднень не виникло. В більшості випадків основний код, співпадає.

А ось при реалізації програм для List, відбулися затруднення при написанні цикла. Скориставшись прикладами з лекцій, та осмисливши свої помилки, виконання відбулося успішно.

З іншими задачами проблем не виникло, все було зроблено чітко за інструкціями, весь матеріал було переглянуто та виконано за шаблонами прикладів задач наведених в теорії.

Налагодив код програми для всіх типів контейнерів та їх комбінацій.

В 3-етапі дослідив час виконання Задачі D - (replace_copy_if). Результати виведенні в таблицю з урахуванням певних діапазонів. В моєму випадку найкращі результати становить Vector.

Основні характеристики комп'ютера:



Додаткове завдання:

Дослідження та аналіз часу виконання окремих кроків програми. У коді основні кроки відмічені числами 1,2,3.

Фрагмент коду з використанням advance:

#include <iostream>

#include <list>

#include <algorithm>

#include <omp.h>

#define N 100

#define C false

using namespace std;

void main()

{

list <int> x;

double t1 = omp_get_wtime();

for (int i = 0; i < N; i++) x.push_back(i + 1); // 1

double t2 = omp_get_wtime();

cout << "Time ->l = " << t2 - t1 << endl;

if (C) for (auto i = x.begin(); i != x.end(); i++)

cout << *i << ' ';

cout << endl;

list <int>::iterator ib, ie;

ib = x.begin(); ie = x.begin();

cout << "N=" << x.size() << endl;

t1 = omp_get_wtime();

advance(ib, x.size() / 4);

advance(ie, (x.size() / 4) * 3);

//for (int i = 0; i < x.size() / 4; i++) ib++, ie--; // 2

t2 = omp_get_wtime();

cout << "Time iter = " << t2 - t1 << endl;

t1 = omp_get_wtime();

fill(ib, ie, 0); // 3

t2 = omp_get_wtime();

cout << "Time fill = " << t2 - t1 << endl;

if (C) for (auto i = x.begin(); i != x.end(); i++)

cout << *i << ' ';

cout << endl;

system("pause");

}

Таблиця 1

Часові дослідження виконання коду з алгоритмом fill та advanced.

Розмір списку N	Наповнення списку	Переміщення ітераторів	Функція fill
1000	0.0031518	0.0001915	0.0001667
10 000	0.0299126	0.0017829	0.0013626
100 000	0.32515	0.0237499	0.02205
1 000 000	3.19152	0.223183	0.182791
10 000 000	35.6562	2.30024	1.87641

Таблиця 2

Часові дослідження виконання коду з алгоритмом fill та for

Розмір списку N	Наповнення списку	Переміщення ітераторів	Функція fill
1000	0.0028169	0.0015265	0.0028247
10 000	0.0540354	0.0164271	0.0100928
100 000	0.433453	0.143256	0.024784
1 000 000	4.46713	0.52363	0.35718
10 000 000	31.5421	7.1383	5.6284

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

Лістинг програми:

#include <iostream>

#include <vector>

#include <algorithm>

#include <list>

#include <deque>

#include <omp.h>

using namespace std;

const long int n = 10;

int maxD = 10;

int a[n];

int main()

{

for (int i = 0; i < n; i++) a[i] = rand() % maxD;

//Task A -- Vector

cout << endl << "Task A: " << endl;

cout << endl << "Vector" << endl;

int a[] = { 1,2,3,4,5,6,7,8 };

double t1 = omp_get_wtime();

vector <int> v(a, a + 8);

for (int i = 0; i < v.size(); i++) cout << v[i] << ' ';

cout << endl;

rotate(v.begin(), v.begin() + v.size() / 4 + 1, v.begin() + v.size() / 2);

rotate(v.begin() + v.size() / 2, v.begin() + v.size() / 2 + v.size() / 4, v.end());

double t2 = omp_get_wtime();

for (int i = 0; i < v.size(); i++) cout << v[i] << ' ';

cout << endl << "Time: " << t2 - t1 << endl;

//Task A -- Deque

cout << endl << "Deque" << endl;

int a1[] = { 1,2,3,4,5,6,7,8 };

double t3 = omp_get_wtime();

deque <int> v1(a1, a1 + 8);

for (int i = 0; i < v1.size(); i++) cout << v1[i] << ' ';

cout << endl;

rotate(v1.begin(), v1.begin() + v1.size() / 4 + 1, v1.begin() + v1.size() / 2);

rotate(v1.begin() + v1.size() / 2, v1.begin() + v1.size() / 2 + v1.size() / 4, v1.end());

double t4 = omp_get_wtime();

for (int i = 0; i < v1.size(); i++) cout << v1[i] << ' ';

cout << endl << "Time: " << t4 - t3 << endl;

//Task A -- List

cout << endl << "List" << endl;

int a2[] = { 1,2,3,4,5,6,7,8 };

double t5 = omp_get_wtime();

list <int> v2(a2, a2 + 8);

for (auto i = v2.begin(); i != v2.end(); i++)

cout << *i << ' ';

cout << endl;

auto f1 = v2.begin();

advance(f1, v2.size() / 2 - 1);

auto f2 = v2.begin();

advance(f2, v2.size() / 2);

rotate(v2.begin(), f1, f2);

auto f3 = v2.begin();

advance(f3, v2.size() / 2);

auto f4 = v2.begin();

advance(f4, v2.size() / 2 + v.size() / 4);

auto f5 = v2.begin();

advance(f5, v2.size() / 4 * 4);

rotate(f3, f4, v2.end());

double t6 = omp_get_wtime();

for (auto i = v2.begin(); i != v2.end(); i++)

cout << *i << ' ';

cout << endl << "Time: " << t6 - t5 << endl;

//Task B -- Vector

cout << endl << "Task B: " << endl;

cout << endl << "Vector" << endl;

int b[] = { 1,2,3,4,5,6,7,8 };

double t7 = omp_get_wtime();

vector <int> m(b, b + 8);

for (int i = 0; i < m.size(); i++) cout << m[i] << ' ';

cout << endl;

auto it = remove_if(m.begin(), m.end(), [](int b)

{ return b % 3 == 0; });

m.erase(it, m.end());

for (int i = 0; i < m.size(); i++) cout << m[i] << ' ';

double t8 = omp_get_wtime();

cout << endl << "Time: " << t8 - t7 << endl;

//Task B -- Deque

cout << endl << "Deque" << endl;

int b1[] = { 1,2,3,4,5,6,7,8 };

double t9 = omp_get_wtime();

deque <int> m1(b1, b1 + 8);

for (int i = 0; i < m1.size(); i++) cout << m1[i] << ' ';

cout << endl;

auto it1 = remove_if(m1.begin(), m1.end(), [](int b) { return b % 3 == 0; });

m1.erase(it1, m1.end());

for (int i = 0; i < m1.size(); i++) cout << m1[i] << ' ';

double t10 = omp_get_wtime();

cout << endl << "Time: " << t10 - t9 << endl;

//Task B -- List

cout << endl << "List" << endl;

int b2[] = { 1,2,3,4,5,6,7,8 };

double t11 = omp_get_wtime();

list <int> m2(b2, b2 + 8);

for (auto i = m2.begin(); i != m2.end(); i++)

cout << *i << ' ';

cout << endl;

auto it2 = remove_if(m2.begin(), m2.end(), [](int b2)

{ return b2 % 3 == 0; });

m2.erase(it2, m2.end());

for (auto i = m2.begin(); i != m2.end(); i++)

cout << *i << ' ';

double t12 = omp_get_wtime();

cout << endl << "Time: " << t12 - t11 << endl;

//Task C -- Vector

cout << endl << "Task C: " << endl;

cout << endl << "Vector" << endl;

int x[] = { 1,2,3,4,5,6,7,8 };

int y[] = { 9,8,7,6,5,4,3,2 };

double t13 = omp_get_wtime();

vector <int> k(x, x + 8);

vector <int> p(y, y + 8);

for (int i = 0; i < k.size(); i++) cout << k[i] << ' ';

cout << endl;

for (int i = 0; i < p.size(); i++) cout << p[i] << ' ';

cout << endl << "\n";

swap_ranges(k.begin() + 2, k.end() - 2, p.begin() + 2);

for (int i = 0; i < k.size(); i++) cout << k[i] << ' ';

cout << endl;

for (int i = 0; i < p.size(); i++) cout << p[i] << ' ';

double t14 = omp_get_wtime();

cout << endl << "Time: " << t14 - t13 << endl;

//Task C -- Deque

cout << endl << "Deque" << endl;

int x1[] = { 1,2,3,4,5,6,7,8 };

int y1[] = { 9,8,7,6,5,4,3,2 };

double t15 = omp_get_wtime();

deque <int> k1(x, x + 8);

deque <int> p1(y, y + 8);

for (int i = 0; i < k1.size(); i++) cout << k1[i] << ' ';

cout << endl;

for (int i = 0; i < p1.size(); i++) cout << p1[i] << ' ';

cout << endl << "\n";

swap_ranges(k1.begin() + 2, k1.end() - 2, p1.begin() + 2);

for (int i = 0; i < k1.size(); i++) cout << k1[i] << ' ';

cout << endl;

for (int i = 0; i < p1.size(); i++) cout << p1[i] << ' ';

double t16 = omp_get_wtime();

cout << endl << "Time: " << t16 - t15 << endl;

//Task C -- List

cout << endl << "List" << endl;

int x2[] = { 1,2,3,4,5,6,7,8 };

int y2[] = { 9,8,7,6,5,4,3,2 };

double t17 = omp_get_wtime();

list <int> k2(x, x + 8);

list <int> p2(y, y + 8);

for (auto i = k2.begin(); i != k2.end(); i++)

cout << *i << ' ';

cout << endl;

for (auto i = p2.begin(); i != p2.end(); i++)

cout << *i << ' ';

cout << endl << "\n";

swap_ranges(std::next(k2.begin(), 2), std::prev(k2.end(), 2), std::next(p2.begin(), 2));

for (auto i = k2.begin(); i != k2.end(); i++)

cout << *i << ' ';

cout << endl;

for (auto i = p2.begin(); i != p2.end(); i++)

cout << *i << ' ';

double t18 = omp_get_wtime();

cout << endl << "Time: " << t18 - t17 << endl;

//Task D -- Vector

cout << endl << "Task D: " << endl;

cout << endl << "Vector" << endl;

int d[] = { 1,2,3,4,5,6,7,8 };

double t19 = omp_get_wtime();

vector <int> r(d, d + 8);

vector <int> g(8);

for (int i = 0; i < r.size(); i++)

cout << r[i] << ' ';

cout << endl;

replace_copy_if(r.begin(), r.end(), g.begin(),

[](int d) { return d > 3 && d < 10; }, 6);

for (int i = 0; i < g.size(); i++)

cout << g[i] << ' ';

double t20 = omp_get_wtime();

cout << endl << "Time: " << t20 - t19 << endl;

//Task D -- Deque

cout << endl << "Deque" << endl;

double t21 = omp_get_wtime();

int d1[] = { 1,2,3,4,5,6,7,8 };

deque <int> r1(d1, d1 + 8);

deque <int> g1(8);

for (int i = 0; i < r1.size(); i++)

cout << r1[i] << ' ';

cout << endl;

replace_copy_if(r1.begin(), r1.end(), g1.begin(),

[](int d1) { return d1 > 3 && d1 < 10; }, 6);

for (int i = 0; i < g1.size(); i++)

cout << g1[i] << ' ';

double t22 = omp_get_wtime();

cout << endl << "Time: " << t22 - t21 << endl;

//Task D -- List

cout << endl << "List" << endl;

int d2[] = { 1,2,3,4,5,6,7,8 };

double t23 = omp_get_wtime();

list <int> r2(d2, d2 + 8);

list <int> g2(8);

for (auto i = r2.begin(); i != r2.end(); i++)

cout << *i << ' ';

cout << endl;

replace_copy_if(r2.begin(), r2.end(), g2.begin(),

[](int d2) { return d2 > 3 && d2 < 10; }, 6);

for (auto i = g2.begin(); i != g2.end(); i++)

cout << *i << ' ';

double t24 = omp_get_wtime();

cout << endl << "Time: " << t24 - t23 << endl;

return 0;

}

Размещено на Allbest.ru