Комментарии 21
Ваша третья задача, про расселение - это задача о максимальном паросочетании в произвольном графе. После того, как вы провели ребро между двумя вершинами, если два человека взаимно согласны селиться вместе, то вам осталось взять максимальное число ребре так, чтобы никакие два ребра не были инцидентны одной и той же вершине. Для этой задачи есть классический алгоритм "сжатия соцветий", работающий за O(n^3). Этот алгоритм реализован в том же networkx: max_weight_matching.
Правда, обычно, когда говорят о паросочетаниях, говорят о задаче на двудольных графах, потому что там алгоритм сильно проще и поэтому ее чаще проходят и она более известна. Ваш случай чуть более продвинутый.
Задача о максимальном независимом множестве, к которой вы свели вашу задачу - NP-полная и решение в итоге работает, скорее всего, сильно медленнее. Хотя для практического применения этого более чем достаточно.
Потом, можно задачу еще лучше решить. Можно же считать еще и частично удовлетворенные пожелания. Если вы поселили вместе двух людей, один из которых хочет жить с другим, то это лучше, чем когда они оба друг-друга недолюбливают. Поэтому можно назначить "парным" ребрам какой-то большой вес, а вот таким "половинчатым" - какой-то сильно меньший. Потом эта же функция max_weight_matching умеет считать паросочетание максимального суммарного веса.
Его Сиятельство.
Union-find для первой задачи проще всяких обходов графов.
Да, вы правы, но эта структура данных делает тоже самое, что и обход графа. Ее и придумали для решения всяких задач на графах. Так что граф тут никуда не делся.
Я про эффективность, а не про то, как это можно интерпретировать. Не надо строить в памяти явное представление графа, без которого вы не вызовете внешнюю библиотеку. А если вы граф делаете неявным, то всё равно код получится более громоздким, нежеле union-find.
Мне ближе подход через графы, т.к. он более универсальный, решает целый комплекс задач. Ну а обходы мы же не вручную делаем, всё за нас делает networkx, а мы только пишем питоновский glue).
А как мы выглядел Unioin-find в python для данной задачке? я сходу не нашел в гугле
Но зато надо построить в памяти Union find стурктуру и перебрать все те же ребра (а значит ребра в памяти уже должны быть!). Плюс, время работы будет O(n log*n) вместо O(n), так что это еще спорный вопрос, что будет эффективнее, Dfs или union-find.
С другой стороны, вы правы, кода для union-find (особенно, если не использовать ранговую эвристику) обычно сильно меньше, но тут же обход из популярной библиотеки вызвается, а union-find еще найти надо или написать самому.
Накладные расходы на union-find - это один массив целых чисел размером в количество столбцов. Да, ранговая эвристика не нужна, нужно делать рандомизированное слияние. Перебирать рёбра надо, но хранить их в памяти не надо, просто вместо создания ребра нужно делать union.
Поэтому расходы на память изрядно ниже, нежели с графовым подходом. А временная сложность та же, линейная. Количество столбцов не превысит количества атомов в наблюдаемой вселенной, а log*(10^80) = 5. То есть, опять O(n), причём временная константа в этом самом O очень небольшая.
Кода будет в десять строчек максимум, даже если писать самому с нуля.
Перебирать рёбра надо, но хранить их в памяти не надо, просто вместо создания ребра нужно делать union.
Ну как вы их переберете, если вы их в памяти не храните? В каком-то виде они вам все-равно понадобятся. Правда, можно их стримить из файла. Вы это имели ввиду?
А временная сложность та же, линейная
Ну, тут вы слишком фривольно обращаетесь с нотацией. Да, этот O(N log* N) возможно даже быстрее O(N) для DFS на любых физически возможных данных. Но сложность тут не становится от этого линейной.
На основе входных данных автор создаёт набор рёбер. Я предлагаю сделать ту же процедуру, но вместо создания каждого конкретного ребра сделать union(u,v). Перебор есть, хранения рёбер нет.
Про сложность - я, конечно, окончил отделение чистой математики, но меня интересуют прикладные вопросы, поэтому варианты при n, превышающим количество атомов в обозримой вселенной меня не интересуют. Фривольности от этого не появляется, появляется лишь ограничение n < 10^80.
Дерево вызовов функций в дизассемблере это граф, и анализ такого графа очень сильно помогал в разборе и модификации чужих приложений
Поскольку простой граф – это всего лишь бинарное отношение на множестве, то графы, действительно, вездесущи.
В задаче 1 рассматривается отношение эквивалентности на множестве столбцов таблицы. В каждом классе эквивалентности надо оставить столбец с минимальным ключом, а остальные - удалить.
Человеческая прямая логика здесь очень проста: если эквивалентны столбцы A и B, а также A и C, то сравнивать столбцы B и C – напрасная потеря времени, эти столбцы тоже эквивалентны. Если класс эквивалентности большой, то потеря времени может быть существенной.
Поэтому никакой граф здесь не нужен. Как только найдена пара эквивалентных столбцов, так сразу столбец с большим ключом надо удалить (или пометить как удалённый), чтобы больше он в сравнениях не участвовал.
В целом да, согласен. Ваш алгоритм более оптимальный. Правда, сходу, я не могу представить как его на python реализовать, чтобы было коротко и понятно...
Количество столбцов у таблице нечасто бывает более 300, поэтому оптимизацию я тут на второе место поставил. Граф использован, скорее, как удобная абстракция, которая скрывает от нас циклы.
Есть кстати одно место в моей библиотеки, где критически важно реализовать его супер оптимально, возможно даже на C++/C. Это поиск потенциальных ключей. Сейчас я это сделал как простой перебор комбинаций не более соответствующей длины (например, не более пяти). Но видимо, это не самый оптимальный алгоритм. Есть некоторые работы, но сложновато показалось (ссылка).
Да не, @BorodaMhogogreshnaya описал нерабочий алгоритм. Пример: у нас эквивалентные ключи A=B, B=C. Из-за первого равенства удаляем столбец B. Второе равенство уже ничего не делает, ведь столбца B нету, и не удаяет C.
Если же у вас отношение уже транзитивно замкнуто, то алгоритм будет работать, но вряд ли у вас такой случай, ибо, если надо руками задавать эквивалентность для всех пар, то можно сразу же и все ненужное руками же и отбросить.
@wataru
Про алгоритм. Если мы удаляем B. То у нас остается два столбца, A и C, они тоже один-к-одному (для один-к-одному выполняется правило: A=B, B=C => A=C). Т.е. когда-то мы пару А, С найдем и удалим один из них. Т.е. по мне алгоритм верный. И он делает меньше операций теоретически. Но вот написать сходу я его не могу в Python, не очевидный подход...
А, так у вас оно уже транзитивно замкнуто. Тогда, да, алгоритм работает. Правда, сильно много он не насокращает, если классы эквивалентности не большие.
Будет он чем-то вроде двух циклов:
removed = [False] * n
canonical = [-1] * n
for i in range(0, n):
if removed[i]: continue
canonical[i] = i
for j in range(i+1, n):
if IsEquivalent(i, j):
removed[j] = True;
canonical[j] = i;В конце удаленные столбцы помечены в removed и у каждого столбца в canonical будет номер представителя класса.
Моя реплика была не о том, что можно что-то ускорить, а о том, что не надо усложнять на ровном месте. Никакие графы в этой задаче не нужны.
Код понял, логичный. В целом canonical переменная не нужна даже. Можно и так было, наверное даже логичнее.
Просто подход с графами мне интуитивно чуть понятнее, естественнее
я не уверен, что в python такой цикл будет быстрее (я только на python пишу). networkx вроде на плюсах написан, так что по скорости может и выиграть у двойного цикла питона
А сама идея понятна, алгоритмическая сложность у вашего алгоритма лучше, конечно
Нет. Алгоритмическая сложность одинакова O(n^2), что у обхода, что о у этих двух циклов. Два цикла будут в 2 раза быстрее за счет рассмотрения ребер только в одну сторону. И на больших классах эквивалентности - еще быстрее из-за пропусков лишних. Но в худшем случае ассимптотика та же самая. Если же граф не транзитивно замкнут, т.е. у вас заданы не все эквивалентные пары, а лишь основные, то обход графа будет быстрее.
Публикации
Его величество Граф