GCC Code Coverage Report

Line	Branch	Exec	Source
1			#include "gonozov_l_bitwise_sorting_double_Batcher_merge/omp/include/ops_omp.hpp"
2
3			#include <algorithm>
4			#include <cmath>
5			#include <cstddef>
6			#include <cstdint>
7			#include <cstring>
8			#include <limits>
9			#include <vector>
10
11			#include "gonozov_l_bitwise_sorting_double_Batcher_merge/common/include/common.hpp"
12
13			namespace gonozov_l_bitwise_sorting_double_batcher_merge {
14
15		✗	GonozovLBitSortBatcherMergeOMP::GonozovLBitSortBatcherMergeOMP(const InType &in) {
16			SetTypeOfTask(GetStaticTypeOfTask());
17		✗	GetInput() = in;
18		✗	}
19
20		✗	bool GonozovLBitSortBatcherMergeOMP::ValidationImpl() {
21		✗	return !GetInput().empty(); // проверка на то, что исходный массив непустой
22			}
23
24		✗	bool GonozovLBitSortBatcherMergeOMP::PreProcessingImpl() {
25		✗	return true;
26			}
27
28			namespace {
29			/// double -> uint64_t
30			uint64_t DoubleToSortableInt(double d) {
31			uint64_t bits = 0;
32			std::memcpy(&bits, &d, sizeof(double));
33		✗	if ((bits >> 63) != 0) { // Отрицательное число
34		✗	return ~bits; // Инвертируем все биты
35			} // Положительное число или ноль
36		✗	return bits | 0x8000000000000000ULL;
37			}
38
39			// uint64_t -> double
40			double SortableIntToDouble(uint64_t bits) {
41		✗	if ((bits >> 63) != 0) { // Если старший бит установлен (было положительное)
42		✗	bits &= ~0x8000000000000000ULL; // Убираем старший бит
43			} else { // Если старший бит не установлен (было отрицательное число)
44		✗	bits = ~bits; // Инвертируем все биты обратно
45			}
46
47			double result = 0.0;
48			std::memcpy(&result, &bits, sizeof(double));
49			return result;
50			}
51
52		✗	void RadixSortDouble(std::vector<double> &data) {
53		✗	if (data.empty()) {
54		✗	return;
55			}
56
57			// Преобразуем в сортируемые целые числа
58		✗	std::vector<uint64_t> keys(data.size());
59		✗	for (size_t i = 0; i < data.size(); ++i) {
60		✗	keys[i] = DoubleToSortableInt(data[i]);
61			}
62
63			const int radix = 256; // 8 бит за проход
64		✗	std::vector<uint64_t> temp_keys(data.size());
65
66			// 8 проходов для 64-битных чисел (8 байт)
67		✗	for (int pass = 0; pass < 8; ++pass) {
68		✗	std::vector<size_t> count(radix, 0);
69		✗	int shift = pass * 8;
70			// Подсчет
71		✗	for (uint64_t key : keys) {
72		✗	uint8_t byte = (key >> shift) & 0xFF;
73		✗	count[byte]++;
74			}
75
76			// Накопление
77		✗	for (int i = 1; i < radix; ++i) {
78		✗	count[i] += count[i - 1];
79			}
80
81			// Распределение
82		✗	for (int i = static_cast<int>(keys.size()) - 1; i >= 0; --i) {
83		✗	uint8_t byte = (keys[i] >> shift) & 0xFF;
84		✗	temp_keys[--count[byte]] = keys[i];
85			}
86			keys.swap(temp_keys);
87			}
88
89			// Преобразуем обратно
90		✗	for (size_t i = 0; i < data.size(); ++i) {
91		✗	data[i] = SortableIntToDouble(keys[i]);
92			}
93			}
94
95		✗	void MergingHalves(std::vector<double> &arr, size_t i, size_t len) { // слияние половинок
96		✗	size_t half = len / 2;
97		✗	size_t end = std::min(i + len, arr.size());
98
99		✗	for (size_t step = half; step > 0; step /= 2) {
100		✗	for (size_t j = i; j + step < end; ++j) {
101		✗	if (arr[j] > arr[j + step]) {
102			std::swap(arr[j], arr[j + step]);
103			}
104			}
105			}
106		✗	}
107
108		✗	void BatcherOddEvenMergeIterative(std::vector<double> &arr, size_t n) {
109		✗	if (n <= 1) {
110			return;
111			}
112		✗	n = std::min(n, arr.size());
113			// Сначала сливаем блоки размером 1, потом 2, потом 4 и т.д.
114		✗	for (size_t len = 2; len <= n; len *= 2) {
115		✗	#pragma omp parallel for default(none) shared(arr, n, len)
116			for (size_t i = 0; i < n; i += len) {
117			MergingHalves(arr, i, len);
118			}
119			}
120			}
121
122			// Нахождение ближайшей степени двойки, большей или равной n
123			size_t NextPowerOfTwo(size_t n) {
124			size_t power = 1;
125		✗	while (power < n) {
126		✗	power <<= 1;
127			}
128			return power;
129			}
130
131		✗	void HybridSortDouble(std::vector<double> &data) {
132		✗	if (data.size() <= 1) {
133		✗	return;
134			}
135
136			size_t original_size = data.size();
137
138			size_t new_size = NextPowerOfTwo(original_size);
139		✗	data.resize(new_size, std::numeric_limits<double>::max());
140
141		✗	size_t mid = new_size / 2;
142		✗	std::vector<double> left(data.begin(), data.begin() + static_cast<ptrdiff_t>(mid));
143		✗	std::vector<double> right(data.begin() + static_cast<ptrdiff_t>(mid), data.end());
144
145			// Сортируем каждую половину поразрядно
146		✗	#pragma omp parallel sections default(none) shared(left, right)
147			{
148			#pragma omp section
149			{
150			RadixSortDouble(left);
151			}
152			#pragma omp section
153			{
154			RadixSortDouble(right);
155			}
156			}
157
158			// Собираем обратно в единый массив
159			std::ranges::copy(left, data.begin());
160			std::ranges::copy(right, data.begin() + static_cast<ptrdiff_t>(mid));
161
162			// Используем слияние Бэтчера для слияния двух отсортированных массивов
163		✗	BatcherOddEvenMergeIterative(data, new_size);
164
165			// Обрезаем до исходного размера
166		✗	data.resize(original_size);
167			}
168
169			} // namespace
170
171		✗	bool GonozovLBitSortBatcherMergeOMP::RunImpl() {
172		✗	std::vector<double> array = GetInput();
173		✗	HybridSortDouble(array);
174		✗	GetOutput() = array;
175		✗	return true;
176			}
177
178		✗	bool GonozovLBitSortBatcherMergeOMP::PostProcessingImpl() {
179		✗	return true;
180			}
181
182			} // namespace gonozov_l_bitwise_sorting_double_batcher_merge
183