Система непересекающихся множеств - История изменений

ASA: /* Общее описание алгоритма */

2022-07-06T11:22:47Z

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

← Предыдущая версия		Версия от 11:22, 6 июля 2022
Строка 9:		Строка 9:

	Систему непересекающихся множеств можно применить при решении следующих задач:		Систему непересекающихся множеств можно применить при решении следующих задач:
	* [[Связность в ~~графа~~\|поиск компонент связности графа]] за время <math>O(m \alpha(m, n)</math>;		* [[Связность в графах\|поиск компонент связности графа]] за время <math>O(m \alpha(m, n)</math>;
	* восстановление отношения эквивалентности по его части;		* восстановление отношения эквивалентности по его части;
	* поддержание информации о текущих фрагментах графа в алгоритмах [[Построение минимального остовного дерева (MST)\|построения минимального остовного дерева]].		* поддержание информации о текущих фрагментах графа в алгоритмах [[Построение минимального остовного дерева (MST)\|построения минимального остовного дерева]].

ASA в 11:22, 6 июля 2022

2022-07-06T11:22:12Z

← Предыдущая версия		Версия от 11:22, 6 июля 2022
Строка 32:		Строка 32:
	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==
	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===
	~~=== Локальность данных и вычислений ===~~
	~~==== Локальность реализации алгоритма ====~~
	~~===== Структура обращений в память и качественная оценка локальности =====~~
	~~===== Количественная оценка локальности =====~~
	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===
	=== ~~Масштабируемость алгоритма и его реализации ===~~		=== Результаты прогонов ===
	~~==== Масштабируемость алгоритма ====~~
	~~==== Масштабируемость реализации алгоритма ====~~
	~~=== Динамические характеристики и эффективность реализации алгоритма~~ ===
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
	~~=== Существующие реализации алгоритма ===~~

	* [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/incremental_components.html incremental_components]</code>).
	* Java: [http://jgrapht.org JGraphT] (класс <code>[http://jgrapht.org/javadoc/org/jgrapht/alg/util/UnionFind.html UnionFind]</code>).

	== Литература ==		== Литература ==

ASA в 13:54, 14 марта 2018

2018-03-14T13:54:58Z

← Предыдущая версия		Версия от 13:54, 14 марта 2018
Строка 52:		Строка 52:

	[[Категория:Начатые статьи]]		[[Категория:Начатые статьи]]

			[[en:Disjoint set union]]

ASA в 14:14, 6 марта 2018

2018-03-06T14:14:34Z

← Предыдущая версия		Версия от 14:14, 6 марта 2018
Строка 1:		Строка 1:
			{{level-a}}

	== Свойства и структура алгоритма ==		== Свойства и структура алгоритма ==
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

ASA в 11:23, 29 июля 2015

2015-07-29T11:23:09Z

← Предыдущая версия		Версия от 11:23, 29 июля 2015
Строка 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 />

			[[Категория:Начатые статьи]]

Daryin: /* Существующие реализации алгоритма */

2015-06-11T19:38:23Z

Существующие реализации алгоритма

← Предыдущая версия		Версия от 19:38, 11 июня 2015
Строка 37:		Строка 37:

	* [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/incremental_components.html incremental_components]</code>).		* [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/incremental_components.html incremental_components]</code>).
	* Java: [http://jgrapht.org JGraphT] (класс [http://jgrapht.org/javadoc/org/jgrapht/alg/util/UnionFind.html UnionFind]).		* Java: [http://jgrapht.org JGraphT] (класс <code>[http://jgrapht.org/javadoc/org/jgrapht/alg/util/UnionFind.html UnionFind]</code>).

	== Литература ==		== Литература ==

	<references />		<references />

Daryin: /* Существующие реализации алгоритма */

2015-06-11T19:29:08Z

Существующие реализации алгоритма

← Предыдущая версия		Версия от 19:29, 11 июня 2015
Строка 37:		Строка 37:

	* [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/incremental_components.html incremental_components]</code>).		* [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/incremental_components.html incremental_components]</code>).
			* Java: [http://jgrapht.org JGraphT] (класс [http://jgrapht.org/javadoc/org/jgrapht/alg/util/UnionFind.html UnionFind]).

	== Литература ==		== Литература ==

	<references />		<references />

Daryin: /* Общее описание алгоритма */

2015-06-11T14:44:11Z

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

← Предыдущая версия		Версия от 14:44, 11 июня 2015
Строка 4:		Строка 4:
	'''Система непересекающихся множеств'''<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- Set'''.		Названия на английском языке – '''Union-Find Data Structure''', '''Disjoint-Set Data Structure''', '''Merge-Find Set'''.

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

Daryin: /* Существующие реализации алгоритма */

2015-06-10T23:14:41Z

Существующие реализации алгоритма

← Предыдущая версия		Версия от 23:14, 10 июня 2015
Строка 35:		Строка 35:
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===

			* [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 />

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

2015-06-05T14:28:32Z

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

Новая страница

== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===

'''Система непересекающихся множеств'''<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- Set'''.

Систему непересекающихся множеств можно применить при решении следующих задач:
* [[Связность в графа|поиск компонент связности графа]] за время <math>O(m \alpha(m, n)</math>;
* восстановление отношения эквивалентности по его части;
* поддержание информации о текущих фрагментах графа в алгоритмах [[Построение минимального остовного дерева (MST)|построения минимального остовного дерева]].

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

Параллельный [[Алгоритм Шилоаха-Вишкина поиска компонент связности|алгоритм Шилоаха-Вишкина]] использует аналогичную структуру данных и находит компоненты связности за время <math>O(\ln n)</math> на <math>n + 2m</math> процессорах, однако не может использоваться как онлайн-алгоритм.

=== Описание входных и выходных данных ===
=== Свойства алгоритма===
== Программная реализация алгоритмов ==
=== Особенности реализации последовательного алгоритма ===
=== Описание локальности данных и вычислений ===
=== Возможные способы и особенности реализации параллельного алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
== Литература ==

<references />