Структуры данных динамический массив и связанный список, замер времени функций (методов)
Задание:
Реализовать динамический массив:
1.1 Создать структуру DynamicArray для хранения структуры (Структура Бомба имеет следующие поля: вес, цвет, количество тротила в кг) и реализовать в ней основные функции динамического массива:
- push_back() – добавить элемент в конец
- pop_back() – считать и удалить элемент с конца
- get() – считать n-ый элемент
- size() – найти количество элементов
- print() – вывести все элементы с хранящимися данными
- clear() – удалить все элементы и очистить память
1.2 Реализовать дополнительные функции для динамического массива:
- push_front() – добавить элемент в начало
- pop_front() – считать и удалить элемент с самого начала
Реализовать односвязный список:
2.1 Создать структуру Node для базового элемента односвязного списка, она будет включать в себя структуру (Структура Бомба имеет следующие поля: вес, цвет, количество тротила в кг).
2.2 Создать структуру LinkedList и реализовать в ней основные функции односвязного списка:
- push_front() – добавить элемент в начало
- push_back() – добавить элемент в конец
- get() – считать n-ый элемент
- pop_front() – считать и удалить элемент с самого начала
- pop_back() – считать и удалить элемент с конца
- size() – найти количество элементов
- print() – вывести все элементы с хранящимися данными
- clear() – удалить все элементы и очистить память
- Провести сравнение работы динамического массива и односвязного списка (каждый шаг выполнить для обеих структур, замерить и сравнить время каждого шага и всех шагов вместе*):
- 3.1 Добавить в конец 50000 элементов
- 3.2 Добавить в начало 10000 элементов
- 3.3 Считать 20 000 элементов под случайными индексами
- 3.4 Удалить 5000 элементов от начала
- 3.5 Удалить 5000 элементов с конца
*если общее время всех шагов вместе превышает 2-4 секунды, то вероятно ваша реализация некоторых методов не является правильной. //А у меня выходит 27 секунд(
Проблема в том, что некоторые функции (методы) выполняются долго, чем нужно, а именно push_front (18 сек) и pop_front (3.8 сек) в динамическом массиве и get (2.9 сек) с pop_back (2.2 сек) в односвязном списке, в то время как другие методы выполняют менее 0.01 секунды. Методы переделывал, но они все равно выполняются дольше, чем нужно. Возможно ошибка в самом замере времени, а может все-таки эти методы для динамического массива и односвязного списка сделаны не оптимально и долго выполняются. Можете пожалуйста помочь решить эту проблему.
КОД:
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
struct Bomb {
int weight;
char color[10];
int tnt;
};
struct DynamicArray {
Bomb* data;
int capacity;
int current_size;
DynamicArray() {
capacity = 1;
current_size = 0;
data = new Bomb[capacity];
}
~DynamicArray() {
delete[] data;
}
void resize() {
capacity *= 2;
Bomb* newData = new Bomb[capacity];
memcpy(newData, data, current_size * sizeof(Bomb));
delete[] data;
data = newData;
}
void push_back(Bomb element) {
if (current_size == capacity) {
resize();
}
data[current_size++] = element;
}
Bomb pop_back() {
if (current_size == 0) {
cout << "Error: cannot pop from empty array. | Error: array is empty" << endl;
return Bomb{};
}
Bomb element = data[current_size--];
return element;
}
Bomb get(int n) {
if (n < 0 || n >= current_size) {
cout << "Error: index out of bounds|range." << endl;
return Bomb{};
}
return data[n];
}
int size() {
return current_size;
}
void print() {
for (int i = 0; i < current_size; i++) {
cout << "Bomb " << i << ": weight=" << data[i].weight << ", color=" << data[i].color << ", tnt=" << data[i].tnt << endl;
}
}
void clear() {
delete[] data;
capacity = 1;
current_size = 0;
data = new Bomb[capacity];
}
void push_front(Bomb element) {
if (current_size == capacity) {
resize();
}
for (int i = current_size; i > 0; i--) {
data[i] = data[i - 1];
}
data[0] = element;
current_size++;
}
Bomb pop_front() {
if (current_size == 0) {
cout << "Error: cannot pop from empty array." << endl;
return Bomb{};
}
Bomb element = data[0];
for (int i = 0; i < current_size - 1; i++) {
data[i] = data[i + 1];
}
current_size--;
return element;
}
};
struct Node {
Bomb value;
Node* nextElement;
};
struct LinkedList {
Node* head;
Node* tail;
int count;
LinkedList() {
head = nullptr;
tail = nullptr;
count = 0;
}
~LinkedList() {
clear();
}
void push_front(Bomb newBomb) {
Node* newNode = new Node();
newNode->value = newBomb;
newNode->nextElement = head;
head = newNode;
if (tail == nullptr) {
tail = head;
}
count++;
}
void push_back(Bomb newBomb) {
Node* newNode = new Node();
newNode->value = newBomb;
newNode->nextElement = nullptr;
if (tail == nullptr) {
head = newNode;
}
else {
tail->nextElement = newNode;
}
tail = newNode;
count++;
}
Bomb get(int n) {
if (n < 0 || n >= count) {
cout << "Index out of range" << endl;
}
Node* currentNode = head;
for (int i = 0; i < n; i++) {
currentNode = currentNode->nextElement;
}
return currentNode->value;
}
Bomb pop_front() {
if (head == nullptr) {
cout << "List is empty" << endl;
}
Node* oldHead = head;
Bomb data = oldHead->value;
head = oldHead->nextElement;
if (head == nullptr) {
tail = nullptr;
}
delete oldHead;
count--;
return data;
}
Bomb pop_back() {
if (tail == nullptr) {
cout << "List is empty" << endl;
}
Node* oldTail = tail;
Bomb data = oldTail->value;
if (head == tail) {
head = nullptr;
tail = nullptr;
}
else {
Node* current = head;
while (current->nextElement != tail) {
current = current->nextElement;
}
current->nextElement = nullptr;
tail = current;
}
delete oldTail;
count--;
return data;
}
int size() {
return count;
}
void print() {
Node* currentNode = head;
while (currentNode != nullptr) {
cout << "weight=" << currentNode->value.weight << ", color=" << currentNode->value.color << ", tnt=" << currentNode->value.tnt << endl;
currentNode = currentNode->nextElement;
}
}
void clear() {
while (head != nullptr) {
Node* oldHead = head;
head = oldHead->nextElement;
delete oldHead;
}
tail = nullptr;
count = 0;
}
};
int main() {
DynamicArray bombsD;
clock_t startTime = clock();
for (int i = 0; i < 50000; i++) {
Bomb b;
b.weight = rand() % 1000;
strcpy_s(b.color, "red");
b.tnt = rand() % 1000;
bombsD.push_back(b);
}
cout << "Time taken to add 50,000 items to the end of DynamicArray: " << (clock() - startTime) / (double)CLOCKS_PER_SEC << " seconds" << endl;
startTime = clock();
for (int i = 0; i < 10000; i++) {
Bomb b;
b.weight = rand() % 1000;
strcpy_s(b.color, "red");
b.tnt = rand() % 1000;
bombsD.push_front(b);
}
cout << "Time taken to add 10,000 items to the beginning of DynamicArray: " << (clock() - startTime) / (double)CLOCKS_PER_SEC << " seconds" << endl;
startTime = clock();
for (int i = 0; i < 20000; i++) {
int n = rand() % bombsD.size();
bombsD.get(n);
}
cout << "Time taken to read 20,000 items at random indexes in DynamicArray: " << (clock() - startTime) / (double)CLOCKS_PER_SEC << " seconds" << endl;
startTime = clock();
for (int i = 0; i < 5000; i++) {
bombsD.pop_front();
}
cout << "Time taken to delete 5,000 items from the beginning of DynamicArray: " << (clock() - startTime) / (double)CLOCKS_PER_SEC << " seconds" << endl;
startTime = clock();
for (int i = 0; i < 5000; i++) {
bombsD.pop_back();
}
cout << "Time taken to delete 5,000 items from the end of DynamicArray: " << (clock() - startTime) / (double)CLOCKS_PER_SEC << " seconds" << endl;
LinkedList bombsL;
startTime = clock();
for (int i = 0; i < 50000; i++) {
Bomb b;
b.weight = rand() % 1000;
strcpy_s(b.color, "red");
b.tnt = rand() % 1000;
bombsL.push_back(b);
}
cout << "Time taken to add 50,000 items to the beginning of LinkedList: " << (clock() - startTime) / (double)CLOCKS_PER_SEC << " seconds" << endl;
startTime = clock();
for (int i = 0; i < 10000; i++) {
Bomb b;
b.weight = rand() % 1000;
strcpy_s(b.color, "red");
b.tnt = rand() % 1000;
bombsL.push_front(b);
}
cout << "Time taken to add 10,000 items to the beginning of LinkedList: " << (clock() - startTime) / (double)CLOCKS_PER_SEC << " seconds" << endl;
startTime = clock();
for (int i = 0; i < 20000; i++) {
int n = rand() % bombsL.size();
bombsL.get(n);
}
cout << "Time taken to read 20,000 items at random indexes in LinkedList: " << (clock() - startTime) / (double)CLOCKS_PER_SEC << " seconds" << endl;
startTime = clock();
for (int i = 0; i < 5000; i++) {
bombsL.pop_front();
}
cout << "Time taken to delete 5,000 items from the beginning of LinkedList: " << (clock() - startTime) / (double)CLOCKS_PER_SEC << " seconds" << endl;
startTime = clock();
for (int i = 0; i < 5000; i++) {
bombsL.pop_back();
}
cout << "Time taken to delete 5,000 items from the end of LinkedList: " << (clock() - startTime) / (double)CLOCKS_PER_SEC << " seconds" << endl;
bombsD.clear();
bombsL.clear();
startTime = clock();
for (int i = 0; i < 50000; i++) {
Bomb b;
b.weight = rand() % 1000;
strcpy_s(b.color, "red");
b.tnt = rand() % 1000;
bombsD.push_back(b);
}
for (int i = 0; i < 10000; i++) {
Bomb b;
b.weight = rand() % 1000;
strcpy_s(b.color, "red");
b.tnt = rand() % 1000;
bombsD.push_front(b);
}
for (int i = 0; i < 20000; i++) {
int n = rand() % bombsD.size();
bombsD.get(n);
}
for (int i = 0; i < 5000; i++) {
bombsD.pop_front();
}
for (int i = 0; i < 5000; i++) {
bombsD.pop_back();
}
for (int i = 0; i < 50000; i++) {
Bomb b;
b.weight = rand() % 1000;
strcpy_s(b.color, "red");
b.tnt = rand() % 1000;
bombsL.push_back(b);
}
for (int i = 0; i < 10000; i++) {
Bomb b;
b.weight = rand() % 1000;
strcpy_s(b.color, "red");
b.tnt = rand() % 1000;
bombsL.push_front(b);
}
for (int i = 0; i < 20000; i++) {
int n = rand() % bombsL.size();
bombsL.get(n);
}
for (int i = 0; i < 5000; i++) {
bombsL.pop_front();
}
for (int i = 0; i < 5000; i++) {
bombsL.pop_back();
}
cout << "Total time of all steps together: " << (clock() - startTime) / (double)CLOCKS_PER_SEC << " seconds" << endl;
return 0;
}
РЕЗУЛЬТАТ:
