Уровень алгоритма

Система непересекающихся множеств: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][досмотренная версия]
 
(не показано 6 промежуточных версий 2 участников)
Строка 1: Строка 1:
== Свойства и структура алгоритмов ==
+
{{level-a}}
 +
 
 +
== Свойства и структура алгоритма ==
 
=== Общее описание алгоритма ===
 
=== Общее описание алгоритма ===
  
Строка 7: Строка 9:
  
 
Систему непересекающихся множеств можно применить при решении следующих задач:
 
Систему непересекающихся множеств можно применить при решении следующих задач:
* [[Связность в графа|поиск компонент связности графа]] за время <math>O(m \alpha(m, n)</math>;
+
* [[Связность в графах|поиск компонент связности графа]] за время <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> процессорах, однако не может использоваться как онлайн-алгоритм.
  
=== Описание входных и выходных данных ===
+
=== Входные и выходные данные алгоритма ===
=== Свойства алгоритма===
+
=== Свойства алгоритма ===
== Программная реализация алгоритмов ==
+
 
 +
== Программная реализация алгоритма ==
 
=== Особенности реализации последовательного алгоритма ===
 
=== Особенности реализации последовательного алгоритма ===
=== Описание локальности данных и вычислений ===
+
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Возможные способы и особенности реализации параллельного алгоритма ===
+
=== Результаты прогонов ===
=== Масштабируемость алгоритма и его реализации ===
 
=== Динамические характеристики и эффективность реализации алгоритма ===
 
 
=== Выводы для классов архитектур ===
 
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
 
 
* [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/incremental_components.html incremental_components]</code>).
 
  
 
== Литература ==
 
== Литература ==
  
 
<references />
 
<references />
 +
 +
[[Категория:Начатые статьи]]
 +
 +
[[en:Disjoint set union]]

Текущая версия на 14:22, 6 июля 2022


1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Система непересекающихся множеств[1] представляет собой структуру данных и сопутствующие алгоритмы для хранения информации об элементах, объединённых в одно или несколько множеств. Алгоритмы позволяют указать, что два элемента находятся в одном и том же множестве, а также узнать, какому множеству принадлежит данный элемент (например, чтобы проверить, принадлежат ли два данных элемента одному и тому же множеству).

Названия на английском языке – Union-Find Data Structure, Disjoint-Set Data Structure, Merge-Find Set.

Систему непересекающихся множеств можно применить при решении следующих задач:

Система непересекающихся множеств может использоваться как онлайн-алгоритм, когда перемежаются запросы на объединение множеств и на определение множества по элементу. По этой причине этому подходу часто отдаётся предпочтение перед асимптотически более быстрым поиск в ширину (который решает ту же задачу о компонентах связности за линейное время [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 Литература

  1. 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.
  2. 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.