Pull to refresh

Comments 29

Жму вашу сильную руку, уже на условие крепко задумался.
Серьезно так. Спасибо за проделанную работу, вы заставили мой мозг задуматься и дали ему пищу на ближайшие пару дней.
Как говорил Альберт Эйнштейн:«Сделай настолько просто, насколько это возможно, но не проще.»
Хорошо, когда используют такой подход
однако я пока так и не понял необходимости хранить множества в виде дерева. Этого требуют дополнительные какие-то условия?
Нет, просто именно такой способ обеспечивает наилучшую скорость работы. Можно хранить списками, можно настоящими множествами (set<T>), но тогда в любом случае какая-нибудь из операций окажется O(log2 N), O(N) и т.д. — слишком медленно.
Вам виднее какую в вашем случае операцию стоит оптимизировать. Но если операций чтения(поиска) будет меньше, чем операций создания(слияния), то алгоритмы стоит применять уже другие, которые так же имеют время работы О(1), но при этом используют меньше функций.
А еще я не могу понять как в теории это работает:
>Достаточно выбирать корень для переподвешивания случайным образом
можно поподробнее на русском языке?
В принципе там есть исходник, однако я не против объяснить и здесь.

У вас есть два элемента, X и Y. Вы стандартными операциями Find нашли корни их деревьев: пускай это RX и RY. Чтобы слить два дерева, достаточно один из корней подвесить к другому непосредственным сыном, то есть сделать просто либо P[RX] = Y, либо P[RY] = X. Встает вопрос, какой из двух вариантов выбирать?

В стандартной реализации для этого используется массив рангов, и мы выбираем вариант из принципа «дерево меньшей высоты подвешивать к дереву большей высоты». Однако можно обойтись и без этого. Просто принимаем решение случайно: каждый раз генерируем местным rand() случайное целое число от 0 до 1. Если это 0, подвешиваем RY к RX, если же 1 — то RX к RY.

Время работы такой реализации в среднем оценить достаточно проблемно. Однако если её действительно написать и протестировать на многих разнообразных данных, окажется, что она почти не уступает варианту с рангами.
а что мы делаем с рангами? Они какую роль играют в таком случае?
Никакую, они в такой реализации вообще не нужны, их можно не считать и не хранить.
Я малость запутался уже, так что буду уточнять. Т.е. дерево у вас хранится в виде одномерного массива? И все?
Но ведь вы так же писали
>Будем хранить помимо предков еще один массив Rank.
Он уже стал не нужен?
Вот именно!
Это два разных варианта реализации одной и той же функции Unite.
В одной нам нужно хранить массив Rank — мы пользуемся им при принятии решения о переподвешивании.
В другой мы принимаем это решение случайным образом, а значит, массив Rank в ней нам не нужен.

Я привел обе реализации, потому что первая является классической, для неё доказана оценка скорости O(α(N)), а вторую проще писать, а на практике она работает почти так же быстро.
пока не могу понять, завтра на свежую голову еще раз прочту
За дальнейшими техническими подробностями отсылаю читателей к <a href=''file///E:/Informatic@NeXT/10.1.1.79.8494.pdf''>оригинальной статье</a>.
спасибо, как-нибудь к вам заедем :)
Сорри. Походу, топики надо дописывать в более выспавшемся состоянии :) Исправил.
Периодически использую этот алгоритм. Подробный анализ временной оценки сложности можно найти у самого Тарьяна в его замечательной книге Data Structures and Network Algorithms, отрывки из которой разбросаны по всей сети.

Автор, Вы разбираетесь в математике, да? Можете разъяснить, что такое многомерные множества?
Множество, имеющее размерность n (имеется ввиду размерность Хаусдорфа). Например, множество всех точек прямой одномерно, множество всех точек квадрата двумерно и т.д.
Разумеется, разговор о размерности множества в метрическом пространстве. Метрическое пространство — всего лишь множество, на котором определено расстояние между двумя соседними элементами.
В случае векторных пространств, множество имеет размерность n если в нем существует базис (максимальный набор линейно независимых векторов) размера n.
Но не каждое множество имеет размерность.
За иллюстрации спасибо. Все равно большинство забудет через пару дней текст, а вот картинки вспомнят и через неделю, может и смутно.
Спасибо огромное, особенно за популяризацию деревьев!

Продолжайте!
Вы бы указали, что оценка сложности справедлива только когда ранги хранятся. А то подумает ещё кто, что в рандомизированной версии всё тоже так хорошо.
Ну это в комментах обсуждалось. Для рандомизированной версии вообще трудно указать оценку сложности, можно ориентироваться только на практические тесты. А они хорошие.
Упс, проглядел. Кстати, любопытно, что оно на практике так же быстро работает. В этой вашей практике какого порядка N было?
Так то мало довольно, тут и логарифм слабо отличим от константы)
Могу протестить на 108. Все равно не думаю, что результаты будут сильно отличаться.
наконец смогу написать быстрое решение задачки 1003 с тимуса :-)
Only those users with full accounts are able to leave comments. Log in, please.