СНМ (списки с весовой эвристикой) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Определение == {{Определение| definition = '''Весовая эвристика'''(weighted-union heuristic) {{ --- }} улучшени...»)
 
м (rollbackEdits.php mass rollback)
 
(не показана 51 промежуточная версия 3 участников)
Строка 1: Строка 1:
== Определение ==
+
'''Весовая эвристика''' (weighted-union heuristic) {{ --- }} улучшение наивной реализации СНМ на списках с указателями на представителя. Позволяет добиться улучшения асимптотики с <tex>O(n^2)</tex> до <tex>O(n \log n)</tex> благодаря добавлению меньшего списка к большему при объединении множеств.
{{Определение|
 
definition =
 
'''Весовая эвристика'''(weighted-union heuristic) {{ --- }} улучшение наивной реализации СНМ, при котором список включает поле длины списка, и добавление идет всегда меньшего списка к большему.
 
}}
 
  
 
== Проблема наивной реализации ==
 
== Проблема наивной реализации ==
[[Файл:ve.png|thumb|600px|Реализация без весовой эвристики]]
+
[[Файл:ve.png|right|600px|Оценка количества переподвешиваний]]
Рассмотрим модифицированную наивную реализацию системы непересекающихся множеств с помощью списка. Кроме ссылок на следующий  элемент будем хранить ссылку на представителя, а для представителя ссылку на голову списка. При использовании такого представления, время работы процедур makeSet и findSet {{ --- }} <tex>O(1)</tex>. Процедуру union(x, y) мы выполняем, добавляя список с элементом x в список содержащий элемент y.  При этом мы должны обновить указатели на представителя у каждого объекта, который содержался в списке, содержащем x. Не трудно привести последовательность из m операций над n объектами, которая требует <tex>O(n^2)</tex> времени. Предположим, что у нас есть объекты <tex>x_1, x_2, ... x_n</tex>. Мы выполняем последовательность из n операций makeSet(или init), за которой следует последовательность из n - 1 операции union. m = n + (n - 1) = 2n - 1. На выполнение n операций makeSet мы тратим время <tex>O(n)</tex>. Поскольку i-ая операция union обновляет i объектов, общее количество объектов, обновленных всеми n - 1 операциями union равно <tex>\sum\limits_{i=1}^{n-1} i = O(n^2)</tex>. Общее количество операций равно 2n - 1, так что каждая операция в среднем требует для выполнения <tex>O(n)</tex>. Таким образом амортизированное время выполнения операции union составляет <tex>O(n)</tex>. В худшем случае представленная реализация процедуры union требует в среднем <tex>O(n)</tex> времени на вызов, поскольку может оказаться, что мы присоединяем длинный список к короткому и должны при этом обновить поля указателей на представителя всех членов длинного списка.
+
Рассмотрим реализацию системы непересекающихся множеств с помощью списков. Для каждого элемента списка будем хранить указатель на представителя и на следующий элемент в списке.
 +
 
 +
При такой реализации операция <tex> \mathrm {init} </tex> для создания n множеств состоящих из одного элемента займет <tex>O(n)</tex> времени. Для выполнения операции <tex> \mathrm {findSet} </tex> достаточно перейти по ссылке на представителя за <tex>O(1)</tex>. Узким местом такой реализации является операция <tex> \mathrm {union} </tex>. Слить списки и обновить указатели на представителя для одного из списков мы можем лишь за время пропорциональное количеству элементов.
 +
 
 +
Нетрудно придумать последовательность из <tex>n - 1</tex> операций <tex> \mathrm {union} </tex>, требующую <tex>O(n^2)</tex> времени. Достаточно каждый раз сливать одно и тоже множество с одним новым элементом в том порядке, чтобы требовалось обновить указатели на представителя именно элементам "большого" множества. Поскольку <tex>i</tex>-ая операция <tex> \mathrm {union} </tex> обновляет <tex>i</tex> указателей, общее количество указателей, обновленных всеми <tex>n - 1</tex> операциями <tex> \mathrm {union} </tex> равно <tex>\sum\limits_{i=1}^{n-1} i = O(n^2)</tex>. Отсюда следует, что амортизированное время выполнения операции <tex> \mathrm {union} </tex> составляет <tex>O(n)</tex>.
  
 
== Реализация с весовой эвристикой ==
 
== Реализация с весовой эвристикой ==
  
Предположим теперь, что каждый список включает также поле длины списка и что мы всегда добавляем меньший список к большему(при одинаковых длинах порядок добавления безразличен). При такой простейшей весовой эвристике одна операция union может потребовать <tex>\Omega(n)</tex> действий, если оба множества имеют <tex>\Omega(n)</tex> членов. Однако последовательность из m операций makeSet, union и findSet, n из которых составляют операции makeSet, требует для выполнения <tex>O(m + n \log n)</tex> времени.
+
Недостаток наивной реализации проявляется при слиянии относительно большого множества с множеством из одного элемента. В наивной реализации список указанный первым всегда подвешивается ко второму. Хотя в данном случае гораздо выгоднее подвесить меньший список к большему, обновив один указатель на представителя, вместо обновления большого числа указателей в первом списке. Отсюда следуют очевидная оптимизация {{ --- }} будем для каждого множества хранить его размер и изменять указатели на представителя всегда элементам из "меньшего" списка. Хотя одна операция <tex> \mathrm {union} </tex> по-прежнему может потребовать <tex>\Omega(n)</tex> действий, если оба множества имеют <tex>\Omega(n)</tex> членов, но последовательность из <tex>n</tex> операций <tex> \mathrm {union} </tex> требует <tex>O(n \log n)</tex> действий.
 +
 
 +
'''Псевдокод:'''
 +
s[n]
 +
'''function''' init():
 +
  '''for''' i = 0 '''to''' n - 1
 +
    s[i].set  = i    <font color = "green">// номер-идентификатор множества</font>
 +
    s[i].next = null
 +
    s[i].head = s[i]
 +
    s[i].tail = s[i] <font color = "green">// храним только для представителя</font>
 +
    s[i].count  = 1  <font color = "green">// храним только для представителя</font>
 +
 +
'''T''' find(x): <font color = "green">// подразумевается, что x {{ --- }} ссылка на один из элементов</font>
 +
  '''return''' x.head.set
 +
 +
'''function''' union(x, y):
 +
  x = x.head
 +
  y = y.head
 +
  '''if''' x == y
 +
    '''return'''
 +
  '''else'''
 +
    '''if''' x.count > y.count
 +
      swap(x, y)
 +
    i = x.head
 +
    '''while''' i != null
 +
      i.head = y
 +
      i = i.next
 +
    y.tail.next = x.head <font color = "green">// соединили списки</font>
 +
    y.tail = x.tail
 +
    y.count += x.count
  
 
== Доказательство оценки времени выполнения ==
 
== Доказательство оценки времени выполнения ==
  
 
{{Утверждение
 
{{Утверждение
|statement=При использовании связанных списков для представления СНМ и применении весовой эвристики, последовательность из m операций makeSet, union, и findSet, n из которых составляют операции makeSet, требует для выполнения <tex>O(m+n \log n)</tex> времени.
+
|statement=При реализации СНМ на списках с указателями на представителя и применении весовой эвристики, последовательность из операции <tex> \mathrm {init} </tex> для n элементов и m операций <tex> \mathrm {union} </tex> и <tex> \mathrm {findSet} </tex>, требует для выполнения <tex>O(m+n \log n)</tex> действий.
|proof = [[Файл:ve2.png|thumb|600px|Оценка количества переподвешиваний]] Вычислим верхнюю границу количества обновлений указателя на представителя для каждого множества из n элементов. Рассмотрим некий фиксированный объект. Когда мы обновляем указатель на представителя в объекте, он должен находиться в меньшем из множеств. Следовательно, при первом обновлении образованное множество хранит не менее 2 элементов, при втором не менее 4 элементов, и т.д. Продолжая рассуждение приходим к выводу о том, что при k <tex>\leqslant\</tex> n, после того как указатель на представителя в объекте обновлен <tex>\left\lceil \log k \right\rceil</tex>, полученное в результате множество должно иметь не менее k элементов. Поскольку максимальное множество может иметь не более n элементов, во всех операциях union указатель на представителя у каждого объекта может быть обновлен не более <tex>\left\lceil \log n \right\rceil</tex> раз. Необходимо также отметить, что обновление указателя на голову и next представителя, а также обновление длины списка при выполнении операции union требует <tex>O(1)</tex> времени. Таким образом, общее время, необходимое для обновления n объектов, составляет <tex>O(n \log n)</tex>.
+
|proof = [[Файл:ve2.png|right|600px|Оценка количества переподвешиваний]] Оценим время работы необходимое для обновления указателей на представителя в операциях <tex> \mathrm {union} </tex>. Рассмотрим количество обновлений отдельно для каждого элемента.
Отсюда легко понять, что время необходимое для выполнения всей последовательности из m операций составит <tex>O(m + n \log n)</tex>. <tex>O(m)</tex> операций makeSet и findSet, работающих за константное время и суммарное время работы операций union для каждого объекта.}}
+
 
 +
Оказывается, что для каждого элемента мы можем обновить указатель не более <tex>O(\log n)</tex> раз. Это связано с тем, что при каждом объединении, множество, в котором оказывается объект, увеличивается не менее чем вдвое. Действительно, так как мы обновляем указатель на представителя элементу, то этот элемент находился в меньшем из множеств (согласно нашей эвристике), но тогда размер второго множества не меньше. Тогда после первого обновления элемент содержится в множестве, в котором не менее двух элементов, после второго {{ --- }} четырех, и так далее. В силу того, что множество не может содержать более n элементов, количество обновлений не превосходит <tex>O(\log n)</tex>.
 +
 
 +
Таким образом, общее время, необходимое для обновления указателей для n элементов, составляет <tex>O(n \log n)</tex>.
 +
 
 +
Необходимо также отметить, что слить два списка и обновить поле длины при выполнении <tex> \mathrm {union} </tex> можно за константное количество операций (последние три строчки в псевдокоде).
 +
 
 +
Отсюда легко понять, что время необходимое для выполнения всей последовательности операций составит <tex>O(m + n \log n)</tex>. Операция <tex> \mathrm {init} </tex> за <tex>O(n)</tex>, <tex>O(m)</tex> операций <tex> \mathrm {findSet} </tex> и часть работы операции <tex> \mathrm {union} </tex> на обновление поля длины и слияния списков, каждая из которых выполняется за константное время, а также суммарное время обновления указателей на представителя операцией <tex> \mathrm {union} </tex> для каждого элемента за <tex>O(n \log n)</tex> действий.
 +
}}
  
 
== Другие реализации ==
 
== Другие реализации ==
Строка 24: Строка 61:
 
* [[СНМ(реализация с помощью леса корневых деревьев)]]
 
* [[СНМ(реализация с помощью леса корневых деревьев)]]
  
== Источники ==
+
== Ссылки ==
 +
* [http://habrahabr.ru/blogs/algorithm/104772/ habrahabr.ru - Система непересекающихся множеств и её применения]
 
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 585—588. — ISBN 5-8489-0857-4
 
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 585—588. — ISBN 5-8489-0857-4
 
== Ссылки ==
 
* [http://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств и её применения]
 
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]

Текущая версия на 19:38, 4 сентября 2022

Весовая эвристика (weighted-union heuristic) — улучшение наивной реализации СНМ на списках с указателями на представителя. Позволяет добиться улучшения асимптотики с [math]O(n^2)[/math] до [math]O(n \log n)[/math] благодаря добавлению меньшего списка к большему при объединении множеств.

Проблема наивной реализации

Оценка количества переподвешиваний

Рассмотрим реализацию системы непересекающихся множеств с помощью списков. Для каждого элемента списка будем хранить указатель на представителя и на следующий элемент в списке.

При такой реализации операция [math] \mathrm {init} [/math] для создания n множеств состоящих из одного элемента займет [math]O(n)[/math] времени. Для выполнения операции [math] \mathrm {findSet} [/math] достаточно перейти по ссылке на представителя за [math]O(1)[/math]. Узким местом такой реализации является операция [math] \mathrm {union} [/math]. Слить списки и обновить указатели на представителя для одного из списков мы можем лишь за время пропорциональное количеству элементов.

Нетрудно придумать последовательность из [math]n - 1[/math] операций [math] \mathrm {union} [/math], требующую [math]O(n^2)[/math] времени. Достаточно каждый раз сливать одно и тоже множество с одним новым элементом в том порядке, чтобы требовалось обновить указатели на представителя именно элементам "большого" множества. Поскольку [math]i[/math]-ая операция [math] \mathrm {union} [/math] обновляет [math]i[/math] указателей, общее количество указателей, обновленных всеми [math]n - 1[/math] операциями [math] \mathrm {union} [/math] равно [math]\sum\limits_{i=1}^{n-1} i = O(n^2)[/math]. Отсюда следует, что амортизированное время выполнения операции [math] \mathrm {union} [/math] составляет [math]O(n)[/math].

Реализация с весовой эвристикой

Недостаток наивной реализации проявляется при слиянии относительно большого множества с множеством из одного элемента. В наивной реализации список указанный первым всегда подвешивается ко второму. Хотя в данном случае гораздо выгоднее подвесить меньший список к большему, обновив один указатель на представителя, вместо обновления большого числа указателей в первом списке. Отсюда следуют очевидная оптимизация — будем для каждого множества хранить его размер и изменять указатели на представителя всегда элементам из "меньшего" списка. Хотя одна операция [math] \mathrm {union} [/math] по-прежнему может потребовать [math]\Omega(n)[/math] действий, если оба множества имеют [math]\Omega(n)[/math] членов, но последовательность из [math]n[/math] операций [math] \mathrm {union} [/math] требует [math]O(n \log n)[/math] действий.

Псевдокод:

s[n]
function init():
  for i = 0 to n - 1
    s[i].set  = i    // номер-идентификатор множества
    s[i].next = null
    s[i].head = s[i]
    s[i].tail = s[i] // храним только для представителя
    s[i].count  = 1  // храним только для представителя

T find(x): // подразумевается, что x — ссылка на один из элементов
  return x.head.set

function union(x, y): 
  x = x.head
  y = y.head
  if x == y
    return
  else
    if x.count > y.count
      swap(x, y)
    i = x.head
    while i != null
      i.head = y
      i = i.next
    y.tail.next = x.head // соединили списки
    y.tail = x.tail 
    y.count += x.count

Доказательство оценки времени выполнения

Утверждение:
При реализации СНМ на списках с указателями на представителя и применении весовой эвристики, последовательность из операции [math] \mathrm {init} [/math] для n элементов и m операций [math] \mathrm {union} [/math] и [math] \mathrm {findSet} [/math], требует для выполнения [math]O(m+n \log n)[/math] действий.
[math]\triangleright[/math]
Оценка количества переподвешиваний
Оценим время работы необходимое для обновления указателей на представителя в операциях [math] \mathrm {union} [/math]. Рассмотрим количество обновлений отдельно для каждого элемента.

Оказывается, что для каждого элемента мы можем обновить указатель не более [math]O(\log n)[/math] раз. Это связано с тем, что при каждом объединении, множество, в котором оказывается объект, увеличивается не менее чем вдвое. Действительно, так как мы обновляем указатель на представителя элементу, то этот элемент находился в меньшем из множеств (согласно нашей эвристике), но тогда размер второго множества не меньше. Тогда после первого обновления элемент содержится в множестве, в котором не менее двух элементов, после второго — четырех, и так далее. В силу того, что множество не может содержать более n элементов, количество обновлений не превосходит [math]O(\log n)[/math].

Таким образом, общее время, необходимое для обновления указателей для n элементов, составляет [math]O(n \log n)[/math].

Необходимо также отметить, что слить два списка и обновить поле длины при выполнении [math] \mathrm {union} [/math] можно за константное количество операций (последние три строчки в псевдокоде).

Отсюда легко понять, что время необходимое для выполнения всей последовательности операций составит [math]O(m + n \log n)[/math]. Операция [math] \mathrm {init} [/math] за [math]O(n)[/math], [math]O(m)[/math] операций [math] \mathrm {findSet} [/math] и часть работы операции [math] \mathrm {union} [/math] на обновление поля длины и слияния списков, каждая из которых выполняется за константное время, а также суммарное время обновления указателей на представителя операцией [math] \mathrm {union} [/math] для каждого элемента за [math]O(n \log n)[/math] действий.
[math]\triangleleft[/math]

Другие реализации

Ссылки