Lite_stream
@Lite_stream

Когда целесообразно использовать именно такую реализацию DSU?

Когда имеет смысл использовать иерархическую реализацию DSU, где у каждого элемента есть свой родитель, пока он не дойдёт до представителя множества (ссылка на себя), с ранговой эвристикой + сжатием путей, перед тривиальной реализацией DSU на хэш-таблице/массиве, где find() работает за O(1) (обычный вызов contains() в хэш-таблице), а union() за O(n) (здесь можно использовать что-то вроде ранговой эвристики, чтобы при переприсваивании ключей у объекдиняемых множеств, присваивать меньшему по количеству элементов множеству новые set id, используя обычный put(setElem, newSetId))

Например, в задачах вроде такой, всё равно придётся пройтись по каждому элементу и асимтотика у DSU с иерархической структурой будет даже чуть хуже - n^2 * A()

Видимо DSU на иерархической структуре даёт прирост, когда в алгоритме union() объединяет не 1 элемент с остальными, а множества сопоставимых размеров, тогда вроде бы есть смысл в такой организации DSU?

Хотя с другой стороны, если union'ов много, то рано или поздно структура выродится в ежа и тогда вариант с наивной реализацией будет лучше
  • Вопрос задан
  • 92 просмотра
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
DSU выполняет две операции: проверить, принадлежат ли 2 элемента одному множеству; объеденить множества двух данных элементов. Обе за O(log*n) ассимтотически. Это не логарифм, а суперлогарифм, или обратная функция Аккермана. Это - сколько нужно двоек сложить в степенную башню, чтобы набрать n. Она растет так медленно, что ее можно считать константой на практике (она достигнет 4 только при n=2^65536 - вы столько числел не сохраните во всех датацентрах мира).

Я бы в качестве альтернативной, "тривиальной" реализации рассматривал массив пометок + списки в массиве:
для каждого элемента храним номер его множества, а для каждого номера храним список всех его элементов в списках (так же, как и в DSU, в одном массиве ссылок на следующий элемент).

Эта структура компактна по памяти и более быстра, чем ваши хеш таблицы. Тут можно за O(1) проверить, что два числа в одном множестве и за O(log n) объеденить два множества (амортизированно, если перекрашиваем меньшее множество).

Итак, имеем O(Log*n) vs O(1) за проверку и O(log*n) vs O(log n) за объединения.

Т.е. вроде бы имеет смысл использовать пометки+списки, если у вас заметно больше проверок, чем объединений.

Но на практике там выигрыша нет, ибо редко когда у вас сильно больше проверок. Да и, если у вас много проверок, то оценка O(log*n) - завышена, ведь если вы одну и ту же проверку повторяете, то там пути сжимаются и проверки работают уже за O(1).

Таким образом, DSU от Тарьяна - лучше всех других структур на практике.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
Lite_stream
@Lite_stream Автор вопроса
Оффтоп

Вот, кстати, нашёл задачу, где dsu не асимптотически, но быстрее. чем dfs, ну и даже сам код лаконичнее и яснее

Конечно не очень хороший бенчмарк, но leetcode для dsu выдаёт в среднем 150 милисекунд, а для dfs 190 милисекунд, там для dfs, в частности, нужно ещё в список смежности превратить исходный массив, нужна мапа (медленная) для vertex To component, сет для used ну и сам код намного длинее выходит

В общем, dfs не очень работает с матрицей смежности и тем более списком ребёр (как в задаче выше), а только с списком смежности, поэтому если в задаче изначально граф дан не в нужном виде, то лучше использовать dsu, ну и также, чтобы рукам не поддерживать компоненты связности, так как это заложено в dsu. То есть если в ходе работы алгоритма нет чёткой структуры графа, или рёбра вообще появляются налету (находятся по каким-то признакам, а не даны заранее), то как раз через dsu удобно делать unite(from, to) этих рёбер

Вот ещё причину нашёл
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы