|
|
СИАОД. ИКБО-33-21_КоршуновПётр_2.1. Сортировка числового файла с помощью битового массива
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ
«МИРЭА – Российский технологический университет»
РТУ МИРЭА
Отчет по выполнению практического задания № 2.1
Тема: Сортировка числового файла с помощью битового массива
Дисциплина: Структуры и алгоритмы обработки данных
Выполнил студент Коршунов П. А.
группы ИКБО-30-21
Москва 2022
Цель работы: освоить приёмы работы с битовым представлением беззнаковых целых чисел, реализовать эффективный алгоритм внешней сортировки на основе битового массива.
Задание 1.а
Задача: Реализовать пример, проверить правильность результата
Код программы
#include
#include
using namespace std;
int main() {
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
unsigned char x = 255; //8-разрядное двоичное число 11111111
unsigned char maska = 1; //1=00000001 – 8-разрядная маска
x = x & ((maska << 4)); //результат x=239
cout << x << endl;
system("pause");
return 0;
}
Результаты тестирования
Ожидаемый результат не получен, так как тип переменной х является char, при выводе в консоль был получен символ из ASCII таблицы по коду 239.
Задание 1.б
Задача: Реализовать по аналогии с заданием 1.а решение установки 7-го бита числа в 1.
Код программы
#include
#include
using namespace std;
int main() {
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
unsigned int x = 63; //8-разрядное двоичное число 00111111
unsigned int maska = 1; //1=00000001 – 8-разрядная маска
x = x | (maska << 6); //результат x=127
cout << x << endl;
system("pause");
return 0;
}
Результаты тестирования
Ожидаемый результат получен, программа работает согласно поставленной задаче.
Задание 1.с
Задача: Реализовать код листинга 1, объяснить полученный результат.
Код программы
#include
#include
#include
#include
using namespace std;
int main() {
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
unsigned int x = 25; //Объявление переменной типа беззнакового int
const int n = sizeof(int) * 8; //размер int = 4 байта, умножаем на 8 = 32
unsigned maska = (1 << n - 1); //Сдвигаем 1 на 31 разряд влево, получаем число с единицой 31-м нулём
cout << "Начальный вид маски: " << bitset(maska) << endl; //Bitset - массив битов, внутри число из маски
for (int i = 1; i <= n; i++) {
cout << ((x & maska) >> (n - i)); //(x & maska) - поразрядная конъюнкция x и маски, пока единица в маске путем сдвигов не дойдет до 4 разряда (считать справа, с нуля), данная операция будет давать 0
maska = maska >> 1; //Сдвиг маски вправо на 1
}
cout << endl;
system("pause");
return 0;
}
Результаты тестирования
Объяснение: на выходе программы мы получаем число данного выражения ((x & maska) >> (n - i)) в 10-тичном представлении 32 раза. Пока единица в маске путем сдвигов не дойдет до 4 разряда (считать справа, с нуля), данная операция будет давать 0, а затем будет давать результат 1, 1, 0, 0, 1 из-за уменьшения сдвига на единицу с каждой итерацией. Число x = 25 в 2-ном представлении = 11001, когда (x & maska) при логическом И дает одну единицу, получается 1.
Задание 2.а
Задача: Реализуйте вышеприведённый пример с вводом произвольного набора 8-ми чисел (со значениями от 0 до 7) и его сортировкой с помощью битового массива. Проверьте его работу.
Описание алгоритма:
Для реализации сортировки с помощью битового массива, используем 0-вое 8-битное число типа unsigned int, в него мы будем записывать единичные биты, индексы которых будут отображать значение числа в исходном наборе. Для записи битовой последовательности воспользуемся маской (10000000).
В цикле при помощи сдвига вправо, двигаем маску согласно следующему выражению - количество бит минус единица - значение числа в массиве. Таким образом маска будет содержать 1 в нужном нам индексе для битовой последовательности ( Например (8 - 1 - 0) сдвиг маски на 7 вправо = 1, последний бит последовательности, отвечает за наличие нуля в исходной последовательности). При помощи логического ИЛИ записываем единичные биты в 8-разрядной битовой последовательности. Ограничение: числа не должны повторяться
Полученную последовательность нужно считать и сформировать новый массив.
Код программы
#include
#include
#include
#include
using namespace std;
vector bitSort(int *data, int s) {
unsigned int a = 0; //00000000
int n = sizeof(int) * 2;
unsigned mask = (1 << (n - 1)); //Маска, в которой двигается единица для дальнейшей поразрядной дизъюнкции
for (int i = 0; i < s; i++) {
a = a | (mask >> ((n - 1) - data[i])); //Заполняем 00000000 единицами, единица стоит на том месте, номер которого присутствует в исходном массиве
}
vector resultArr;
for (int i = 0; i < n; i++) {
if ((a & (mask >> i)) != 0) {
resultArr.push_back(n - i - 1);
}
}
reverse(resultArr.begin(), resultArr.end());
return resultArr;
}
int main() {
int arr[7] = { 5, 4, 7, 0, 6, 1, 2 };
vector out = bitSort(arr, 7);
for (int n : out) {
cout << n << " ";
}
system("pause");
return 0;
}
Результаты тестирования
Задание 2.б
Задача: Адаптировать задание 2.a для набора из 64-х чисел (со значениями от 0 до 63).
Описание алгоритма:
Требуется изменить тип переменных на long long, чтобы использовать 64-разрядную сетку. Также необходимо добавить функцию заполнения массива неповторяющимися числами в произвольном порядке. Сам алгоритм битовой сортировки изменять не требуется.
Код программы
#include
#include
#include
#include
#include
using namespace std;
void fillArrayWithRandomNumbers(int *arr, int s) {
srand(time(NULL));
for (int i = 0; i < s; i++) {
arr[i] = i;
}
for (int i = 0; i < s; i++) {
swap(arr[i], arr[rand() % s]);
}
}
vector bitSort(int *data, int s) {
unsigned long long a = 0;
int n = sizeof(long long) * 8;
unsigned mask = (1 << (n - 1));
for (int i = 0; i < s; i++) {
a = a | (mask >> ((n - 1) - data[i]));
}
vector resultArr;
for (int i = 0; i < n; i++) {
if ((a & (mask >> i)) != 0) {
resultArr.push_back(n - i - 1);
}
}
reverse(resultArr.begin(), resultArr.end());
return resultArr;
}
int main() {
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
int arr[64];
fillArrayWithRandomNumbers(arr, 64);
cout << "Исходный массив: \n";
for (int n : arr) { cout << n << " "; }
cout << endl << "Отсортированный массив: \n";
vector out = bitSort(arr, 64);
for (int n : out) {
cout << n << " ";
}
system("pause");
return 0;
}
Результаты тестирования
Массив отсортирован по возрастанию
Задание 2.в
Задача: Исправьте программу задания 2.б, чтобы использовалось не одно число типа unsigned long long, а линейный массив чисел типа unsigned char
Описание алгоритма:
Чтобы не использовать одно число unsigned long long, можно использовать класс bitset, он поддерживает такие же операции над битами, как и переменные => алгоритм сортировки менять не придется. Так же можно увеличить количество сортируемых чисел. Bitset задается при помощи константы, поэтому зададим размер 256 (по заданию требуется использовать числа типа unsigned char, диапазон значений которых 0-255)
Код программы
#include
#include
#include
#include
#include
#include
using namespace std;
void fillArrayWithRandomNumbers(int *arr, int s) {
srand(time(NULL));
for (int i = 0; i < s; i++) {
arr[i] = i;
}
for (int i = 0; i < s; i++) {
swap(arr[i], arr[rand() % s]);
}
}
vector bitSort(int *data, int s) {
bitset<256> a = 0;
int n = sizeof(long long) * 32;
bitset<256> mask;
mask[255] = 1;
for (int i = 0; i < s; i++) {
a = a | (mask >> ((n - 1) - data[i]));
}
vector resultArr;
for (int i = 0; i < n; i++) {
if ((a & (mask >> i)) != 0) {
resultArr.push_back(n - i - 1);
}
}
reverse(resultArr.begin(), resultArr.end());
return resultArr;
}
int main() {
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
int arr[256];
fillArrayWithRandomNumbers(arr, 256);
cout << "Исходный массив: \n";
for (int n : arr) { cout << n << " "; }
cout << endl << "Отсортированный массив: \n";
vector out = bitSort(arr, 256);
for (int n : out) {
cout << n << " ";
}
system("pause");
return 0;
}
Результаты тестирования
Массив отсортирован по возрастанию
Задание 3
Формулировка задачи:
Входные данные: файл, содержащий не более n=10^7 целых положительных чисел, каждое из которых – семизначное число в диапазоне [1000000…9999999], среди них нет повторяющихся.
Результат: упорядоченный по возрастанию список чисел в выходном файле
Время работы программы:
10 с ( до 1 минуты при малых вычислительных мощностях).
Размер входных данных гарантированно превысит 1МБ – допустимый объем стека, используемого для статических массивов. Требование по времени накладывает ограничение на количество чтений исходного файла. Требование 7-значности чисел в исходном файле необязательно, но оно может упростить код для чтения из файла
Задание 3 a и б.
Задача: Реализовать выше поставленную задачу сортировки числового файла. Добавьте в код возможность определения времени работы программы и объема оперативной памяти, занимаемого битовым массивом.
Описание алгоритма
Необходимо создать файл, содержащий не более n=10^7 целых неповторяющихся положительных чисел, каждое из которых – семизначное число в диапазоне [1000000…9999999]. Для этого можно воспользоваться классом vector, в который нужно записать последовательно все числа из данного диапазона.
Реализация: битовая сортировка. Для этого создадим вектор типа unsigned char размерностью 1 250 000, в данный вектор мы можем поместить все значения 10^7 (значения unsigned char от 0 до 255). При считывании файла исходное число делим целочисленно на 8 – получаем индекс в векторе, в данный индекс при помощи маски записываем необходимое значение, (он будет определятся сдвигом маски влево на остаток от деления самого числа). Так мы запишем все возможные числа в один вектор. Для получения выходного результата следует считывать каждый элемент класса vector, и дополнительно просматривать каждый бит, полученного элемента. Если в бите есть 1, то необходимо записать число в новый файл (отсортированный). Чтобы записать полученное число нужно восстановить его исходное значение (индекс умноженный на 8 и добавить значение переменной второго цикла), переменная второго цикла равна биту в который записана 1.
Встроенные методы класса vector shrink_to_fit() и capacity() позволяют узнать количество занимаемых байт массивом.
Код программы
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int main() {
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
unsigned char mask = 1;
int start = clock();
ifstream file;
ofstream out;
file.open("file.txt");
out.open("out.txt");
vector data;
for (int i = 0; i < 10000000 / 8; i++) {
data.push_back(0);
}
int n;
while (file >> n) {
data[n / 8] = data[n / 8] | (mask << (n % 8));
}
for (int i = 0; i < 10000000 / 8; i++) {
for (int j = 0; j < 8; j++) {
n = (data[i] & mask) >> j;
if (n == 1) {
out << 8 * i + j << " ";
}
mask = mask << 1;
}
mask = 1;
}
int stop = clock();
int resTime = stop - start;
data.shrink_to_fit();
cout << data.capacity() << " Байт" << endl;
cout << data.capacity() / 1024 << " КБ" << endl;
cout << data.capacity() / (1024 * 1024) << " МБ" << endl;
cout << "Time: " << resTime << " ms \n";
system("pause");
return 0;
}
Результаты тестирования
 
ВЫВОДЫ
В результате выполнения данной работы поставленные задачи были выполнены. Был изучен алгоритмы битовой сортировки, так же были приобретены навыки её реализации на примерах с разным количеством сортируемых чисел. |
|
|
Скачать 389.16 Kb.