Система непересекающихся множеств: различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [досмотренная версия] |
Daryin (обсуждение | вклад) |
ASA (обсуждение | вклад) |
||
| (не показано 7 промежуточных версий 2 участников) | |||
| Строка 1: | Строка 1: | ||
| − | == Свойства и структура | + | {{level-a}} |
| + | |||
| + | == Свойства и структура алгоритма == | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
'''Система непересекающихся множеств'''<ref>Tarjan, Robert Endre. “Efficiency of a Good but Not Linear Set Union Algorithm.” Journal of the ACM 22, no. 2 (April 1975): 215–25. doi:10.1145/321879.321884.</ref> представляет собой структуру данных и сопутствующие алгоритмы для хранения информации об элементах, объединённых в одно или несколько множеств. Алгоритмы позволяют указать, что два элемента находятся в одном и том же множестве, а также узнать, какому множеству принадлежит данный элемент (например, чтобы проверить, принадлежат ли два данных элемента одному и тому же множеству). | '''Система непересекающихся множеств'''<ref>Tarjan, Robert Endre. “Efficiency of a Good but Not Linear Set Union Algorithm.” Journal of the ACM 22, no. 2 (April 1975): 215–25. doi:10.1145/321879.321884.</ref> представляет собой структуру данных и сопутствующие алгоритмы для хранения информации об элементах, объединённых в одно или несколько множеств. Алгоритмы позволяют указать, что два элемента находятся в одном и том же множестве, а также узнать, какому множеству принадлежит данный элемент (например, чтобы проверить, принадлежат ли два данных элемента одному и тому же множеству). | ||
| − | Названия на английском языке – '''Union-Find Data Structure''', '''Disjoint-Set Data Structure''', '''Merge-Find | + | Названия на английском языке – '''Union-Find Data Structure''', '''Disjoint-Set Data Structure''', '''Merge-Find Set'''. |
Систему непересекающихся множеств можно применить при решении следующих задач: | Систему непересекающихся множеств можно применить при решении следующих задач: | ||
| − | * [[Связность в | + | * [[Связность в графах|поиск компонент связности графа]] за время <math>O(m \alpha(m, n)</math>; |
* восстановление отношения эквивалентности по его части; | * восстановление отношения эквивалентности по его части; | ||
* поддержание информации о текущих фрагментах графа в алгоритмах [[Построение минимального остовного дерева (MST)|построения минимального остовного дерева]]. | * поддержание информации о текущих фрагментах графа в алгоритмах [[Построение минимального остовного дерева (MST)|построения минимального остовного дерева]]. | ||
| Строка 13: | Строка 15: | ||
Система непересекающихся множеств может использоваться как онлайн-алгоритм, когда перемежаются запросы на объединение множеств и на определение множества по элементу. По этой причине этому подходу часто отдаётся предпочтение перед асимптотически более быстрым [[Поиск в ширину (BFS)|поиск в ширину]] (который решает ту же задачу о компонентах связности за линейное время <math>O(m)</math>). | Система непересекающихся множеств может использоваться как онлайн-алгоритм, когда перемежаются запросы на объединение множеств и на определение множества по элементу. По этой причине этому подходу часто отдаётся предпочтение перед асимптотически более быстрым [[Поиск в ширину (BFS)|поиск в ширину]] (который решает ту же задачу о компонентах связности за линейное время <math>O(m)</math>). | ||
| − | === Математическое описание === | + | === Математическое описание алгоритма === |
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
| − | === | + | === Схема реализации последовательного алгоритма === |
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
=== Информационный граф === | === Информационный граф === | ||
| − | === | + | === Ресурс параллелизма алгоритма === |
Система непересекающихся множеств допускает эффективную многопоточную реализацию <ref>Anderson, Richard J, and Heather Woll. “Wait-Free Parallel Algorithms for the Union-Find Problem,” 370–80, New York, New York, USA: ACM Press, 1991. doi:10.1145/103418.103458.</ref> в виде неблокирующего алгоритма «без ожидания». | Система непересекающихся множеств допускает эффективную многопоточную реализацию <ref>Anderson, Richard J, and Heather Woll. “Wait-Free Parallel Algorithms for the Union-Find Problem,” 370–80, New York, New York, USA: ACM Press, 1991. doi:10.1145/103418.103458.</ref> в виде неблокирующего алгоритма «без ожидания». | ||
| Строка 25: | Строка 27: | ||
Параллельный [[Алгоритм Шилоаха-Вишкина поиска компонент связности|алгоритм Шилоаха-Вишкина]] использует аналогичную структуру данных и находит компоненты связности за время <math>O(\ln n)</math> на <math>n + 2m</math> процессорах, однако не может использоваться как онлайн-алгоритм. | Параллельный [[Алгоритм Шилоаха-Вишкина поиска компонент связности|алгоритм Шилоаха-Вишкина]] использует аналогичную структуру данных и находит компоненты связности за время <math>O(\ln n)</math> на <math>n + 2m</math> процессорах, однако не может использоваться как онлайн-алгоритм. | ||
| − | === | + | === Входные и выходные данные алгоритма === |
| − | === Свойства алгоритма=== | + | === Свойства алгоритма === |
| − | == Программная реализация | + | |
| + | == Программная реализация алгоритма == | ||
=== Особенности реализации последовательного алгоритма === | === Особенности реализации последовательного алгоритма === | ||
| − | + | === Возможные способы и особенности параллельной реализации алгоритма === | |
| − | === Возможные способы и особенности реализации | + | === Результаты прогонов === |
| − | === | ||
| − | |||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
| − | |||
| − | |||
| − | |||
== Литература == | == Литература == | ||
<references /> | <references /> | ||
| + | |||
| + | [[Категория:Начатые статьи]] | ||
| + | |||
| + | [[en:Disjoint set union]] | ||
Текущая версия на 14:22, 6 июля 2022
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 3 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Система непересекающихся множеств[1] представляет собой структуру данных и сопутствующие алгоритмы для хранения информации об элементах, объединённых в одно или несколько множеств. Алгоритмы позволяют указать, что два элемента находятся в одном и том же множестве, а также узнать, какому множеству принадлежит данный элемент (например, чтобы проверить, принадлежат ли два данных элемента одному и тому же множеству).
Названия на английском языке – Union-Find Data Structure, Disjoint-Set Data Structure, Merge-Find Set.
Систему непересекающихся множеств можно применить при решении следующих задач:
- поиск компонент связности графа за время [math]O(m \alpha(m, n)[/math];
- восстановление отношения эквивалентности по его части;
- поддержание информации о текущих фрагментах графа в алгоритмах построения минимального остовного дерева.
Система непересекающихся множеств может использоваться как онлайн-алгоритм, когда перемежаются запросы на объединение множеств и на определение множества по элементу. По этой причине этому подходу часто отдаётся предпочтение перед асимптотически более быстрым поиск в ширину (который решает ту же задачу о компонентах связности за линейное время [math]O(m)[/math]).
1.2 Математическое описание алгоритма
1.3 Вычислительное ядро алгоритма
1.4 Макроструктура алгоритма
1.5 Схема реализации последовательного алгоритма
1.6 Последовательная сложность алгоритма
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
Система непересекающихся множеств допускает эффективную многопоточную реализацию [2] в виде неблокирующего алгоритма «без ожидания».
Параллельный алгоритм Шилоаха-Вишкина использует аналогичную структуру данных и находит компоненты связности за время [math]O(\ln n)[/math] на [math]n + 2m[/math] процессорах, однако не может использоваться как онлайн-алгоритм.
1.9 Входные и выходные данные алгоритма
1.10 Свойства алгоритма
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Возможные способы и особенности параллельной реализации алгоритма
2.3 Результаты прогонов
2.4 Выводы для классов архитектур
3 Литература
- ↑ Tarjan, Robert Endre. “Efficiency of a Good but Not Linear Set Union Algorithm.” Journal of the ACM 22, no. 2 (April 1975): 215–25. doi:10.1145/321879.321884.
- ↑ Anderson, Richard J, and Heather Woll. “Wait-Free Parallel Algorithms for the Union-Find Problem,” 370–80, New York, New York, USA: ACM Press, 1991. doi:10.1145/103418.103458.
