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

Question

[floppa322]

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

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

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

Хотя с другой стороны, если union'ов много, то рано или поздно структура выродится в ежа и тогда вариант с наивной реализацией будет лучше

Answer 1

[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 от Тарьяна - лучше всех других структур на практике.

Comments

[floppa322]

DSU выполняет две операции: проверить, принадлежат ли 2 элемента одному множеству; объеденить множества двух данных элементов. Обе за O(log*n) ассимтотически. Это не логарифм, а суперлогарифм, или обратная функция Аккермана. Это - сколько нужно двоек сложить в степенную башню, чтобы набрать n. Она растет так медленно, что ее можно считать константой на практике (она достигнет 4 только при n=2^65536 - вы столько числел не сохраните во всех датацентрах мира).

я в "n^2 * A()" под A() и имел в виду обр. аккермана

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

те реализации, которые я видел, на вики, например, обычно не имели списка всех элементов одного множества, вот, например, та, которую для leetcode/codeforces использую DisjointSetUnion

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

если по какой-то причине не удалось сжать координаты (id элементов множеств), то придётся хеш таблицы использовать, а не плотные массивы

собственно я и задал вопрос, потому что ради интереса, посмотрев решения литкода на некоторые задачи, тегированные как union-find, люди зачем-то использовали disjoint set, там где можно было обойтись обычным dfs'ом, и на этой почве как раз и возник вопрос :)
вот ещё пример, большинство решений через disjoint set, но непонятно зачем, если можно сделать, например, так

[floppa322]

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

ну и я подчеркнул, если объекдинения вида: проход dfs'ом по каждому элементу и добавление в текущее множество ровно по одному элементу, то от disjoint set'а одно название, а вот как раз обоснованное применение его видится (с ранговой эвристикой и сжатием путей), как раз когда не по одному элементу добавляется, а когда часто вызывается union() у множеств внушительных размеров, а также часто вызывается makeSet(x), то есть исходный размер всех элементов тоже растёт

[Wataru]

floppa322,

те реализации, которые я видел, на вики, например, обычно не имели списка всех элементов одного множества, вот, например, та, которую для leetcode/codeforces использую DisjointSetUnion

Ну так это у вас DSU тарьяна и есть. Вы же процитировали описание "тривиальной" альтернативы. Список элементов в множестве нужен будет для перекраски, чтобы не проходиться по всем n элементам, а только по элементам множества. Иначе объединение будет O(n) а не O(log n) и DSU окажется еще лучше.

если по какой-то причине не удалось сжать координаты (id элементов множеств), то придётся хеш таблицы использовать, а не плотные массивы

Ну да, вместо массивов будут хешмапы. Но тогда и в DSU будет хешмап.

люди зачем-то использовали disjoint set, там где можно было обойтись обычным dfs'ом, и на этой почве как раз и возник вопрос :)

Я бы в этой задаче тоже dfs использовал. Но, может, кому-то dsu первым в голову придет. Кому-то dsu может показаться проще dfs. Проще писать, проще осмыслить, короче код.

[floppa322]

Ну так это у вас DSU тарьяна и есть. Вы же процитировали описание "тривиальной" альтернативы. Список элементов в множестве нужен будет для перекраски, чтобы не проходиться по всем n элементам, а только по элементам множества. Иначе объединение будет O(n) а не O(log n) и DSU окажется еще лучше.

да точно, я просто в голове держал задачи, где можно было просто запомнить список "текущего" множества, чтобы за n не проходится по массиву, это как раз те задачи, которые dfs'ом решаются

Я бы в этой задаче тоже dfs использовал. Но, может, кому-то dsu первым в голову придет. Кому-то dsu может показаться проще dfs. Проще писать, проще осмыслить, короче код.

лично в моём понимании как раз dsu и должен давать ощутимый выигрыш, когда прилетают рандомные union'ы и добавляются новые элементы через makeSet :)

[Wataru]

floppa322,

лично в моём понимании как раз dsu и должен давать ощутимый выигрыш, когда прилетают рандомные union'ы и добавляются новые элементы через makeSet :)

Ну, такой паттерн dfs-ом сделать сложно. Только если все union'ы заранее известны. И там эти два подхода не различимы по скорости, в общем-то. Кому что нравится. А если заранее все неизвестно, и надо именно по одному union делать, то DSU - лучше всего.

[floppa322]

в общем, спасибо за ответ )
вроде примерно устаканилось в голове )

[floppa322]

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

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

вынесу этот коммент наружу топика, чтобы если кому понадобилось - сразу увидел

Answer 2

[floppa322]

Оффтоп

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

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

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

Вот ещё причину нашёл