Disjoint-set

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

• Реализуется структура данных под названием система непересекающихся множеств (en. disjoint-set)
• Представляет из себя систему непересекающихся деревьев
• Приложения структуры данных:
  • Поддержание компонент связности графа
  • Построение остова минимального веса
  • Сегментирование изображений
  • Генерация лабиринтов
• Структура данных определяется множеством трёх операций: {Union, Find, MakeSet}
• Теоретическая сложность операций:
  • Создание множества (MakeSet) за O(1)
  • Нахождение множества, которому принажлежит элемент (Find) за O(α(n)), где α(n) - функция, обратная функции Аккермана
  • Объединение двух множеств (Union) за O(α(n))

Команда "DeadInside"

Группа: 11-104

Фамилия Имя	Вклад (%)	Прозвище
Зорин Виталий	100	главный суетолог

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

Мой девиз - всего три слова: питонистом быть прикольно!

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

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

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

Требования

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

1. Интерпретатор Python (версия 3.7.x и выше).
2. Рекомендуемый объем оперативной памяти - не менее 4 ГБ.
3. Свободное дисковое пространство объемом ~ 1 ГБ (для входного набора данных).

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

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

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

git clone https://github.com/Addefan/semester-project-disjoint-set.git

Сборка и запуск проекта осуществляется через среду разработки.

Видео-инструкция по сборке проекта

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

Формат данных: comma-seperated values (CSV).

Инструкции по генерации:

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

# запуск Python-скрипта
python generate_csv_dataset.py <output> --samples 100

• <output> - выходной файл;
• --samples - количество генерируемых элементов

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

6700657
9436641
8555103
...

По названию директории /dataset/data/make можно понять, что здесь хранятся наборы данных для контрольных тестов по соданию одноэлементного множества в структуре данных. Названия файлов 100.csv. 5000000.csv и т.д. хранят информацию о размере набора данных (т.е. количество элементов).

Генерация CSV-файла со ста элементами:

cd dataset
python generate_csv_dataset.py data/make/01/100.csv --samples 100

где <output> = data/make/01/100.csv

Видео-инструкция по генерации данных

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

Для запуска контрольных тестов необходимо предварительно сгенерировать или скачать готовый набор тестовых данных.

Примечание. Скачать готовый набор текстовых данных можно, пройдя по этой ссылке и

• нажав кнопку "СКАЧАТЬ ВСЕ" в правом верхнем углу, если вы не авторизованы в Google
• нажав ПКМ по папке data и далее нажав на кнопку "Скачать", если вы авторизованы в Google

Скачанный архив необходимо разархивировать в dataset

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

Название	Описание	Метрики
make_benchmark	создание одноэлементного множества	время
find_benchmark	поиск "представителя" множества, которому принадледит элемент	время
union_benchmark	объединение двух множеств по двум элементам	время

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

python benchmark/<control-test> <input> <output> --trials 50

• <control-test> - название контрольного теста (например, make_benchmark);
• <input> - входной файл с набором данных в формате CSV;
• <output> - выходной файл с результатами контрольного теста;
• --trials - количество прогонов на наборе данных

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

python benchmark/make_benchmark.py dataset/data/make/01/100.csv benchmark/metrics.txt --trials 10

где <input> = dataset/data/make/01/100.csv и <output> = benchmark/metrics.txt

Видео-инструкция по запуску контрольных тестов

Источники

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

• Статья на Википедии (en)
• Статья на Википедии (ru)
• Статья на Хабре
• Серия видео на YouTube от канала "Контур Студент"
• Статья с сайта MAXimal
• Статья с сайта Techie Delight

Это не плагиат, это уважение чужого труда и помощь своим сокурсникам более подробно разобраться в теме.