Система непересекающихся множеств: различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [непроверенная версия] |
Daryin (обсуждение | вклад) |
ASA (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
== Свойства и структура | == Свойства и структура алгоритма == | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
| Строка 13: | Строка 13: | ||
Система непересекающихся множеств может использоваться как онлайн-алгоритм, когда перемежаются запросы на объединение множеств и на определение множества по элементу. По этой причине этому подходу часто отдаётся предпочтение перед асимптотически более быстрым [[Поиск в ширину (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: | Строка 25: | ||
Параллельный [[Алгоритм Шилоаха-Вишкина поиска компонент связности|алгоритм Шилоаха-Вишкина]] использует аналогичную структуру данных и находит компоненты связности за время <math>O(\ln n)</math> на <math>n + 2m</math> процессорах, однако не может использоваться как онлайн-алгоритм. | Параллельный [[Алгоритм Шилоаха-Вишкина поиска компонент связности|алгоритм Шилоаха-Вишкина]] использует аналогичную структуру данных и находит компоненты связности за время <math>O(\ln n)</math> на <math>n + 2m</math> процессорах, однако не может использоваться как онлайн-алгоритм. | ||
=== | === Входные и выходные данные алгоритма === | ||
=== Свойства алгоритма=== | === Свойства алгоритма === | ||
== Программная реализация | |||
== Программная реализация алгоритма == | |||
=== Особенности реализации последовательного алгоритма === | === Особенности реализации последовательного алгоритма === | ||
=== | === Локальность данных и вычислений === | ||
=== Возможные способы и особенности реализации | ==== Локальность реализации алгоритма ==== | ||
===== Структура обращений в память и качественная оценка локальности ===== | |||
===== Количественная оценка локальности ===== | |||
=== Возможные способы и особенности параллельной реализации алгоритма === | |||
=== Масштабируемость алгоритма и его реализации === | === Масштабируемость алгоритма и его реализации === | ||
==== Масштабируемость алгоритма ==== | |||
==== Масштабируемость реализации алгоритма ==== | |||
=== Динамические характеристики и эффективность реализации алгоритма === | === Динамические характеристики и эффективность реализации алгоритма === | ||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
| Строка 42: | Строка 48: | ||
<references /> | <references /> | ||
[[Категория:Начатые статьи]] | |||
Версия от 11:23, 29 июля 2015
Свойства и структура алгоритма
Общее описание алгоритма
Система непересекающихся множеств[1] представляет собой структуру данных и сопутствующие алгоритмы для хранения информации об элементах, объединённых в одно или несколько множеств. Алгоритмы позволяют указать, что два элемента находятся в одном и том же множестве, а также узнать, какому множеству принадлежит данный элемент (например, чтобы проверить, принадлежат ли два данных элемента одному и тому же множеству).
Названия на английском языке – Union-Find Data Structure, Disjoint-Set Data Structure, Merge-Find Set.
Систему непересекающихся множеств можно применить при решении следующих задач:
- поиск компонент связности графа за время [math]\displaystyle{ O(m \alpha(m, n) }[/math];
- восстановление отношения эквивалентности по его части;
- поддержание информации о текущих фрагментах графа в алгоритмах построения минимального остовного дерева.
Система непересекающихся множеств может использоваться как онлайн-алгоритм, когда перемежаются запросы на объединение множеств и на определение множества по элементу. По этой причине этому подходу часто отдаётся предпочтение перед асимптотически более быстрым поиск в ширину (который решает ту же задачу о компонентах связности за линейное время [math]\displaystyle{ O(m) }[/math]).
Математическое описание алгоритма
Вычислительное ядро алгоритма
Макроструктура алгоритма
Схема реализации последовательного алгоритма
Последовательная сложность алгоритма
Информационный граф
Ресурс параллелизма алгоритма
Система непересекающихся множеств допускает эффективную многопоточную реализацию [2] в виде неблокирующего алгоритма «без ожидания».
Параллельный алгоритм Шилоаха-Вишкина использует аналогичную структуру данных и находит компоненты связности за время [math]\displaystyle{ O(\ln n) }[/math] на [math]\displaystyle{ n + 2m }[/math] процессорах, однако не может использоваться как онлайн-алгоритм.
Входные и выходные данные алгоритма
Свойства алгоритма
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Локальность данных и вычислений
Локальность реализации алгоритма
Структура обращений в память и качественная оценка локальности
Количественная оценка локальности
Возможные способы и особенности параллельной реализации алгоритма
Масштабируемость алгоритма и его реализации
Масштабируемость алгоритма
Масштабируемость реализации алгоритма
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
- Boost Graph Library (функция
incremental_components). - Java: JGraphT (класс
UnionFind).
Литература
- ↑ 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.