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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Реализация с весовой эвристикой)
(Реализация с весовой эвристикой)
Строка 12: Строка 12:
  
 
Недостаток наивной реализации проявляется при слиянии относительно большого множества с множеством из одного элемента. В наивной реализации список указанный первым всегда подвешивается ко второму. Хотя в данном случае гораздо выгоднее подвесить меньший список к большему, обновив один указатель на представителя, вместо обновления большого числа указателей в первом списке. Отсюда следуют очевидная оптимизация {{ --- }} будем для каждого множества хранить его размер и изменять указатели на представителя всегда элементам из "меньшего" списка. Хотя одна операция union по-прежнему может потребовать <tex>\Omega(n)</tex> действий, если оба множества имеют <tex>\Omega(n)</tex> членов, но последовательность из <tex>n</tex> операций union требует <tex>O(n \log n)</tex> действий.
 
Недостаток наивной реализации проявляется при слиянии относительно большого множества с множеством из одного элемента. В наивной реализации список указанный первым всегда подвешивается ко второму. Хотя в данном случае гораздо выгоднее подвесить меньший список к большему, обновив один указатель на представителя, вместо обновления большого числа указателей в первом списке. Отсюда следуют очевидная оптимизация {{ --- }} будем для каждого множества хранить его размер и изменять указатели на представителя всегда элементам из "меньшего" списка. Хотя одна операция union по-прежнему может потребовать <tex>\Omega(n)</tex> действий, если оба множества имеют <tex>\Omega(n)</tex> членов, но последовательность из <tex>n</tex> операций union требует <tex>O(n \log n)</tex> действий.
 +
 +
'''Псевдокод:'''
 +
s[n]
 +
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
 +
 +
find(x): // подразумевается, что x {{ --- }} ссылка на один из элементов
 +
    return x.head.set
 +
 +
union(x, y): // здесь важно, что x и y {{ --- }} представители множеств
 +
    if x == y:
 +
        return
 +
    else:
 +
        if x.count > y.count:
 +
            swap(x, y)
 +
        i = x.tail
 +
        while i != null:
 +
            i.head = y
 +
            i = i.next
 +
        x.next = y.tail // соединили списки
 +
        y.count += x.count
  
 
== Доказательство оценки времени выполнения ==
 
== Доказательство оценки времени выполнения ==

Версия 23:11, 25 апреля 2012

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

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

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

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

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

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

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

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

Псевдокод:

s[n]
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

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

union(x, y): // здесь важно, что x и y — представители множеств
    if x == y:
        return
    else:
        if x.count > y.count:
            swap(x, y)
        i = x.tail
        while i != null:
            i.head = y
            i = i.next
        x.next = y.tail // соединили списки
        y.count += x.count

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

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

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

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

Необходимо также отметить, что слить два списка и обновить поле длины при выполнении union можно за [math]O(1)[/math].

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

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

Источники

  • Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 585—588. — ISBN 5-8489-0857-4

Ссылки