СНМ (реализация с помощью леса корневых деревьев) — различия между версиями
(Новая страница: «{{В разработке}} ==Реализация== В ''реализации системы непересекающихся множеств с помощью л…») |
|||
| Строка 1: | Строка 1: | ||
{{В разработке}} | {{В разработке}} | ||
| + | Система непересекающихся множеств. Реализация с помощью леса корневых деревьев. (disjoint set union (DSU) или Union-Find) | ||
| + | |||
==Реализация== | ==Реализация== | ||
| − | + | Каждое множество хранится в виде дерева. Элементы множества хранятся в узлах дерева. У каждого множества есть его представитель - один из элементов этого множества, он хранится в корне дерева. В каждом узле, кроме элемента множества, хранится ссылка на "родителя". | |
| + | |||
| + | При объединении двух множеств, корень одного дерева подвешивается к другому (операция ''union''). Таким образом, чтобы определить, в каком множестве находится элемент достаточно пройтись по ссылкам по дереву вверх до корня (операция ''get''). | ||
| + | |||
| + | Сама по себе такая реализация еще не дает выигрыша в скорости, в сравнении с [[СНМ(наивные_реализации)|наивными реализациями]], так как при неудачном стечении обстоятельств дерево может выродиться в линейный список и get будет работать за линейное время. Сильный выигрыш в скорости даст использование двух эвристик: '''объединение по рангу''' (union by rank) и '''сжатие пути''' (path compression). | ||
| + | |||
| + | ===Объединение по рангу=== | ||
| + | Эта эвристика аналогична [[СНМ(списки_с_весовой_эвристикой)||весовой эвристике у связных списков]]. Идея в том, чтобы при объединении подвешивать дерево с меньшей глубиной к дереву с большей. | ||
| + | |||
| + | Вместо того, чтобы явно хранить высоту дерева, можно хранить его ранг, который по сути является некой верхней границей высоты дерева. У дерева, состоящего ровно из одного элемента ранг равен 1. При объединении дерево с меньшим рангом подвешивается к дереву с большим, и ранг объединенного дерева становится равным большему из этих двух рангов. Если ранги объединяемых деревьев равны, то не важно какое, к какому подвешивать, но ранг объединенного дерева будет больше на 1. | ||
| − | + | ===Сжатие пути=== | |
| + | Эта эвристика несколько модифицирует операцию ''get'' и делает ее двухпроходной. Операция get вызывается для элемента ''x'' (''get(x)''), проходит через несколько вершин и попадает в корень. Все пройденные в этом процессе вершины принадлежат тому же множеству, что и ''x''. Поэтому подвесим их напрямую (изменим ссылки) к корню дерева и, таким образом уменьшим его высоту. | ||
==Асимптотика== | ==Асимптотика== | ||
| Строка 15: | Строка 27: | ||
! m*get + n*union || m*a(m,n) + n | ! m*get + n*union || m*a(m,n) + n | ||
|} | |} | ||
| − | где m - общее количество операций, n - полное количество элементов, a(m, n) - обратная | + | где m - общее количество операций, n - полное количество элементов, a(m, n) - функция, обратная к функции Аккермана - очень медленно растущая функция и практически для всех разумных значений не превышает 4, поэтому ее можно считать константой. Таким образом, при этой реализации время работы линейно зависит от количества операций. |
| − | |||
| − | |||
| − | |||
==Ссылки== | ==Ссылки== | ||
Версия 05:28, 22 марта 2011
Система непересекающихся множеств. Реализация с помощью леса корневых деревьев. (disjoint set union (DSU) или Union-Find)
Содержание
Реализация
Каждое множество хранится в виде дерева. Элементы множества хранятся в узлах дерева. У каждого множества есть его представитель - один из элементов этого множества, он хранится в корне дерева. В каждом узле, кроме элемента множества, хранится ссылка на "родителя".
При объединении двух множеств, корень одного дерева подвешивается к другому (операция union). Таким образом, чтобы определить, в каком множестве находится элемент достаточно пройтись по ссылкам по дереву вверх до корня (операция get).
Сама по себе такая реализация еще не дает выигрыша в скорости, в сравнении с наивными реализациями, так как при неудачном стечении обстоятельств дерево может выродиться в линейный список и get будет работать за линейное время. Сильный выигрыш в скорости даст использование двух эвристик: объединение по рангу (union by rank) и сжатие пути (path compression).
Объединение по рангу
Эта эвристика аналогична |весовой эвристике у связных списков. Идея в том, чтобы при объединении подвешивать дерево с меньшей глубиной к дереву с большей.
Вместо того, чтобы явно хранить высоту дерева, можно хранить его ранг, который по сути является некой верхней границей высоты дерева. У дерева, состоящего ровно из одного элемента ранг равен 1. При объединении дерево с меньшим рангом подвешивается к дереву с большим, и ранг объединенного дерева становится равным большему из этих двух рангов. Если ранги объединяемых деревьев равны, то не важно какое, к какому подвешивать, но ранг объединенного дерева будет больше на 1.
Сжатие пути
Эта эвристика несколько модифицирует операцию get и делает ее двухпроходной. Операция get вызывается для элемента x (get(x)), проходит через несколько вершин и попадает в корень. Все пройденные в этом процессе вершины принадлежат тому же множеству, что и x. Поэтому подвесим их напрямую (изменим ссылки) к корню дерева и, таким образом уменьшим его высоту.
Асимптотика
Реализация системы непересекающихся множеств с помощью леса корневых деревьев дает следующие асимптотически оценки для операций:
| get | a(m,n) |
|---|---|
| union | 1 |
| m*get + n*union | m*a(m,n) + n |
где m - общее количество операций, n - полное количество элементов, a(m, n) - функция, обратная к функции Аккермана - очень медленно растущая функция и практически для всех разумных значений не превышает 4, поэтому ее можно считать константой. Таким образом, при этой реализации время работы линейно зависит от количества операций.
Ссылки
- Система непересекающихся множеств - описание этой реализации на habrahabr.ru
- Функция Аккермана - Википедия
Литература
- Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы. Построение и анализ — Вильямс, 2010. - 1296с. — ISBN 978-5-8459-0857-4, 0-07-013151-1. (стр 589)
