DataStructures-HashTableDictionary/Tester.cpp at master · Czarko-exe/DataStructures-HashTableDictionary · GitHub

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include "Tester.hpp"
#include "HashTable.hpp"
#include "DoubleHashing.hpp"
#include "CuckooHashing.hpp"
#include <iostream>
#include <chrono>
#include <random>
#include <fstream>
#include <filesystem>
#include <vector>
namespace fs = std::filesystem;

std::vector<int> generate_unique_keys(int N, int seed) {	//generowanie unikalnych kluczy (od 1 do 3*N) i ich losowe mieszanie
	std::vector<int> keys(3 * N);
	for (int i = 0; i < 3 * N; i++)
		keys[i] = i + 1;

	std::mt19937 rng(seed);
	std::shuffle(keys.begin(), keys.end(), rng);			//losowe mieszanie kluczy

	keys.resize(N);											//zachowanie tylko N kluczy (reszta jest niepotrzebna)
	return keys;
}

int generate_insert_key(const std::vector<int>& keys, int N, int seed) {	//generowanie klucza do wstawienia
	int maxKey = 3 * N;

	std::vector<bool> used(maxKey + 1, false);								//tablica do oznaczania użytych kluczy

	for (int k : keys)														//oznaczenie kluczy, które są już używane (te, które zostały wygenerowane jako unikalne)
		used[k] = true;

	std::vector<int> free_keys;
	free_keys.reserve(2 * N);												//rezerwacja miejsca na klucze, które są wolne

	for (int i = 1; i <= maxKey; i++)
		if (!used[i])
			free_keys.push_back(i);

	std::mt19937 rng(seed);
	std::uniform_int_distribution<int> dist(0, free_keys.size() - 1);

	return free_keys[dist(rng)];
}


std::vector<int> loadSeeds(const std::string filename) {	//ładowanie seedów z pliku
	std::vector<int> seeds;
	std::ifstream in(filename);
	int s;
	while (in >> s) {
		seeds.push_back(s);
	}
	return seeds;
}

void test_structure(std::string structure, int N, std::string operation) {	//główna funkcja testująca, która wykonuje 10 testów dla danej struktury, operacji, rozmiaru i seeda, mierzy czas i zapisuje wyniki do pliku CSV
	if (!fs::exists("output"))
		fs::create_directory("output");

	if (!fs::exists("output/results.csv")) {
		std::ofstream out("output/results.csv", std::ios::app);
		out << "Struktura; Operacja; Rozmiar; Seed";
		for (int i = 1; i <= 10; ++i) out << ";Time" << i;
		out << "\n";
	}

	std::ofstream out("output/results.csv", std::ios::app);
	std::vector<int> seeds = loadSeeds("seeds.txt");

	for (int seed : seeds) {
		std::vector<int> keys = generate_unique_keys(N, seed);				//generowanie unikalnych kluczy dla danego N i seeda (od 1 do 3*N, losowo mieszane)

		std::mt19937 rng(seed);
		std::uniform_int_distribution<int> dist(0, N - 1);

		long long times[10] = {};

		for (int i = 0; i < 10; ++i) {
			int insert_key = generate_insert_key(keys, N, seed + i);		//generowanie klucza do wstawienia
			int remove_key = keys[dist(rng)];								//klucz do usunięcia

			if (structure == "AVL_Tree") {									//testowanie AVL Tree (wstawianie i usuwanie kluczy w drzewie AVL)
				HashTable avl(101);
				for (int d_idx = 0; d_idx < N; ++d_idx) avl.insert(keys[d_idx], keys[d_idx] * 10);

				std::cout << "Testing " << structure << " with operation " << operation << " for N = " << N << " and seed = " << seed << " (Test " << i + 1 << "/10)" << std::endl;

				long long t = measure_time([&]() {
					if (operation == "insert") avl.insert(insert_key, insert_key * 10);
					else if (operation == "remove") avl.remove(remove_key);
					});

				times[i] = t;
				std::cout << "Time: " << times[i] << " ns" << std::endl;
			}

			else if (structure == "Double_Hashing") {						//testowanie Double Hashing (wstawianie i usuwanie kluczy w tablicy z podwójnym hashowaniem)
				DoubleHashTable doubleHash(101);
				for (int d_idx = 0; d_idx < N; ++d_idx) doubleHash.insert(keys[d_idx], keys[d_idx] * 10);

				std::cout << "Testing " << structure << " with operation " << operation << " for N = " << N << " and seed = " << seed << " (Test " << i + 1 << "/10)" << std::endl;

				long long t = measure_time([&]() {
					if (operation == "insert") doubleHash.insert(insert_key, insert_key * 10);
					else if (operation == "remove") doubleHash.remove(remove_key);
					});

				times[i] = t;
				std::cout << "Time: " << times[i] << " ns" << std::endl;
			}
			else if (structure == "Cuckoo_Hashing") {						//testowanie Cuckoo Hashing (wstawianie i usuwanie kluczy w tablicy z Cuckoo Hashing)
				CuckooHashTable cuckooHash(101);
				for (int d_idx = 0; d_idx < N; ++d_idx) cuckooHash.insert(keys[d_idx], keys[d_idx] * 10);

				std::cout << "Testing " << structure << " with operation " << operation << " for N = " << N << " and seed = " << seed << " (Test " << i + 1 << "/10)" << std::endl;

				long long t = measure_time([&]() {
					if (operation == "insert") cuckooHash.insert(insert_key, insert_key * 10);
					else if (operation == "remove") cuckooHash.remove(remove_key);
					});

				times[i] = t;
				std::cout << "Time: " << times[i] << " ns" << std::endl;
			}
		}

		out << structure << ";" << operation << ";" << N << ";" << seed;
		for (int i = 0; i < 10; ++i) out << ";" << times[i];
		out << "\n";
	}
}