Система непересекающихся множеств: различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [непроверенная версия] |
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 /> | ||
| + | |||
| + | [[Категория:Начатые статьи]] | ||
Версия 14:23, 29 июля 2015
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 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.2.1 Локальность реализации алгоритма
2.2.1.1 Структура обращений в память и качественная оценка локальности
2.2.1.2 Количественная оценка локальности
2.3 Возможные способы и особенности параллельной реализации алгоритма
2.4 Масштабируемость алгоритма и его реализации
2.4.1 Масштабируемость алгоритма
2.4.2 Масштабируемость реализации алгоритма
2.5 Динамические характеристики и эффективность реализации алгоритма
2.6 Выводы для классов архитектур
2.7 Существующие реализации алгоритма
- Boost Graph Library (функция
incremental_components). - Java: JGraphT (класс
UnionFind).
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.
