Disjoint-set

Краткое описание семестрового проекта.

Disjoint-set (система непересекающихся множеств) также называется Union-find. Представляет из себя множество элементов, разбитое на непересекающиеся подмножества, которые в представленной реализации являются деревьями. При этом каждому подмножеству назначается его представитель — элемент этого подмножества (корень дерева). Структура данных определяется множеством трёх операций: Union, Find, make_set. Find(x) возвращает представителя подмножества, в котором находится x. Union(x, y) объединяет множество, к которому принадлежит x, и множество, к которому принадлежит y. Применяется для хранения компонент связности в графах, в частности, алгоритму Краскала необходима подобная структура данных для эффективной реализации.

Есть много вариантов реализации структуры данных.

Команда "ZAG"

Фамилия Имя	Вклад (%)	Прозвище
Касимов Дамир	100

Девиз команды

Наши цели ясны. Задачи определены. За работу, товарищи!

Структура проекта

Описание основных частей семестрового проекта.

Проект состоит из следующих частей:

• src/include - реализация структуры данных (исходный код и заголовочные файлы);
• benchmark - контрольные тесты производительности структуры данных;
• examples - примеры работы со структурой данных;
• dataset - наборы данных для запуска контрольных тестов и их генерация;

Требования (Prerequisites)

В этом разделе задаются основые требования к программному и аппаратному обеспечению для успешной работы с проектом.

Пример. Рекомендуемые требования:

1. С++ компилятор c поддержкой стандарта C++17 (например, GNU GCC 8.1.x и выше).
2. Система автоматизации сборки CMake (версия 3.12.x и выше).
3. Интерпретатор Python (версия 3.7.x и выше).
4. Рекомендуемый объем оперативной памяти - не менее 6 ГБ.
5. Свободное дисковое пространство объемом ~ 3 ГБ (набор данных для контрольных тестов).

Сборка и запуск

Инструкция по сборке проекта, генерации тестовых данных, запуска контрольных тестов и примеров работы.

Пример (Windows)

Сборка проекта

Склонируйте проект к себе на устройство через Git for Windows (либо используйте возможности IDE):

git clone https://github.com/Algorithms-and-Data-Structures-2021/semester-work-disjoint-set-03

Для ручной сборки проекта в терминале введите:

# переход в папку с проектом
cd C:\Users\username\asd-projects\semester-work-disjoint-set-03

# создание папки для файлов сборки (чтобы не засорять папку с проектом) 
mkdir -p build && cd build 

# сборка проекта
cmake .. -DCMAKE_BUILD_TYPE=RelWithDebInfo && cmake --config RelWithDebInfo --build . 

Генерация тестовых данных

Генерация тестового набора данных в формате comma-separated values (CSV):

# переход в папку генерации набора данных
cd dataset

# запуск Python-скрипта
python generate_csv_bench_dataset_join.py --datasets 10 --samples 100

Создаст 10 наборов данных по 100 элементов.

• --samples - количество генерируемых элементов;
• --datasets - количество генерируемых наборов данных;

Тестовые данные представляют собой последовательность объединений, которые создадут струтуру данных из дефолтной структуры (100 элементов, каждый в своем сете).

Тестовые данные представлены в CSV формате (см. dataset/data/dataset-example.csv):

num1, num2
0, 1
1, 5
...

Данные организованы в директориях:

dataset/data/
  join/
    01/
      100.csv
      ...
      5000000.csv
    02/ ...
    03/ ...
    ...
    10/ ...
  ...

Директории с названиями 01, 02 и т.д. означают набор данных. Названия файлов 100.csv, 5000000.csv и т.д. хранят информацию о размере набора данных (т.е. количество элементов).

Контрольные тесты (benchmarks)

Для запуска контрольных тестов необходимо предварительно сгенерировать или скачать готовый набор тестовых данных. Из архива нужно будет достать папку join и заменить ею уже существующую папку в dataset/data.

Ссылка на архив с наборами данных

Список контрольных тестов

Название	Описание	Метрики
find_benchmark	поиск элементов по случайному индексу	время выполнения одного find
find_multiple_benchmark	поиск элементов по случайному индексу	время выполнения нескольких find
join_benchmark	объединение 2 подмножеств по их элементам	время выполнения одного join
join_multiple_benchmark	объединение 2 подмножеств по их элементам	время выполнения нескольких join
make_set_benchmark	добавление подмножества из одного элемента в структуру данных	время выполнения одного make_set
make_set_multiple_benchmark	добавление подмножеств из одного элемента в структуру данных	время выполнения нескольких make_set

Примеры запуска

В IDE выбираете нужный бенчмарк в выпадающем меню в правой верхней части экрана. Затем в том же меню нажимаете на Edit Configurations. В открывшемся окне заполняете Program arguments. Пишите например 100 10 10. Ниже описание аргументов.

Ну а если хотите вручную...

./benchmark num1 num2 num3

• Первый аргумент - количество элементов в структуре данных;
• Второй аргумент - количество наборов данных, на которых проводить тесты;
• Третий аргумент - количество прогонов на наборе данных.

Этот порядок аргументов не для всех бенчмарков. Есть одно исключение - make_set_multiple_benchmark. О нем позже.

Поиск случайного элемента на 10 разных структурах данных размером в 100 элементов (повторить операцию 10 раз на каждом наборе и вычислить среднее время работы одного поиска):

./find_benchmark.exe 100 10 10

Поиск 100 случайных элементов на 10 разных структурах данных размером в 100 элементов (повторить операцию 10 раз на каждом наборе и вычислить среднее время поиска 100 элементов):

./find_multiple_benchmark.exe 100 10 10

Исключение - make_set_multiple_benchmark:

./make_set_multiple_benchmark.exe 100 10

• Первый аргумент - количество элементов в структуре данных, оно же количество вызовов make_set;
• Второй аргумент - количество прогонов;

Источники

Список использованных при реализации структуры данных источников.

• Википедия
• Geeksforgeeks(1)
• Geeksforgeeks(2)