Второе домашнее задание

Потехин Сергей, 156 группа

Структура репозитория

• profiler - самописная утилита для тестирования производительности
• samples - наборы данных для запуска программ
• profiler.first.csv (profiler.second.csv) - таблица с результатами тестирования для первого (второго) пункта
• source.first.cpp (source.second.cpp) - исходники для первого (второго) пункта
• x.first (x.second) - исполняемые файлы для первого (второго) пункта
• plot.first.py (plot.second.py) - скрипт для отрисовки данных из profiler.first.csv (profiler.second.csv)

Первый пункт

Код

Используем vector used_nodes для хранения уже посещенных вершин и vector answer для хранения ребер финального паросочетания. После ввода, будем просто идти по списку ребер и если вершин из этого ребра нет в used, то добавим ребро в answer, а вершины ребра в used. Ответом будет answer.

P.S. В первом и втором пункте ввод реализован через std::cin, для быстрого ввода файла можно использовать

cat data.example | ./x.first

Ассимптотика

Будем считать, что вершин у нас x, а ребер - y. Тогда:

1. Считать x и y O(1)
2. m раз считать ребро и добавить его в vector O(m)
3. Инициализируем вектор использованных вершин O(n)
4. Идем по списку ребер O(m)
5. Проверяем начало и конец ребра на наличие в used_nodes O(1)
6. Добавляем ребро в answer, а вершины в used O(1)

Итог: O(m + n)

Доказательство

Пусть есть паросочетание, найденное нашим алгоритмом (А), и оптимальное паросочетание (Б) - сравним их. Возьмем какое-то ребро из А - оно может либо совпадать с каким-то ребром из Б (неинтересно), либо пересекаться с пересекаться к какими-то ребрами из Б.

1. Ребро может пересечься с одним ребром из Б (a.б)
2. Ребро может пересечься с двумя ребрами из Б (б.а.б)

Заметим, что ребро из А не может пересекаться с тремя и более ребрами из Б, тк тогда в Б присутствуют пересекающиеся ребра, что противоречит определению паросочетания. Следовательно, каждому ребру из А, можно поставить в соответствие максимум два ребра из Б, следовательно - Б больше чем А максимум в два раза.

График зависимости времени работы (Y) от числа ребер (Х) при фиксированном числе вершин

Для графика использовался набор данных, полученных в результате тестирования командой (работает несколько минут, ~5000 тестов). Описание профайлера дано внизу страницы.

$ ./profiler --first True --nodes 100 100 --edges 10 5000

Видно, что за исключением несольких аномальных точек, время работы зависит линейно от числа ребер. График также соответствует найденной ассимптотике.

Второй пункт

Код

Общая идея - пройдем через список всех вершин (= строк). На каждой итерации будем смотреть, были ли мы уже в данной вершине и если нет - это значит, что мы нашли новый кластер. В этом случае увеличиваем число кластеров на 1 и запускаем BFS из этой вершины чтобы найти все оставшиеся вершины этого кластера и пометить их, как использованные.

Реализация - заведем set raws для хранения вершин графа. В нашем случае вершина - это то же самое что строка. Также заведем map used_raws, где для каждой вершины будем отмечать, были ли мы уже в этой вершине. После ввода данных будем итерироваться по raws и смотреть, отмечена ли эта вершина в used_raws, как уже посещенная. Если нет - увеличиваем счетчик кластеров clusters на 1 и запускаем BFS от этой вершины. Внутри BFS мы отмечаем выбранную вершину как посещенную и начинаем искать ее соседей. Согласно условию - ее соседом будет строка, которая отличается от нашей на 1 или 2 символа. Будем искать соседей простым перебором. Будем перебирать все варианты нашей строки, измененной в одной или двух позициях сразу, и, если такая строка существует в raws и еще не посещена - запустим BFS от нее.

Ассимптотика

1. Ввод данных. n строк, операция вставки в set и вставки в map занимает logn - O(n*logn)
2. Итерируемся по raws и проверяем на значение в map (logn)
3. Перебор всех возможных значений новых строк внутри BFS занимает O(m^2) (два вложенных цикла длиной m), генерация новой строки проиходит за O(1)
4. Проверка на вхождение новой строки в set занимает O(m)*O(logn).
5. Следовательно BFS имееет сложность O(m^3 * logn)
6. Максимум можно вызвать BFS n раз (т.к. после каждого вызова вершина будет добавляться в уже использованные).

Следовательно O(nm^3logn)

График зависимости времени работы (Y) от числа строк (X) при фиксированной длине строки

Опять же видно, что найденная ассимптотика подходит под график.

Профайлинг

Профайлер написан на Python 2.7, для корректной работы необходимо установить несколько библиотек.

$ sudo pip install pandas termcolor
$ ./profiler --help
usage: profiler [-h] [--first FIRST] [--second SECOND]
                [--nodes NODES [NODES ...]] [--edges EDGES [EDGES ...]]
                [--raws RAWS [RAWS ...]] [--lenght LENGHT [LENGHT ...]]

Profiler for HW, part 2. Profiler works good right out of the box, so just
type "./profiler --first True -- second True"

optional arguments:
  -h, --help            		show this help message and exit
  --first FIRST         		Profile first problem; default = False
  --second SECOND       		Profile second problem; default = False
  --nodes NODES [NODES ...]		Nodes range for the first problem; default = 10 15
  --edges EDGES [EDGES ...]		Edges range for the first problem; default = 20 25
  --raws RAWS [RAWS ...]		Number of raws range for the second problem; default = 100 110
  --lenght LENGHT [LENGHT ...]	Raw's lenght for the second problem; default = 10 15

В принципе все неплохо работает на дефолтных настройках, достаточно запустить

$ ./profiler --first True --second True

Но при желании можно изменить параметры, в --help все достаточно подробно описано. Отчеты в репозитории созданы командой (работает долго, 1600 и 2000 тестов соответственно)

$ ./profiler --first True --second True --nodes 10 30 --edges 20 100 --raws 100 300 --lenght 10 20